2001 - 数当てゲームをするKamba君

問題

Kamba君は、友達のGettan君と数当てゲームをしています。Kamba君は回答者で、Gettan君が出題者です。ゲームのルールは「※制約・ルール」に従います。そこで、整数 $N$ が与えられたとき、Kamba君が二分探索アルゴリズムを用いて必ず勝てる方法を教えてあげてください。具体的には、各質問で使用する数値 $T_1, T_2, ... , T_i$ を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$

1行目に整数$N$が与えられる。

出力

$T_i$ の出力は改行区切りで行い、出力の最後に改行を入れること。

※制約・ルール

全ての入出力ケースについて以下を満たす。

• $0 \leq N \leq 7.4 \times 10^9$
• $N$ は Kamba君が当てるべき数字を表します。
• 質問回数は最大で $33$ 回までとする。
• 質問は「その値は $T_i$ 以下ですか？」のみ許される。（この質問通りになるように $middle$ を合わせましょう。）


問題のヒント（ここをクリック）

今回の問題を解くことができる二分探索アルゴリズムの実装方法
なお二部探索にはいろいろな手法がありますが今回はこの手法でしかできません
1. 初期値は $left = 0, right = 7.4 \times 10^9$
2. 真ん中の値は $left + ( right - left ) ÷ 2$ で求められます。
3. $N$ が真ん中の値以下だった場合は、上限を真ん中の値にします。逆に、 $N$ が真ん中の値より大きかった場合は、真ん中の値 $+ 1$ にします。
4. これを繰り返します。

入出力例

入力例1

4

出力例1

3700000000
1850000000
925000000
462500000
231250000
115625000
57812500
28906250
14453125
7226562
3613281
1806640
903320
451660
225830
112915
56457
28228
14114
7057
3528
1764
882
441
220
110
55
27
13
6
3
5
4

よく分からない方や、答えがずれている方は ※制約・ルール にあるヒントを見てください。

入力例2

20250704

出力例2

3700000000
1850000000
925000000
462500000
231250000
115625000
57812500
28906250
14453125
21679688
18066407
19873048
20776368
20324708
20098878
20211793
20268251
20240022
20254137
20247080
20250609
20252373
20251491
20251050
20250830
20250720
20250665
20250693
20250707
20250700
20250704
20250702
20250703