3508 Hide That Number
問題概要
電話番号を次のように暗号化する。
電話番号を10倍した数字に元の数字を加える。できた数字の下から元の数字の桁数と同じだけの桁の数字を取る。
暗号化後の数が与えられたとき、元の電話番号を復元せよ。
どのような元の番号を暗号化しても与えられた文字列にはならないとき、IMPOSSIBLEを出力せよ。
電話番号の長さは1000000以下である。
解法
暗号化した後の数字の先頭に1〜10をつけたしてみて、それぞれ11で割り算して割り切れたものの商が正しい電話番号である。
筆算の割り算をしてやればよい。
先頭に付け足す数字は10もあることに注意する(例: 92→1012→12)
ソースコード
char in[1000001],out[1000001]; int main() { int n,m,r,T=0; while(gets(in),strcmp(in,"0")){ n=strlen(in); out[n]=0; for(int b=1;b<=10;b++){ r=b; rep(i,n){ r*=10; r+=in[i]-'0'; out[i]=r/11+'0'; r%=11; } if(r==0)goto END; } strcpy(out,"IMPOSSIBLE"); END:printf("%d. %s\n",++T,out); } return 0; }