Codeforces 132 A. Turing Tape
問題
整数の配列に対して以下の操作をする。
- 直前に出力した文字のASCIIコードの8ビットを反転(逆から読む)させる
- 上の結果(0文字目の場合は0とする)からi番目の配列の値をmod 256で引く
- 再び8ビットを反転(逆から読む)させて、そのASCIIコードをもつ文字を出力する
を配列の全ての要素に対して繰り返す。
このときに出力される文字列が与えられるので、
それを出力するような元の整数の配列を求めよ。
制約条件
文字列の長さ≦100
文字列のASCIIコードは32以上126以下
方針
文字列i文字目をstr[i]とする。
すると、配列のi番目をa[i]とすると、上の定義より
str[i]=rev((rev(str[i-1])-a[i]+256)%256)
⇔rev(str[i])=(rev(str[i-1])-a[i]+256)%256
⇔a[i]=(rev(str[i-1])-rev(str[i])+256)%256
となることがわかる。
ソースコード
int rev(int a){ int d[8]={},res=0; rep(i,8)d[i]=a>>i&1; rep(i,8)res*=2, res+=d[i]; return res; } void run() { string in; getline(cin,in); int res[101]={}; rep(i,in.size()){ res[i]=(rev(i?in[i-1]:0)-rev(in[i])+256)%256; cout<<res[i]<<endl; } }