Advertisement
Guest User

Untitled

a guest
Nov 18th, 2019
140
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.74 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <stack>
  4. #include <string>
  5. #include <vector>
  6.  
  7. using namespace std;
  8.  
  9. vector<string> ans;
  10. stack<string> st;
  11.  
  12. bool check(const string& cur, const string s) {
  13. if (cur.size() * 2 - 1 > s.size()) {
  14. return false;
  15. }
  16. vector<int> a(100, 0);
  17. for (size_t i = 0; i < cur.size(); i++) {
  18. for (size_t j = 0; j < cur.size(); j++) {
  19. a[i + j] += (cur[i] - '0') * (cur[j] - '0') % 10;
  20. a[i + j] %= 10;
  21. }
  22. }
  23. if (cur.size() * 2 - 1 == s.size()) {
  24. for (size_t i = 0; i < cur.size() * 2 - 1; i++) {
  25. if (s[i] - '0' != a[i]) {
  26. return false;
  27. }
  28. }
  29. return true;
  30. }
  31. for (size_t i = 0; i < cur.size(); i++) {
  32. if (s[i] - '0' != a[i]) {
  33. return false;
  34. }
  35. }
  36. return true;
  37. }
  38.  
  39. int main() {
  40. string s; cin >> s;
  41. reverse(s.begin(), s.end());
  42. st.push("");
  43. while (!st.empty()) {
  44. string cur = st.top();
  45. st.pop();
  46. for (size_t i = 0; i < 10; i++) {
  47. cur.push_back(i + '0');
  48. if (check(cur, s)) {
  49. if (cur.size() * 2 - 1 == s.size()) {
  50. ans.push_back(cur);
  51. } else {
  52. st.push(cur);
  53. }
  54. }
  55. cur.pop_back();
  56. }
  57. }
  58.  
  59. for (auto& item : ans) {
  60. reverse(item.begin(), item.end());
  61. }
  62.  
  63. sort(ans.begin(), ans.end());
  64. if (ans.empty()) {
  65. cout << -1 << endl;
  66. } else {
  67. cout << ans[0] << endl;
  68. }
  69. /*
  70. cout << ans.size() << endl;
  71. for (auto& item : ans) {
  72. cout << item << endl;
  73. }
  74. */
  75. return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement