実行時間制限: 6 sec / メモリ制限: 256 MB
この問題はリアクティブ形式の問題である. つまり,あなたは応答プログラムとあるゲームを行う.
あなたのプログラムは,はじめに,入力として2つの整数 N と D が与えられる. それにたいして,長さ N の 0/1 列を出力する. すると,応答プログラムは,2人の小人,京子さんと結衣さんをこの列の上のどこかに配置する.このときの京子さんの位置を i とし,結衣さんの位置をjとする. また、このとき京子さんと結衣さんは必ず D だけ離れている. (|i-j| = D である). あなたは常に2人の位置にある文字を知ることができる.
この条件の下で,あなたは応答プログラムと京子さんと結衣さんの位置関係を特定するゲームを行う.あなたは応答プログラムに命令を渡し,京子さんまたは結衣さんのどちらか一方を左右に1つずつ動かすことができる.2人の初期位置は列の端から十分遠く設定されるので、命令によって2人のどちらかが列の端から飛び出してしまう場合を考慮する必要はない.そして最後に2人の位置関係を特定し i < j または j < i なのかを応答プログラムに入力せよ.位置関係の入力は1回しか行えない.命令は位置関係の入力と合計で50回まで行える.
できるだけ少ない移動回数で i < j なのか j < iなのかを特定せよ.
入出力形式
まず入力が以下の形式で与えられる。
N D
Nはあなたが出力する 0/1 列の長さである. Dは初期状態での2人の間隔である.
これらの入力の後,あなたはまず長さNの0/1列を出力しなければならない. あなたのプログラムが0/1列を出力すると,次に2人の初期位置が応答プログラ ムによって決定され,京子さんの位置の文字と結衣さんの位置の文字とを入力で 受けとることができる.例えば C/C++ で長さ3の 0/1 列 "011" を出力する場 合は,
printf("011\n"); fflush(stdout);
とする. 次に
scanf("%d %d", &a, &b);
とすると変数aとbに京子さんの初期位置の文字と結衣さんの初期位置の文字が入る.
この後,あなたは京子さんまたは結衣さんを左または右に1つ,50回までなら何度でも動かすことができる. 2人を動かした後には,2人の位置の文字を入力として受けとることができる. 例えば,京子さんを右に動かす場合には,
printf(“Move(A,1)\n”); fflush(stdout);とする。 次に、
scanf(“%d %d”, &a, &b);とすると変数aとbに2人の位置の文字が入る。 また、結衣さんを左に動かす場合には、
printf(“Move(B,-1)\n”); fflush(stdout);とする。次に、
scanf(“%d %d”, &a, &b);とすれば変数aとbに2人の位置の文字が入る。
あなたが送ることのできる命令は次の6種類である.
命令 | 意味 |
---|---|
Move(A,1) | 京子を右に1つ動かす |
Move(A,-1) | 京子を左に1つ動かす |
Move(B,1) | 結衣を右に1つ動かす |
Move(B,-1) | 結衣を左に1つ動かす |
i<j | i < jであると確定する |
i>j | i > jであると確定する |
制約
- 10000 \leq N \leq 100000
- 1 \leq D \leq N-1
- 入力値はすべて整数である.
- 命令は位置関係の入力と合計で50回まで行える
- 2人の初期位置は列の端から十分遠く設定されるので、命令によって2人のどちらかが列の端から飛び出してしまう場合を考慮する必要はない
- この問題の時間制限は6秒に設定されているが、このうち最大2秒程度が応答プログラムが2人の初期位置を決めるために使われる
採点方式
この問題の得点は,テストデータにたいして,あなたの最大の命令回数をCとしたとき- C \leq 5 ならば 900点
- C \gt 5 ならば 900 / (C - 4) 点となる。
入出力例
説明 | プログラムの出力 | プログラムへの入力 |
---|---|---|
あなたが出力する0/1列の長さと2人の間隔が与えられる | 10000 100 | |
長さ10000の 0/1 列を出力する | 010101 … 010101 | |
京子さんと結衣さんの位置の文字が返される | 0 1 | |
京子さんを1つ右に動かす | Move(A,1) | |
京子さんと結衣さんの位置の文字が返される | 1 1 | |
結衣さんを1つ左に動かす | Move(B,-1) | |
京子さんと結衣さんの位置の文字が返される | 1 0 | |
京子さんの初期位置が結衣さんの初期位置より左にあったと確定する | i<j |