QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#105608 | #6300. Best Carry Player 2 | LYC_music# | WA | 2ms | 3284kb | C++14 | 1.4kb | 2023-05-14 15:27:57 | 2023-05-14 15:28:01 |
Judging History
answer
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll unsigned long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define mod 998244353
#define int ll
//#define N
using namespace std;
int x,k;
int dp[20][20][2];
int inf;
void chk(int &x,int y)
{
x=min(x,y);
}
void BellaKira()
{
cin>>x>>k;
inf=-1;
for (int i=0;i<=18;i++)
for (int j=0;j<=18;j++)
dp[i][j][0]=dp[i][j][1]=inf;
dp[0][0][0]=0;
if (k==0)
{
int ans=1;
while (x%10==9)
{
x/=10;
ans*=10;
}
cout<<ans<<'\n';
return;
}
for (int i=1,coef=1;i<=18;i++,coef=coef*10)
{
int nx=x%10;
x/=10;
for (int j=0;j<=18;j++)
for (int k=0;k<=1;k++)
if (dp[i-1][j][k]!=inf)
{
int now=nx+k;
if (now==10)
{
chk(dp[i][j+1][1],dp[i-1][j][k]);
// if (i==10&&j==5)
// {
// cout<<"??"<<dp[i][j+1][1]<<'\n';
// cout<<dp[i-1][j][k]<<"........."<<'\n';
// }
} else
{
chk(dp[i][j][0],dp[i-1][j][k]);
if (now!=0)
chk(dp[i][j+1][1],dp[i-1][j][k]+coef*(10-now));
}
}
}
int ans=min(dp[18][k][0],dp[18][k][1]);
if (ans==inf) cout<<"-1\n";
else cout<<ans<<'\n';
}
signed main()
{
IOS;
cin.tie(0);
int T=1;
cin>>T;
while (T--)
{
BellaKira();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3236kb
input:
4 12345678 0 12345678 5 12345678 18 990099 5
output:
1 54322 999999999987654322 9910
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3284kb
input:
21 999990000099999 0 999990000099999 1 999990000099999 2 999990000099999 3 999990000099999 4 999990000099999 5 999990000099999 6 999990000099999 7 999990000099999 8 999990000099999 9 999990000099999 10 999990000099999 11 999990000099999 12 999990000099999 13 999990000099999 14 999990000099999 15 999...
output:
100000 10000 1000 100 10 1 900001 9900001 99900001 999900001 10000000001 9999910000 9999901000 9999900100 9999900010 9999900001 9000009999900001 99000009999900001 999000009999900001 -1 1000000000000000000
result:
wrong answer 20th lines differ - expected: '99999999999999999900000000000000000', found: '-1'