QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#425724#2835. Number TheoryAFewSunsWA 16ms97588kbC++202.5kb2024-05-30 16:14:472024-05-30 16:14:47

Judging History

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

  • [2024-05-30 16:14:47]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:97588kb
  • [2024-05-30 16:14:47]
  • 提交

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';
		a[m+1]=a[m+2]=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);
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 97464kb

input:

12
100
998244353

output:

3
5
76

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 15ms
memory: 97548kb

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
36
28
27
35
36
22
30
32
22
33
15
20
30
28
32
19
29
40
22
34
34
30
26
30
35
24
23
42
18
26
28
31
14
22
22
33
22
43
30
21
24
42
19
30
33
43
30
21
18
34
36
21
18
19
34
6
30
35
42
14
27
36
32
23
25
30
35
28
22
32
27
41
39
26
37
30
28
39
35
22
24
32
44
35
36
35
42
22
22
31
35
25
32
32
15
17
33
38
31
2...

result:

ok 9999 lines

Test #3:

score: -100
Wrong Answer
time: 16ms
memory: 97588kb

input:

16528
11452
14198
11877
11309
14176
10807
19189
12063
11011
11618
18292
19862
13144
16834
16652
14120
17091
19836
16498
17655
19144
14088
13370
12709
17115
14482
10958
12306
17891
17979
10705
10036
17976
12035
18042
17495
14498
10163
15926
12209
18908
13033
19875
11699
14361
14785
14253
12647
14726
...

output:

37
19
19
19
17
17
24
17
17
10
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
17
18
17
17
17
28
18
17
17
17
17
17
25
17
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
19
24
13
13
20
20
27
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
12
21
10
10
10
...

result:

wrong answer 3rd lines differ - expected: '29', found: '19'