QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#770675#2835. Number TheoryS00021TL 92ms395448kbC++141.3kb2024-11-21 23:15:122024-11-21 23:15:12

Judging History

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

  • [2024-11-21 23:15:12]
  • 评测
  • 测评结果:TL
  • 用时:92ms
  • 内存:395448kb
  • [2024-11-21 23:15:12]
  • 提交

answer

#include<bits/stdc++.h>
#define N 5005
#define pb push_back
#define fi first
#define INF 0x3f3f3f3f
#define se second
#define pii pair<int,int>
#define MP make_pair
using namespace std; const int B=5000;
int dp[N][N*2][2],a[N],c[N],n,T; char s[N];
bool chk(int x){ if(c[x+1]) return 1;
	for(int i=x;i;i--) if(c[i]!=1) return c[i]>1;
	return 1;
}int dfs(int x,int y,int z){
	if(x==1) return abs(y-z*10);
	if(abs(y)>5000) return INF;
	if(~dp[x][y+B][z]) return dp[x][y+B][z];
	int &ans=dp[x][y+B][z],w=a[x]-z*10; ans=INF;
	if(x>5) for(int i=0;i<=1;i++) ans=min(ans,dfs(x-1,y-i,i)+abs(i+w)*x);
	else{ int ww=(powl(10,x)-1)/9;
		for(int i=0;i<=1;i++){
			if(y>0) for(int j=0;j<=abs(y)/ww+1;j++) ans=min(ans,dfs(x-1,y-i-j*ww,i)+abs(i+w+j)*x);
			else for(int j=0;j<=abs(y)/ww+1;j++) ans=min(ans,dfs(x-1,y-i+j*ww,i)+abs(i+w-j)*x);
		}
	}return ans;
}void slv(){
	n=strlen(s+1); reverse(s+1,s+n+1);
	memset(dp,-1,sizeof(dp)),memset(a,0,sizeof(a)),memset(c,0,sizeof(c));
	for(int i=1;i<=n;i++) c[i]=s[i]-'0';
	for(int i=n;i;i--){
		while(chk(i)){
			int t=min(max(c[i+1]*10+c[i]-1,1),9);
			for(int j=1;j<=i;j++){
				c[j]-=t; if(c[j]<0) c[j]+=10,c[j+1]--; 
			}a[i]+=t; }
	}printf("%d\n",dfs(n+1,a[1],0));
}signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	while(~scanf("%s",s+1)) slv();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 92ms
memory: 395448kb

input:

12
100
998244353

output:

3
5
76

result:

ok 3 lines

Test #2:

score: -100
Time Limit Exceeded

input:

4296
5370
8014
9532
6311
4070
2541
4782
5630
1487
2916
454
2020
5650
1851
5885
3556
6533
5044
1780
5746
5605
7860
4416
4495
8081
2416
3534
6045
3348
4536
8725
3505
1074
1531
937
7954
4451
7052
9586
3468
2679
6085
9908
3630
8046
6282
2883
9021
1436
5201
8166
8986
2167
7780
4156
101
3753
5732
5173
118...

output:


result: