Advertisement
Guest User

Untitled

a guest
Feb 7th, 2016
52
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.44 KB | None | 0 0
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. #define x first
  6. #define y second
  7. #define pb push_back
  8. #define mp make_pair
  9. #define all(a) (a).begin(), (a).end()
  10. #define rall(a) (a).rbegin(), (a).rend()
  11. #define sz(a) int((a).size())
  12. #define sqr(x) ((x)*(x))
  13. #define forn(i, n) for (int i = 0; i < int(n); i++)
  14. #define NAME "sqrtnim"
  15. #define FREOPEN freopen(NAME".in", "r", stdin); freopen(NAME".out", "w", stdout);
  16. #define Freopen freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
  17.  
  18. typedef unsigned int unt;
  19. typedef long long ll;
  20. typedef unsigned long long ull;
  21. typedef long double ld;
  22. typedef pair <int, int> pii;
  23. typedef pair <ll, ll> pll;
  24. typedef long double geom;
  25.  
  26. const ll MOD = 1e9 + 7;
  27. const int INF = 2e9;
  28. const ll INF64 = 9e18;
  29. const ld EPS = 1e-12;
  30. const ld PI = 3.1415926535897932384626433832795028841;
  31. const ll MD = 925262732;
  32. const ll T = 634521;
  33. const int N = 100010;
  34. const int M = 501;
  35.  
  36. int n;
  37. string s;
  38. bool d[N][11][11], mark[N][11][11];
  39. int ans[N];
  40.  
  41. bool rec(int l, int x, int y, int zz = 0)
  42. {
  43. int r = n - l - 1 + zz;
  44. if (l > r)
  45. return (x == y);
  46. if (mark[l][x][y])
  47. return d[l][x][y];
  48. bool f = 0;
  49. if (l == r)
  50. {
  51. for (int i = 0; i < 10; i++)
  52. if ((i + i + y) % 10 == int(s[l] - '0') && (i + i + y) / 10 == x)
  53. {
  54. f = 1;
  55. }
  56. }
  57. else
  58. {
  59. for (int i = 0; i < 10; i++)
  60. for (int j = 0; j < 10; j++)
  61. for (int u = 0; u < 10; u++)
  62. 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))
  63. {
  64. f = 1;
  65. }
  66. }
  67. mark[l][x][y] = 1;
  68. d[l][x][y] = f;
  69. return f;
  70. }
  71.  
  72. void dfs(int l, int x, int y, int zz = 0)
  73. {
  74. int r = n - l - 1 + zz;
  75. if (l > r)
  76. return;
  77. if (l == r)
  78. {
  79. for (int i = 0; i < 10; i++)
  80. if ((i + i + y) % 10 == int(s[l] - '0') && (i + i + y) / 10 == x)
  81. {
  82. ans[l] = i;
  83. return;
  84. }
  85. }
  86. else
  87. {
  88. for (int i = 0; i < 10; i++)
  89. for (int j = 0; j < 10; j++)
  90. for (int u = 0; u < 10; u++)
  91. 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))
  92. {
  93. ans[l] = i;
  94. dfs(l + 1, u, (i + j + y) / 10, zz);
  95. ans[r] = j;
  96. return;
  97. }
  98. }
  99. }
  100.  
  101. int main()
  102. {
  103. cin >> s;
  104. n = sz(s);
  105. if (!rec(0, 0, 0))
  106. {
  107. forn(i, N)
  108. forn(x, 11)
  109. forn(y, 11)
  110. mark[i][x][y] = d[i][x][y] = 0;
  111. if (rec(1, int(s[0] - '0'), 0, 1))
  112. {
  113. dfs(1, int(s[0] - '0'), 0, 1);
  114. int t = n - 1;
  115. while (t >= 0 && ans[t] == 0)
  116. t--;
  117. for (int i = t; i >= 1; i--)
  118. printf("%d", ans[i]);
  119. return 0;
  120. }
  121. cout << 0;
  122. }
  123. else
  124. {
  125. int t = n - 1;
  126. dfs(0, 0, 0);
  127. while (t >= 0 && ans[t] == 0)
  128. t--;
  129. for (int i = t; i >= 0; i--)
  130. printf("%d", ans[i]);
  131. }
  132. return 0;
  133. }
  134.  
  135. /*
  136.  
  137.  
  138.  
  139.  
  140. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement