QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#640842#6257. Efficient Exchangechanuuu#WA 0ms3792kbC++17823b2024-10-14 16:28:032024-10-14 16:28:03

Judging History

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

  • [2024-10-14 16:28:03]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3792kb
  • [2024-10-14 16:28:03]
  • 提交

answer

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

ll dp[1010][2];
ll a[1010];
int chk[1010];
int n;

ll solve(int i, int k){
    if(dp[i][k] ^ -1) return dp[i][k];
    ll s = a[i];
    if(!chk[i]){
        if(k) dp[i][k] = 10 - s;
        else dp[i][k] = s;
        return dp[i][k];
    }

    if(k) {
        s = (10 - s) % 10;
        s--;
    }
    return dp[i][k] = min(solve(i + 1, k), solve(i + 1, k ^ 1) + 1) + s;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s; cin>>s;
    n = s.size();
    for(int i = 0; i < n; i++) a[i] = s[i] - '0';
    for(int i = 0; i < n; i++) for(int k = 0; k < 2; k++) dp[i][k] = -1;
    for(int k = n - 1; k >= 1; k--) if(a[k] || chk[k]) chk[k - 1] = 1;
    cout << min(solve(0, 0), solve(0, 1) + 1);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3572kb

input:

83

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3792kb

input:

13

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

0

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

12345678987654321

output:

42

result:

ok single line: '42'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

1

output:

1

result:

ok single line: '1'

Test #6:

score: -100
Wrong Answer
time: 0ms
memory: 3640kb

input:

108894478469214466804158556038509473912228070531930682335592810379690071992846446138400855834536144291684432969861435324866089578025171848195442401602361161260026599515983657327709498488895075795438278518721851530339458103065105649832422088699047412786278455363479689485262210227415931822805287251225...

output:

1856

result:

wrong answer 1st lines differ - expected: '1971', found: '1856'