QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#772923 | #3596. New Maths | wcyQwQ | AC ✓ | 0ms | 3864kb | C++14 | 1.3kb | 2024-11-22 22:59:22 | 2024-11-22 22:59:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
string s;
map<string, int> ans;
int conv[30];
void dfs(string t) {
if (t.size() == (s.size() + 1) / 2) {
for (int i = 0; i < s.size(); i++) {
if (s[i] - '0' != conv[i]) return;
}
reverse(t.begin(), t.end());
ans[t];
return;
}
for (int d = 0; d <= 9; d++) {
if (!t.size()) {
if (d * d % 10 == s[0] - '0') {
conv[0] = d * d % 10;
t += '0' + d;
dfs(t);
t.pop_back();
conv[0] = 0;
}
}
else {
int ck = (conv[t.size()] + 2 * d * (t[0] - '0')) % 10;
if (ck == s[t.size()] - '0') {
for (int i = 0; i < t.size(); i++) (conv[t.size() + i] += 2 * d * (t[i] - '0')) %= 10;
conv[2 * t.size()] = d * d % 10;
t += '0' + d;
dfs(t);
t.pop_back();
for (int i = 0; i < t.size(); i++) (conv[t.size() + i] -= 2 * d * (t[i] - '0')) %= 10, (conv[t.size() + i] += 10) %= 10;
conv[2 * t.size()] = 0;
}
}
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> s;
reverse(s.begin(), s.end());
if (s.size() % 2 == 0) cout << -1 << '\n';
else {
dfs("");
cout << (ans.size() ? (*ans.begin()).first : "-1") << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3556kb
input:
6
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
149
output:
17
result:
ok single line: '17'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
123476544
output:
11112
result:
ok single line: '11112'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
15
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
255768423183
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
45665732555
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
129862724660409
output:
11450607
result:
ok single line: '11450607'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
423019449793954427977
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
27121
output:
-1
result:
ok single line: '-1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1062062012267214086
output:
1086309746
result:
ok single line: '1086309746'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
7121439534552006831
output:
-1
result:
ok single line: '-1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
2331
output:
-1
result:
ok single line: '-1'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
664
output:
42
result:
ok single line: '42'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
48960202843634584
output:
270467972
result:
ok single line: '270467972'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
950191368742123
output:
-1
result:
ok single line: '-1'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
6838729832825874768072709
output:
4195767732753
result:
ok single line: '4195767732753'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
126412441
output:
16521
result:
ok single line: '16521'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4466447004844686806
output:
2609442604
result:
ok single line: '2609442604'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
4
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
90074858599988014
output:
-1
result:
ok single line: '-1'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
9498578088490196330623
output:
-1
result:
ok single line: '-1'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
82
output:
-1
result:
ok single line: '-1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
8925123681749359895
output:
-1
result:
ok single line: '-1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
9008004
output:
3008
result:
ok single line: '3008'