1 - メッセンジャー (Messenger) Editorial /

Time Limit: 0 msec / Memory Limit: 256 MiB

AtCoder での提出方法

配布ファイル

  • 現在この問題には提出できません.他のオンラインジャッジに提出することを検討してください.
    This problem is unavailable now. Please try to submit to other online judges.
  • AtCoder では,提出する場合はすべての関数を 1 つのソースコードに記述して提出してください.

配点 : 100 点

問題文

国際情報オリンピックの日本代表に選ばれた A さんと B さんは,情報処理技術を高めるため,情報オリンピック日本委員会の K 理事長と「メッセンジャー・ゲーム」を行うことになった.以下にこのゲームのルールを説明する.

A さんと B さんは,図のように部屋に隔離されている.A さん・B さん・K 理事長の各部屋には内線電話が設置されているが,電話を発信することが可能なのは K 理事長のみである.その他の連絡手段は断たれており,A さんと B さんは指示がない限り部屋から出ることはできない.

図

ゲームの開始時に,K 理事長は電話で A さんにある正の整数 X を伝える.ゲームの目的は,A さんと B さんが直接の連絡をとらずに,A さんが B さんに X の値を正しく伝えることである.

K 理事長の部屋には 4\times 4 のマス目がある.i 行 j 列のマスを (i, j) と表す (1 \leqq i \leqq 4,1 \leqq j \leqq 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)

    このルーチンは,最初に 1 回だけ呼び出される.引数 T は,小課題の番号 T である.引数 X は,A さんが B さんに伝えるべき正の整数 X である.

  • int GameA(int I, int J)

    このルーチンは,A さんが K 理事長の部屋に来ることに対応して呼び出される.引数 I, J は,A さんが K 理事長の部屋に来たときに駒があるマスを表す整数の組 (I, J) である.1 \leqq I \leqq 4 および 1 \leqq J \leqq 4 を満たす.

    このルーチンは整数 -1, -2, -3, -4 のいずれかを返さなければならない.それ以外の値を返した場合は,不正解 [1] と判定され,プログラムの実行は終了される.これらは A さんが以下の行動を行うことを表す.

    • -1:駒を上のマス (I - 1, J) に動かす.
    • -2:駒を下のマス (I + 1, J) に動かす.
    • -3:駒を左のマス (I, J - 1) に動かす.
    • -4:駒を右のマス (I, J + 1) に動かす.

    駒が盤の外に出るような動きを指定した場合は,不正解 [2] と判定され,プログラムの実行は終了される.

2 つ目のファイルは playerB.c または playerB.cpp という名前である.このファイルは B さんの戦略を実装したファイルであり,以下のルーチンを実装していなければならない.

  • void InitB(int T)

    このルーチンは,最初に 1 回だけ呼び出される.引数 T は,小課題の番号 T である.

  • int GameB(int I, int J)

    このルーチンは,B さんが K 理事長の部屋に来ることに対応して呼び出される.引数 I, J は,B さんが K 理事長の部屋に来たときに駒があるマスを表す整数の組 (I, J) である.1 \leqq I \leqq 4 および 1 \leqq J \leqq 4 を満たす.

    このルーチンは整数 -1, -2, -3, -4 のいずれか,または正の整数 Y を返さなければならない.それ以外の値を返した場合は,不正解 [3] と判定され,プログラムの実行は終了される.これらは B さんが以下の行動を行うことを表す.

    • -1:駒を上のマス (I - 1, J) に動かす.
    • -2:駒を下のマス (I + 1, J) に動かす.
    • -3:駒を左のマス (I, J - 1) に動かす.
    • -4:駒を右のマス (I, J + 1) に動かす.

    駒が盤の外に出るような動きを指定した場合は,不正解 [4] と判定され,プログラムの実行は終了される.

    • 正の整数 Y:K 理事長に,X の値は Y である,と答える.このとき,X = Y であれば正解,そうでなければ不正解 [5] と判定され,プログラムの実行は終了される.

ルーチン GameA および GameB は,一方が連続して 100 回より多く呼び出されることはない.また,GameA と GameB が合計 10\,000 回呼び出された段階で GameB が正の整数を返していない場合は,不正解 [6] と判定され,プログラムの実行は終了される.

内部での使用のために他のルーチンを実装したり,グローバル変数を宣言したりするのは自由である.ただし,提出された 2 つのプログラムは,採点プログラムとまとめてリンクされて 1 つの実行ファイルになるので,各ファイル内のすべてのグローバル変数と内部ルーチンを static で宣言して,他のファイルとの干渉を避ける必要がある.採点時には,このプログラムは A さん側,B さん側として 2 個のプロセスとして実行されるので,A さん側と B さん側でプログラム中のグローバル変数を共有することはできない.

あなたの提出は標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.

コンパイル・実行の方法

作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウンロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルのサンプルも含まれている.

採点プログラムのサンプルは 1 つのファイルからなる.そのファイルは grader.c または grader.cpp である.作成したプログラムをテストするには,次のようにコマンドを実行する.

  • C の場合
gcc -O2 -lm grader.c playerA.c playerB.c -o grader
  • C++ の場合
g++ -O2 -lm grader.cpp playerA.cpp playerB.cpp -o grader

コンパイルが成功すれば,grader という実行ファイルが生成される.

実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラムのサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出力に結果を出力する.

入力

採点プログラムのサンプルは標準入力から以下の入力を読み込む.

  • 1 行目には整数 T, X, I_{0}, J_{0} が空白を区切りとして書かれており,小課題の番号が T,A さんが B さんに伝えるべき整数が X,ゲームの開始時の駒の位置が (I_{0}, J_{0}) であることを表す.
  • 2 行目には 2 種類の文字 A, B からなる,長さがちょうど 10\,000 の文字列が書かれており,k 文字目 (1 \leqq k \leqq 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” のように出力される.

制約

すべての入力データは以下の条件を満たす.

  • 1 \leqq X \leqq 1\,000\,000\,000.

小課題

小課題 1 [20 点]

  • T = 1 を満たす.
  • 最初に K 理事長の部屋に呼ばれるのは A さんであり,A さんと B さんは交互に K 理事長の部屋に呼ばれる.すなわち,ルーチン InitA および InitB が呼び出された後に,GameA, GameB, GameA, GameB, \ldots という順でルーチンが呼び出される.

小課題 2 [20 点]

  • T = 2 を満たす.
  • ゲームの開始時の駒の位置は (I_{0}, J_{0}) = (1, 1) である.すなわち,ルーチン InitA および InitB が呼び出された後に,まずルーチン GameA または GameB が,I = 1,J = 1 を引数として呼び出される.

小課題 3 [60 点]

  • T = 3 を満たす.

やりとりの例

採点プログラムのサンプルが読み込む入力の例と,それに対応するルーチンの呼び出しの例を以下に示す.

入力

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

この例は,必ずしも意味のあるやりとりを記述しているとは限らないことに注意せよ.


Source Name

JOI 2012/2013 春季トレーニング合宿 Contest Day4