Floating-Point Numbers

時間制限 : 8 sec, メモリ制限 : 262144 KB
英語版はこちら

浮動小数点数

この問題では,コンピュータ上で実数を表現するためのデータ表現形式である浮動小数点数形式を扱う.

指数表記は数を表記する方法の一つで,通常の十進記数法では表しにくい大きな数や小さな数によく用いる. 指数表記では任意の正の実数を m × 10e という形式で表せる. ここで,m (仮数部と呼ばれる) は 1 以上 10 未満の実数であり,e (指数部と呼ばれる) は整数である. 例えば,13.5 という数は 1.35×101 であるので, 仮数部が 1.35,指数部が 1 の指数表記で表せる.

コンピュータで数を扱うには二進数が便利なので,指数表記も 10 の代わりに 2 を基数とする二進指数表記を考える. 二進指数表記では任意の正の実数は m × 2e と表せる.基数が 2 なので,m は 2 未満に制限できる. 例えば,13.5 は 1.6875×23 なので,仮数部が 1.6875,指数部が 3 の二進指数表記で表せる. 仮数部は 1.6875 = 1 + 1/2 + 1/8 + 1/16 なのでこれを小数点以下も二進で表すと 1.10112 となる. 同様に指数部の 3 は 112 である.

浮動小数点数はこの二進指数表記を有限のビット列で表そうとするものである.ビット数の制限によって仮数部の精度が制約され,指数部の範囲が制約されるのはいたしかたないが,広い範囲の実数をある程度高い精度で近似することができる.

この問題では,実際に広く使われているものを簡素化した,1 以上の数だけを表せる 64 ビットの浮動小数点数表現を考える. ここでは最初の 12 ビットを指数部,残る 52 ビットを仮数部に用いる. 浮動小数点数の 64 ビットを b64...b1 と表すことにする. e を最初の 12 ビットを符号なし二進数と解釈した (b64...b53)2 とし, m を残る 52 ビットが表す二進小数に 1 を加えた (1.b52...b1)2 とする. このとき,この浮動小数点数は m × 2e を表す.

以下に 13.5 を上述のフォーマットで表現するビット列を示す.

浮動小数点数の加算操作では,結果を浮動小数点数として表現できる数で近似しなければならない. ここでは近似は切捨てによるものとする.ふたつの浮動小数点数 ab の和が二進指数表記で a + b = m × 2e (1 ≤ m < 2, 0 ≤ e < 212) と表されるとき,両者の浮動小数点加算操作の結果である浮動小数点数は,12 ビットが e を符号なし二進数で表したもの,残る 52 ビットは m の二進小数部の最初の 52 ビットになる.

この近似手法の欠点として,誤差がすぐ蓄積してしまうことがある. このことを確認するため,ある浮動小数点数を何度も加算する,以下の擬似コードで表される実験をしてみよう. ここで,sa も共に浮動小数点数であり,個々の加算の結果は前述の方法によって近似するものとする.

s := a
for n times {
    s := s + a
}

浮動小数点数 a と繰り返し回数 n が与えられたときこの擬似コードを実行した後の浮動小数点数 s の各ビットを求めよ.

Input

入力は 1000 個以下のデータセットからなる. 各データセットは次の形式で表される.

n
b52...b1

n は繰り返し回数 (1 ≤ n ≤ 1018) を表す. 各 i について,bi は 0 か 1 である. 擬似コード中の浮動小数点数 a は指数部が 0 で,仮数部のビット列が b52...b1 であるようなものとする.

入力の終わりは,ゼロだけからなる行で表される.

Output

各データセットについて,擬似コード実行後の浮動小数点数 s の 64 ビットを 64 個の 0 または 1 の数字の並びとして 1 行に出力せよ.

Sample Input

1
0000000000000000000000000000000000000000000000000000
2
0000000000000000000000000000000000000000000000000000
3
0000000000000000000000000000000000000000000000000000
4
0000000000000000000000000000000000000000000000000000
7
1101000000000000000000000000000000000000000000000000
100
1100011010100001100111100101000111001001111100101011
123456789
1010101010101010101010101010101010101010101010101010
1000000000000000000
1111111111111111111111111111111111111111111111111111
0

Output for the Sample Input

0000000000010000000000000000000000000000000000000000000000000000
0000000000011000000000000000000000000000000000000000000000000000
0000000000100000000000000000000000000000000000000000000000000000
0000000000100100000000000000000000000000000000000000000000000000
0000000000111101000000000000000000000000000000000000000000000000
0000000001110110011010111011100001101110110010001001010101111111
0000000110111000100001110101011001000111100001010011110101011000
0000001101010000000000000000000000000000000000000000000000000000

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Yokohama, Japan, 2018-07-6
https://icpc.iisf.or.jp/2018-yokohama/