QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#425722#2835. Number TheoryAFewSunsWA 39ms97488kbC++202.5kb2024-05-30 16:13:282024-05-30 16:13:28

Judging History

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

  • [2024-05-30 16:13:28]
  • 评测
  • 测评结果:WA
  • 用时:39ms
  • 内存:97488kb
  • [2024-05-30 16:13:28]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 1e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
ll m,a[5050],f[2][5050][2],ans=inf;
ll g[6][2000020],O[6]={0,1,11,111,1111,11111},pw[11],lim=1000000;
char s[5050];
int main(){
	pw[0]=1;
	fr(i,1,10) pw[i]=pw[i-1]*10;
	fr(i,0,5) fr(j,0,2*lim) g[i][j]=inf;
	g[0][lim]=0;
	fr(i,1,5){
		fr(j,-lim,lim){
			if(g[i-1][j+lim]==inf) continue;
			fr(k,-10,10) if(-lim<=(j+k*O[i])&&(j+k*O[i])<=lim) g[i][j+k*O[i]+lim]=min(g[i][j+k*O[i]+lim],g[i-1][j+lim]+i*abs(k));
		}
	}
	while(~scanf("%s",s)){
		m=strlen(s)-1;
		fr(i,0,m) a[i]=s[m-i]-'0';
		ll lst=0;
		fr(i,0,m){
			ll x=9*a[i]+lst;
			a[i]=x%10;
			lst=x/10;
			if(lst) m=max(m,i+1);
		}
		if(m<5){
			ll n=0;
			fr(i,0,m) n+=a[i]*pw[i];
			n/=9;
			writeln(g[5][n+lim]);
			continue;
		}
		fr(i,0,1) fr(j,0,m+1) f[i][j][0]=f[i][j][1]=inf;
		f[(m+1)&1][0][0]=0;
		f[(m+1)&1][0][1]=m+1;
		pfr(i,m,6){
			ll o=i&1;
			fr(j,0,m+1) f[o][j][0]=f[o][j][1]=inf;
			fr(j,0,m+1){
				fr(k,0,1){
					if(f[o^1][j][k]==inf) continue;
					f[o][j+k][0]=min(f[o][j+k][0],f[o^1][j][k]+i*abs(a[i]-10*k));
					f[o][j+k][1]=min(f[o][j+k][1],f[o^1][j][k]+i*abs(a[i]-10*k+1));
				}
			}
		}
		ll n=0;
		fr(i,0,5) n+=a[i]*pw[i];
		fr(i,6,m) n+=a[i];
		fr(i,0,m+1) fr(j,0,1) ans=min(ans,f[0][i][j]+g[5][(n-j*999999-9*i)/9+lim]);
		writeln(ans);
	}
}

详细

Test #1:

score: 100
Accepted
time: 16ms
memory: 97336kb

input:

12
100
998244353

output:

3
5
76

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 39ms
memory: 97488kb

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:

29
39
39
39
39
39
22
39
39
39
39
39
21
30
21
21
21
21
21
21
21
21
21
21
21
35
21
21
21
21
21
21
21
14
21
21
21
21
21
21
21
21
21
21
21
21
21
21
21
18
21
21
21
21
21
34
6
21
35
21
21
21
36
21
21
21
21
21
21
21
21
21
41
21
21
21
21
21
39
21
21
21
32
21
21
21
35
21
22
21
21
21
21
21
21
15
21
33
21
21
2...

result:

wrong answer 2nd lines differ - expected: '36', found: '39'