Day 1 Task 2: 熱い, 冷たい(Hotter Colder)
ジャックとジルは 熱い，冷たい (Hotter, Colder) というゲームで遊んでいる．
ジルは 1 以上 N 以下の 1 つの数を持つ．
ジャックはその数が何であるかを推測することを繰り返す．
ジャックの推測は 1 以上 N 以下の数である．
それぞれの推測に対して，ジルは，熱い (hotter)，冷たい (colder), 同じ (same) のいずれかの返事をする．
ジャックの最初の推測に対しては，ジルは同じ (same) を返す．
残りの推測に対しては，ジルは：
- もし推測が前回の推測よりもジルの数に近いなら，
熱い (hotter) と答える．
- もし推測が前回の推測よりもジルの数から離れているなら，
冷たい (colder) と答える．
- もし推測が前回の推測よりもジルの数に近くなく，
離れてもいないなら，同じ (same) と答える．
ジャックの役割を演じるプロシージャー HC(N) を実装せよ．
実装では Guess(G) を繰り返し呼び出すことができる．
G は 1 以上 N 以下の数である．
Guess(G) は 熱い (hotter) を表す 1 か 冷たい (colder) を表す -1 か 同じ (same) を表す 0 のいずれかを返す．
HC(N) はジルの数を返す必要がある．
例
例えば， N = 5 とし，ジルが数 2 を選んだと仮定する．
プロシージャー HC が以下に示す Guess の呼び出しを行ったとすると，
2 列目の結果が返される．
| 呼び出し(Call) | 返り値(Returned value) | 説明(Explanation)
|
|---|
| Guess(5) | 0 | 同じ (Same) (最初の呼び出し)
|
| Guess(3) | 1 | 熱い (Hotter)
|
| Guess(4) | -1 | 冷たい (Colder)
|
| Guess(1) | 1 | 熱い (Hotter)
|
| Guess(3) | 0 | 同じ (Same)
|
この時点でジャックは答えを知っており，
HC は 2 を返す必要がある．
ジャックがジルの数を決めるのに 5 回の推測が必要であった．
もっと良い方法もある．
小課題 1 [25点]
HC(N) が Guess(G) を呼び出す回数は 500 回以下である．
HC(N) が呼び出される回数は 125 250 回以下である．
N は 1 以上 500 以下である．
小課題 2 [25点]
HC(N) が Guess(G) を呼び出す回数は 18 回以下である．
HC(N) が呼び出される回数は 125 250 回以下である．
N は 1 以上 500 以下である．
小課題 3 [25点]
HC(N) が Guess(G) を呼び出す回数は 16 回以下である．
HC(N) が呼び出される回数は 125 250 回以下である．
N は 1 以上 500 以下である．
小課題 4 [最高25点]
W を 2W≤3N をみたす最大の整数とする．この小課題におけるあなたの得点は次の通り．
- HC(N) が Guess(G) を 2W 回以上呼び出していれば 0 点．
- α を 0<α<1 かつ HC(N) が Guess(G) を呼び出す回数が 2W-αW 回以下となる最大の実数とすると， 25α 点が得られる．
- HC(N) が Guess(G) を呼び出す回数が W 回以下であれば 25 点．
HC(N) が呼び出される回数は 1 000 000 回以下である．
N は 1 以上 500 000 000 以下である．
HCが呼ばれるごとに，そこで使われる変数を必ず初期化すること．
実装の詳細
- プログラムの作成とテストのためにはRunC 環境を利用せよ．
- 実装フォルダー (Implementation folder): /home/ioi2010-contestant/hottercolder/ (プロトタイプ : hottercolder.zip)
- 選手が実装するファイル: hottercolder.c または hottercolder.cpp または hottercolder.pas
- 提出ファイルのインターフェース (Contestant interface): hottercolder.h または hottercolder.pas
- 採点プログラムのインターフェース (Grader interface): grader.h または graderlib.pas
- 採点プログラムのサンプル (Sample grader): grader.c または grader.cpp または grader.pas と graderlib.pas
- 採点プログラムの入力のサンプル (Sample grader input): grader.in.1 grader.in.2.
注意: 入力ファイルはいくつかの行からなる．各行は N とジルの数を含む．
- 採点プログラムの入力のサンプルに対して，期待される出力: 採点プログラムは grader.out.1 grader.out.2 等のファイルを作成する．
- もし，小課題 1 が正しく実装されていれば，出力は OK 1 と書かれた行を含む．
- もし，小課題 2 が正しく実装されていれば，出力は OK 2 と書かれた行を含む．
- もし，小課題 3 が正しく実装されていれば，出力は OK 3 と書かれた行を含む．
- もし，小課題 4 が正しく実装されていれば，出力は OK 4 alpha α を含む．
- コンパイルと実行 (コマンドライン): runc grader.c または runc grader.cpp または runc grader.pas
- コンパイルと実行 (gedit プラグイン): 実装ファイルを編集中に Ctrl-R
- 提出 (コマンドライン): submit grader.c または submit grader.cpp または submit grader.pas
- 提出 (gedit プラグイン): 実装ファイルまたは採点プログラムのファイルを編集中に Ctrl-J