Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <stack>
- #include <string>
- #include <vector>
- using namespace std;
- vector<string> ans;
- stack<string> st;
- bool check(const string& cur, const string s) {
- if (cur.size() * 2 - 1 > s.size()) {
- return false;
- }
- vector<int> a(100, 0);
- for (size_t i = 0; i < cur.size(); i++) {
- for (size_t j = 0; j < cur.size(); j++) {
- a[i + j] += (cur[i] - '0') * (cur[j] - '0') % 10;
- a[i + j] %= 10;
- }
- }
- if (cur.size() * 2 - 1 == s.size()) {
- for (size_t i = 0; i < cur.size() * 2 - 1; i++) {
- if (s[i] - '0' != a[i]) {
- return false;
- }
- }
- return true;
- }
- for (size_t i = 0; i < cur.size(); i++) {
- if (s[i] - '0' != a[i]) {
- return false;
- }
- }
- return true;
- }
- int main() {
- string s; cin >> s;
- reverse(s.begin(), s.end());
- st.push("");
- while (!st.empty()) {
- string cur = st.top();
- st.pop();
- for (size_t i = 0; i < 10; i++) {
- cur.push_back(i + '0');
- if (check(cur, s)) {
- if (cur.size() * 2 - 1 == s.size()) {
- ans.push_back(cur);
- } else {
- st.push(cur);
- }
- }
- cur.pop_back();
- }
- }
- for (auto& item : ans) {
- reverse(item.begin(), item.end());
- }
- sort(ans.begin(), ans.end());
- if (ans.empty()) {
- cout << -1 << endl;
- } else {
- cout << ans[0] << endl;
- }
- /*
- cout << ans.size() << endl;
- for (auto& item : ans) {
- cout << item << endl;
- }
- */
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement