Advertisement
Guest User

Untitled

a guest
Apr 28th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define FOR(i,a,b) for (int i = (a); i < (b); i++)
  5. #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
  6. #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
  7. #define FILL(a,value) memset(a, value, sizeof(a))
  8.  
  9. #define SZ(a) (int)a.size()
  10. #define ALL(a) a.begin(), a.end()
  11. #define PB push_back
  12. #define MP make_pair
  13.  
  14. typedef long long LL;
  15. typedef vector<int> VI;
  16. typedef pair<int, int> PII;
  17.  
  18. const double PI = acos(-1.0);
  19. const int INF = 1000 * 1000 * 1000 + 7;
  20. const LL LINF = INF * (LL) INF;
  21.  
  22. const int MAX = 256;
  23.  
  24. int DP[MAX][MAX];
  25.  
  26.  
  27. int main()
  28. {
  29.     //reopen("in.txt", "r", stdin);
  30.     ios::sync_with_stdio(false); cin.tie(0);
  31.  
  32.     string s;
  33.     while(getline(cin, s))
  34.     {
  35.         int n = SZ(s);
  36.  
  37.         FOR (i, 0, n)
  38.         {
  39.             DP[i][i] = 0;
  40.             if (i) DP[i][i-1] = 1;
  41.         }
  42.  
  43.         FOR (len, 2, n+1)
  44.         {
  45.             FOR (i, 0, n)
  46.             {
  47.                 int L = i;
  48.                 int R = i + len - 1;
  49.                 if (R >= n) break;
  50.  
  51.                 DP[L][R] = false;
  52.                 if (s[L] == s[R])
  53.                 {
  54.                     if (DP[L+1][R-1])
  55.                     {
  56.                         DP[L][R] = true;
  57.                         continue;
  58.                     }
  59.                 }
  60.  
  61.                 FOR (k, L, R)
  62.                 {
  63.                     if (DP[L][k] && DP[k+1][R])
  64.                     {
  65.                         DP[L][R] = true;
  66.                         break;
  67.                     }
  68.                 }
  69.  
  70.                 if (DP[L][R]) continue;
  71.  
  72.                 if (s[L] == s[R])
  73.                 {
  74.                     FOR (k, L+1, R)
  75.                     {
  76.                         if (s[k] == s[L])
  77.                         {
  78.                             if (DP[L+1][k-1] && DP[k+1][R-1])
  79.                             {
  80.                                 DP[L][R] = true;
  81.                                 break;
  82.                             }
  83.                         }
  84.                     }
  85.                 }
  86.             }
  87.         }
  88.  
  89.         if (DP[0][n-1]) cout<<"solvable\n";
  90.         else cout<<"unsolvable\n";
  91.     }
  92.  
  93.  
  94.  
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement