QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#134647	#5729. Carry Cam Failure	Nicolas125841	AC ✓	1ms	3588kb	C++17	1.7kb	2023-08-04 12:08:46	2023-08-04 12:08:47

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-08-04 12:08:47]
评测

测评结果：AC
用时：1ms
内存：3588kb

查看

[2023-08-04 12:08:46]
提交

answer

#include<bits/stdc++.h>

using namespace std;

bool solve(vector<int> &num, vector<int> &stack, int ind, int cap){
    if(ind == 0){
        for(int i = 0; i < 10; i++){
            if((i * i) % 10 == num[ind]){
                stack.push_back(i);

                if(solve(num, stack, ind + 1, cap)){
                    return true;
                }

                stack.pop_back();
            }
        }

        return false;
    }else if(ind == num.size()){
        return true;
    }else if(ind > cap){
        int cnst = 0;

        for(int i = ind - cap; i <= cap; i++){
            cnst += stack[i] * stack[ind - i];
        }

        if(cnst % 10 == num[ind]){
            return solve(num, stack, ind + 1, cap);
        }

        return false;
    }else{
        int cnst = 0;
        int coef = 2 * stack[0];

        for(int i = 1; i < ind; i++){
            cnst += stack[i] * stack[ind - i];
        }

        for(int i = 0; i < 10; i++){
            if((cnst + coef * i) % 10 == num[ind]){
                stack.push_back(i);

                if(solve(num, stack, ind + 1, cap)){
                    return true;
                }

                stack.pop_back();
            }
        }

        return false;
    }
}

int main(){
    cin.tie(NULL)->sync_with_stdio(false);

    string num;
    cin >> num;

    vector<int> nnum(num.size());

    transform(num.begin(), num.end(), nnum.begin(), [](const char &c) { return c - '0'; });

    vector<int> stack;
    
    if(nnum.size() & 1 && solve(nnum, stack, 0, (nnum.size() - 1) / 2)){
        for(int v : stack)
            cout << v;
        cout << "\n";
    }else{
        cout << "-1\n";
    }
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3540kb

input:

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 1ms

memory: 3520kb

input:

output:

result:

ok single line: '17'

Test #3:

score: 0

Accepted

time: 1ms

memory: 3568kb

input:

123476544

output:

result:

ok single line: '11112'

Test #4:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

output:

-1

result:

ok single line: '-1'

Test #5:

score: 0

Accepted

time: 1ms

memory: 3536kb

input:

255768423183

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0

Accepted

time: 1ms

memory: 3448kb

input:

45665732555

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3476kb

input:

129862724660409

output:

11450607

result:

ok single line: '11450607'

Test #8:

score: 0

Accepted

time: 1ms

memory: 3588kb

input:

423019449793954427977

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0

Accepted

time: 1ms

memory: 3492kb

input:

output:

-1

result:

ok single line: '-1'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

1062062012267214086

output:

1086309746

result:

ok single line: '1086309746'

Test #11:

score: 0

Accepted

time: 1ms

memory: 3516kb

input:

7121439534552006831

output:

-1

result:

ok single line: '-1'

Test #12:

score: 0

Accepted

time: 1ms

memory: 3472kb

input:

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0

Accepted

time: 1ms

memory: 3512kb

input:

output:

result:

ok single line: '42'

Test #14:

score: 0

Accepted

time: 1ms

memory: 3496kb

input:

48960202843634584

output:

270467972

result:

ok single line: '270467972'

Test #15:

score: 0

Accepted

time: 1ms

memory: 3492kb

input:

950191368742123

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0

Accepted

time: 1ms

memory: 3580kb

input:

6838729832825874768072709

output:

4195767732753

result:

ok single line: '4195767732753'

Test #17:

score: 0

Accepted

time: 1ms

memory: 3448kb

input:

126412441

output:

result:

ok single line: '16521'

Test #18:

score: 0

Accepted

time: 1ms

memory: 3524kb

input:

4466447004844686806

output:

2609442604

result:

ok single line: '2609442604'

Test #19:

score: 0

Accepted

time: 1ms

memory: 3452kb

input:

output:

result:

ok single line: '2'

Test #20:

score: 0

Accepted

time: 1ms

memory: 3472kb

input:

90074858599988014

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0

Accepted

time: 1ms

memory: 3520kb

input:

9498578088490196330623

output:

-1

result:

ok single line: '-1'

Test #22:

score: 0

Accepted

time: 1ms

memory: 3472kb

input:

output:

-1

result:

ok single line: '-1'

Test #23:

score: 0

Accepted

time: 1ms

memory: 3492kb

input:

8925123681749359895

output:

-1

result:

ok single line: '-1'

Test #24:

score: 0

Accepted

time: 1ms

memory: 3456kb

input:

output:

result:

ok single line: '3008'