시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB43141333.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)
    • このルーチンは,最初に 1 回だけ呼び出される.引数 T は,小課題の番号 T である.引数 X は,Aさんが B さんに伝えるべき正の整数 X である.
  • int GameA(int I, int J)
    • このルーチンは,A さんが K 理事長の部屋に来ることに対応して呼び出される.引数 I, J は,A さんが K 理事長の部屋に来たときに駒があるマスを表す整数の組 (I, J) である.1 ≤ I ≤ 4 および 1 ≤ J ≤ 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 ≤ I ≤ 4 および 1 ≤ J ≤ 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 回より多く呼び出されることはない.また,GameAGameB が合計 10 000 回呼び出された段階で GameB が正の整数を返していない場合は,不正解 [6] と判定され,プログラムの実行は終了される.

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

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

입력

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

  • 1 行目には整数 T, X, I0, J0 が空白を区切りとして書かれており,小課題の番号が T,A さんが B さん に伝えるべき整数が X,ゲームの開始時の駒の位置が (I0, J0) であることを表す.
  • 2 行目には 2 種類の文字 A, B からなる,長さがちょうど 10 000 の文字列が書かれており,k 文字目 (1 ≤ k ≤ 10 000) が A または B である場合,ルーチン InitAInitB が呼び出された後に k 番目に呼 び出されるルーチンがそれぞれ GameA または GameB であることを表す.

출력

プログラムの実行が正常に終了した場合,採点プログラムのサンプルは標準出力へ以下の情報を 1 行で 出力する.

  • 正解の場合,“Accepted” と出力される (引用符は実際には出力されない.以下同様である).
  • 不正解の場合,不正解の種類が「実装の詳細」の節に書かれた番号によって “Wrong Answer [1]” の ように出力される.さらに,不正解 [5] については,正しい X の値およびルーチン GameB が返した 正の整数 Y の値が “Wrong Answer [5] : X = 2, Y = 3” のように出力される.

제한

  • 1 ≤ X ≤ 1 000 000 000.

서브태스크 1 (20점)

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

서브태스크 2 (20점)

  • T = 2 を満たす.
  • ゲームの開始時の駒の位置は (I0, J0) = (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

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

첨부

제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

채점 및 기타 정보

  • 예제는 채점하지 않는다.