Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "bits/stdc++.h"
- using namespace std;
- #define x first
- #define y second
- #define pb push_back
- #define mp make_pair
- #define all(a) (a).begin(), (a).end()
- #define rall(a) (a).rbegin(), (a).rend()
- #define sz(a) int((a).size())
- #define sqr(x) ((x)*(x))
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- #define NAME "sqrtnim"
- #define FREOPEN freopen(NAME".in", "r", stdin); freopen(NAME".out", "w", stdout);
- #define Freopen freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
- typedef unsigned int unt;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- typedef pair <int, int> pii;
- typedef pair <ll, ll> pll;
- typedef long double geom;
- const ll MOD = 1e9 + 7;
- const int INF = 2e9;
- const ll INF64 = 9e18;
- const ld EPS = 1e-12;
- const ld PI = 3.1415926535897932384626433832795028841;
- const ll MD = 925262732;
- const ll T = 634521;
- const int N = 100010;
- const int M = 501;
- int n;
- string s;
- bool d[N][11][11], mark[N][11][11];
- int ans[N];
- bool rec(int l, int x, int y, int zz = 0)
- {
- int r = n - l - 1 + zz;
- if (l > r)
- return (x == y);
- if (mark[l][x][y])
- return d[l][x][y];
- bool f = 0;
- if (l == r)
- {
- for (int i = 0; i < 10; i++)
- if ((i + i + y) % 10 == int(s[l] - '0') && (i + i + y) / 10 == x)
- {
- f = 1;
- }
- }
- else
- {
- for (int i = 0; i < 10; i++)
- for (int j = 0; j < 10; j++)
- for (int u = 0; u < 10; u++)
- if ((i + j + y) % 10 == int(s[r] - '0') && (i + j + u) % 10 == int(s[l] - '0') && (i + j + u) / 10 == x && rec(l + 1, u, (i + j + y) / 10, zz))
- {
- f = 1;
- }
- }
- mark[l][x][y] = 1;
- d[l][x][y] = f;
- return f;
- }
- void dfs(int l, int x, int y, int zz = 0)
- {
- int r = n - l - 1 + zz;
- if (l > r)
- return;
- if (l == r)
- {
- for (int i = 0; i < 10; i++)
- if ((i + i + y) % 10 == int(s[l] - '0') && (i + i + y) / 10 == x)
- {
- ans[l] = i;
- return;
- }
- }
- else
- {
- for (int i = 0; i < 10; i++)
- for (int j = 0; j < 10; j++)
- for (int u = 0; u < 10; u++)
- if ((i + j + y) % 10 == int(s[r] - '0') && (i + j + u) % 10 == int(s[l] - '0') && (i + j + u) / 10 == x && rec(l + 1, u, (i + j + y) / 10, zz))
- {
- ans[l] = i;
- dfs(l + 1, u, (i + j + y) / 10, zz);
- ans[r] = j;
- return;
- }
- }
- }
- int main()
- {
- cin >> s;
- n = sz(s);
- if (!rec(0, 0, 0))
- {
- forn(i, N)
- forn(x, 11)
- forn(y, 11)
- mark[i][x][y] = d[i][x][y] = 0;
- if (rec(1, int(s[0] - '0'), 0, 1))
- {
- dfs(1, int(s[0] - '0'), 0, 1);
- int t = n - 1;
- while (t >= 0 && ans[t] == 0)
- t--;
- for (int i = t; i >= 1; i--)
- printf("%d", ans[i]);
- return 0;
- }
- cout << 0;
- }
- else
- {
- int t = n - 1;
- dfs(0, 0, 0);
- while (t >= 0 && ans[t] == 0)
- t--;
- for (int i = t; i >= 0; i--)
- printf("%d", ans[i]);
- }
- return 0;
- }
- /*
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement