PKU 3508 Hide That Number
http://poj.org/problem?id=3508
ある数字を以下のルールに従って暗号化する。
数字を10倍して、もとの数字とたす。足してできた数が元の数字と同じ桁になるように上位桁を削る。
こうして出来た暗号化された数字を復元するという問題。
11で割った余りで考えると削られた数字が分かるので、あとは11で割った値を出せばよい。
TLEが厳しく、C++でないと通りませんでした。
char ans[1000010]; int ansn; int main(){ int cc=0; string in; while(cin>>in){ if(in=="0")break; ansn=0; ++cc; printf("%d. ",cc); int sum=0; rep(i,SZ(in))sum=(sum*10+in[i]-'0')%11; if(sum){ reverse(ALL(in)); if(SZ(in)&1){ if(sum<10)in+=char(sum+'0'); else in+="01"; }else{ if(sum==1)in+="01"; else in+=char(11-sum+'0'); } ans[ansn++]=in[0]; int c=0; for(int i=0;i+2<SZ(in);i++){ int t=in[i+1]-ans[ansn-1]+c; c=0; if(t<0)t+=10,c=-1; ans[ansn++]=t+'0'; } if(ans[ansn-1]=='0')--ansn; rep(i,ansn)putchar(ans[ansn-i-1]); putchar('\n'); }else{ puts("IMPOSSIBLE"); } } }