시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 43 | 14 | 13 | 33.333% |
国際情報オリンピックの日本代表に選ばれた A さんと B さんは,情報処理技術を高めるため,情報オリ ンピック日本委員会の K 理事長と「メッセンジャー・ゲーム」を行うことになった.以下にこのゲームの ルールを説明する.
A さんと B さんは,図のように部屋に隔離されている.A さん・B さん・K 理事長の各部屋には内線電 話が設置されているが,電話を発信することが可能なのは K 理事長のみである.その他の連絡手段は断た れており,A さんと B さんは指示がない限り部屋から出ることはできない.
ゲームの開始時に,K 理事長は電話で A さんにある正の整数 X を伝える.ゲームの目的は,A さんと B さんが直接の連絡をとらずに,A さんが B さんに X の値を正しく伝えることである.
K 理事長の部屋には 4×4 のマス目がある.i 行 j 列のマスを (i, j) と表す (1 5 i 5 4, 1 5 j 5 4).マス (1, 1)が左上の隅,マス (1, 4) が右上の隅,マス (4, 1) が左下の隅,マス (4, 4) が右下の隅である.ゲームの開始時,1 つの駒がいずれかのマスに置かれる.以後,K 理事長は駒が置かれているマスを変えることはない.
これから,K 理事長が A さんまたは B さんを電話で部屋に呼ぶということが繰り返される.A さんまたは B さんは,K 理事長の部屋に来るたびに,駒を上下左右のいずれかのマスに動かさなければならない.駒を動かしたら,A さんまたは B さんは自分の部屋に戻る.B さんは,K 理事長の部屋に来たときにもしX の値がわかったならば,駒を動かす代わりにそれを K 理事長に答えることができる.正しい X の値を答えられれば正解であり,そうでなければ不正解である.
K 理事長が A さんまたは B さんを部屋に呼ぶタイミングは不規則であり,A さんと B さんは K 理事長がどういう順序で 2 人を部屋に呼んでいるかはわからない.ただし,K 理事長は 2 人を部屋に呼ぶ順序をゲームの開始時に決めており,また,K 理事長が A さんまたは B さんの一方を 100 回より多く連続して部屋に呼ぶことはないことが保証されている.K 理事長が A さんと B さんを合計 10 000 回部屋に呼んだ後に A さんまたは B さんが自分の部屋に戻った段階で B さんが X の値を答えていない場合は,不正解としてゲームは終了される.
A さんと B さんの戦略を実装し,上で説明された「メッセンジャー・ゲーム」で正解できるプログラム を作成せよ.
あなたは同じプログラミング言語で 2 つのファイルを提出しなければならない.
1 つ目のファイルは playerA.c
または playerA.cpp
という名前である.このファイルは A さんの戦略を実装したファイルであり,以下のルーチンを実装していなければならない.
void InitA(int T, int X)
T
は,小課題の番号 T である.引数 X
は,Aさんが B さんに伝えるべき正の整数 X である.int GameA(int I, int J)
I
, J
は,A さんが K 理事長の部屋に来たときに駒があるマスを表す整数の組 (I, J) である.1 ≤ I ≤ 4 および 1 ≤ J ≤ 4を満たす.2 つ目のファイルは playerB.c
または playerB.cpp
という名前である.このファイルは B さんの戦略を実装したファイルであり,以下のルーチンを実装していなければならない.
void InitB(int T)
T
は,小課題の番号 T である.int GameB(int I, int J)
I
, J
は,B さんが K 理事長の部屋に来たときに駒があるマスを表す整数の組 (I, J) である.1 ≤ I ≤ 4 および 1 ≤ J ≤ 4を満たす.ルーチン GameA
および GameB
は,一方が連続して 100 回より多く呼び出されることはない.また,GameA
と GameB
が合計 10 000 回呼び出された段階で GameB
が正の整数を返していない場合は,不正解 [6] と判定され,プログラムの実行は終了される.
内部での使用のために他のルーチンを実装したり,グローバル変数を宣言したりするのは自由である.ただし,提出された 2 つのプログラムは,採点プログラムとまとめてリンクされて 1 つの実行ファイルになるので,各ファイル内のすべてのグローバル変数と内部ルーチンを static
で宣言して,他のファイルとの干渉を避ける必要がある.採点時には,このプログラムは A さん側,B さん側として 2 個のプロセスとして実行されるので,A さん側と B さん側でプログラム中のグローバル変数を共有することはできない.
あなたの提出は標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.
採点プログラムのサンプルは標準入力から以下の入力を読み込む.
A
, B
からなる,長さがちょうど 10 000 の文字列が書かれており,k 文字目 (1 ≤ k ≤ 10 000) が A
または B
である場合,ルーチン InitA
と InitB
が呼び出された後に k 番目に呼 び出されるルーチンがそれぞれ GameA
または GameB であることを表す.プログラムの実行が正常に終了した場合,採点プログラムのサンプルは標準出力へ以下の情報を 1 行で 出力する.
Accepted
” と出力される (引用符は実際には出力されない.以下同様である).Wrong Answer [1]
” の ように出力される.さらに,不正解 [5] については,正しい X の値およびルーチン GameB
が返した 正の整数 Y の値が “Wrong Answer [5] : X = 2, Y = 3
” のように出力される.InitA
および InitB
が呼び出された後に,GameA
, GameB
, GameA
, GameB
, . . . という順でルーチンが呼び出される.InitA
および InitB
が呼 び出された後に,まずルーチン GameA
または GameB
が,I = 1, J = 1 を引数として呼び出される.採点プログラムのサンプルが読み込む入力の例と,それに対応するルーチンの呼び出しの例を以下に示す.
入力 |
---|
2 6 1 1 ABBAABAAABBBBBABBAABBBABBBBAAAAABABAABAABBBBABAAAA (以下省略) |
A さん側 | B さん側 | ||
---|---|---|---|
呼び出し | 返り値 | 呼び出し | 返り値 |
InitA(2, 6) |
なし | ||
InitB(2) |
なし | ||
GameA(1, 1) |
-2 | ||
GameB(2, 1) |
-4 | ||
GameB(2, 2) |
-2 | ||
GameA(3, 2) |
-3 | ||
GameA(3, 1) |
-1 | ||
GameB(2, 1) |
6 |
この例は,必ずしも意味のあるやりとりを記述しているとは限らないことに注意せよ.
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)