Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define FOR(i,a,b) for (int i = (a); i < (b); i++)
- #define RFOR(i,b,a) for (int i = (b)-1; i >= (a); i--)
- #define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
- #define FILL(a,value) memset(a, value, sizeof(a))
- #define SZ(a) (int)a.size()
- #define ALL(a) a.begin(), a.end()
- #define PB push_back
- #define MP make_pair
- typedef long long LL;
- typedef vector<int> VI;
- typedef pair<int, int> PII;
- const double PI = acos(-1.0);
- const int INF = 1000 * 1000 * 1000 + 7;
- const LL LINF = INF * (LL) INF;
- const int MAX = 256;
- int DP[MAX][MAX];
- int main()
- {
- //reopen("in.txt", "r", stdin);
- ios::sync_with_stdio(false); cin.tie(0);
- string s;
- while(getline(cin, s))
- {
- int n = SZ(s);
- FOR (i, 0, n)
- {
- DP[i][i] = 0;
- if (i) DP[i][i-1] = 1;
- }
- FOR (len, 2, n+1)
- {
- FOR (i, 0, n)
- {
- int L = i;
- int R = i + len - 1;
- if (R >= n) break;
- DP[L][R] = false;
- if (s[L] == s[R])
- {
- if (DP[L+1][R-1])
- {
- DP[L][R] = true;
- continue;
- }
- }
- FOR (k, L, R)
- {
- if (DP[L][k] && DP[k+1][R])
- {
- DP[L][R] = true;
- break;
- }
- }
- if (DP[L][R]) continue;
- if (s[L] == s[R])
- {
- FOR (k, L+1, R)
- {
- if (s[k] == s[L])
- {
- if (DP[L+1][k-1] && DP[k+1][R-1])
- {
- DP[L][R] = true;
- break;
- }
- }
- }
- }
- }
- }
- if (DP[0][n-1]) cout<<"solvable\n";
- else cout<<"unsolvable\n";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement