QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#425724 | #2835. Number Theory | AFewSuns | WA | 16ms | 97588kb | C++20 | 2.5kb | 2024-05-30 16:14:47 | 2024-05-30 16:14:47 |
Judging History
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'