QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#425722 | #2835. Number Theory | AFewSuns | WA | 39ms | 97488kb | C++20 | 2.5kb | 2024-05-30 16:13:28 | 2024-05-30 16:13:28 |
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';
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: 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'