QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#771108 | #3596. New Maths | Made_in_Code | AC ✓ | 0ms | 3712kb | C++14 | 1.2kb | 2024-11-22 09:54:15 | 2024-11-22 09:54:21 |
Judging History
answer
#include <iostream>
#define LL long long
using namespace std;
const LL kMaxN = 26, kInf = 1e13;
int a[kMaxN];
LL ans;
string s;
void S(int x) {
if (x * 2 >= s.size()) {
for (int i = x; i < s.size(); i++) {
int w = 0;
for (int j = 0; j <= i; j++) {
w += a[j] * a[i - j];
}
if (w % 10 != s[i] - '0') {
return;
}
}
LL t = 0;
for (int i = x - 1; i >= 0; i--) {
t = t * 10 + a[i];
}
ans = min(ans, t);
return;
}
int w = 0;
for (int i = 1; i < x; i++) {
w += a[i] * a[x - i];
}
w = (w - (s[x] - '0') + 10) % 10;
for (int i = 0; i < 10; i++) {
if ((2 * a[0] * i + w) % 10 == 0) {
a[x] = i, S(x + 1);
}
}
}
int main() {
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(0);
cin >> s;
if (s.size() & 1 ^ 1) {
cout << -1 << '\n';
} else {
ans = kInf;
for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
swap(s[i], s[j]);
}
for (int i = 0; i < 10; i++) {
if (i * i % 10 == s[0] - '0') {
a[0] = i, S(1);
}
}
cout << (ans == kInf ? -1 : ans) << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
6
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
149
output:
17
result:
ok single line: '17'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
123476544
output:
11112
result:
ok single line: '11112'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
15
output:
-1
result:
ok single line: '-1'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
255768423183
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
45665732555
output:
-1
result:
ok single line: '-1'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
129862724660409
output:
11450607
result:
ok single line: '11450607'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
423019449793954427977
output:
-1
result:
ok single line: '-1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
27121
output:
-1
result:
ok single line: '-1'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
1062062012267214086
output:
1086309746
result:
ok single line: '1086309746'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
7121439534552006831
output:
-1
result:
ok single line: '-1'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
2331
output:
-1
result:
ok single line: '-1'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
664
output:
42
result:
ok single line: '42'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
48960202843634584
output:
270467972
result:
ok single line: '270467972'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
950191368742123
output:
-1
result:
ok single line: '-1'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
6838729832825874768072709
output:
4195767732753
result:
ok single line: '4195767732753'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
126412441
output:
16521
result:
ok single line: '16521'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4466447004844686806
output:
2609442604
result:
ok single line: '2609442604'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
4
output:
2
result:
ok single line: '2'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
90074858599988014
output:
-1
result:
ok single line: '-1'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
9498578088490196330623
output:
-1
result:
ok single line: '-1'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
82
output:
-1
result:
ok single line: '-1'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
8925123681749359895
output:
-1
result:
ok single line: '-1'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
9008004
output:
3008
result:
ok single line: '3008'