QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#771108#3596. New MathsMade_in_CodeAC ✓0ms3712kbC++141.2kb2024-11-22 09:54:152024-11-22 09:54:21

Judging History

你现在查看的是最新测评结果

  • [2024-11-22 09:54:21]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3712kb
  • [2024-11-22 09:54:15]
  • 提交

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'