Computer Transformation(0)
0,1の2値表現を持つコンピュータが、以下のような文字列を生成する
このとき、文字列内に2文字隣接した「0」が何組あるかを答える問題だ。
①1からスタートし
②0は10に、1は01に置き換える
③入力値をNとすれば、②の操作をN回繰り返す
たとえば、N=3とすると、
のように3ステップで「01101001」という文字列が生成される。
0: 1
1: 01
2: 1001
3: 01101001
この中に「00」と隣り合った0が現れるのは1箇所なので答えは1だ。
N=5なら、
で、5箇所に「00」が現れるから、答えは5。
0: 1
1: 01
2: 1001
3: 01101001
4: 1001011001101001
5: 01101001100101101001011001101001
文字列の長さは2^Nなので、Nの値が1増えると答えはおよそ2倍になるのではないかという予測は出来る。ということは、この問題のインプット最大値が気になる。問題には
とあるので、出力する10進数の最大値は2^1000まで。多倍長の演算が必要になる。この場合は当然Javaで書いたほうが短くなるが、CでどこまでJavaの最短コードに近づくことが出来るのかチャレンジしたい。
Input
Every input line contains one natural number n (0 < n <= 1000).
