QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#105608#6300. Best Carry Player 2LYC_music#WA 2ms3284kbC++141.4kb2023-05-14 15:27:572023-05-14 15:28:01

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-14 15:28:01]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3284kb
  • [2023-05-14 15:27:57]
  • 提交

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'