#2211. Memory2
Memory2
Memory2
题目描述
Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 1 – Memory2 神経衰弱(Memory2) 表に0 以上N −1 以下の整数が1 つ書かれたカードが2 枚ずつある.あなたとJOI 君は,これら2N 枚 のカードを用いて神経衰弱というゲームの練習をしている. ゲームの練習を始める時点では,カードは裏向きの状態でテーブルに横一列に並べられている.左から i + 1 枚目(0 ≦i ≦2N −1) のカードを,カードi と呼ぶ.カードi の表に書かれた整数をAi (0 ≦i ≦2N −1) とする.最初,JOI 君とあなたには,Ai (0 ≦i ≦2N −1) がどのような値であるかは分からない. あなたとJOI 君は,以下のやりとりをK 回まで繰り返すことができる.
- あなたは,2N 枚のカードのうちの2 枚のカードを指定する.
- JOI 君は,指定された2 枚のカードをめくり,表に書かれた整数をあなたに見えないようにこっそり 見る.もし,2 枚のカードの表に書かれた整数が等しい場合は,その値を覚えてあなたに伝える.そ うでない場合は,表に書かれている整数のうちJOI 君が覚えやすい方の整数を覚えてあなたに伝える. JOI 君にとっての整数の覚えやすさは,N 個の整数P0, P1, . . . , PN−1 で表される.これらの整数は,以下 の2 つの条件を満たす. • 0 ≦Pi ≦N −1 (0 ≦i ≦N −1). • Pi , Pj (0 ≦i < j ≦N −1). JOI 君にとってi がj よりも覚えやすいことは,Pi < Pj が成り立つことと同値である. あなたの課題は,JOI 君とK 回以下のやりとりを行うことで,それぞれのカードに書かれた整数を特定 することである.ただし,あなたは,JOI 君にとっての整数の覚えやすさを表す整数P0, P1, . . . , PN−1 がど のような値であるかを知らない. 課題 JOI 君とやりとりを行って,それぞれのカードに書かれた整数を特定するプログラムを作成せよ. 実装の詳細 あなたは,それぞれのカードに書かれた整数を特定する方法を実装した1 個のプログラムを書かねばな らない.プログラムはMemory2_lib.h をインクルードすること. プログラムは,以下のルーチンを実装しなければならない. • void Solve(int T, int N) このルーチンは,各テストケースに対し1 回だけ呼び出される.引数T は小課題の番号を表し,N は カードが2N 枚あることを表す. このルーチンは,Flip を呼び出すことによってカードに書かれた整数を特定し,その内容をAnswer を呼び出すことによって答えなければならない. 神経衰弱– 1 / 4 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 1 – Memory2 プログラム中では以下の関数を呼び出すことができる. • int Flip(int I, int J) この関数は,JOI 君にカードを指定する際に呼び出す.引数I, J は,JOI 君がめくるカードの番号I, J である. I とJ はともに0 以上2N −1 以下の互いに異なる整数でなければならない.これを満たさない引数 とともにFlip を呼び出した場合は不正解[1] となる. この関数は,整数AI と整数AJ が等しい場合はその値を,そうでない場合は整数AI と整数AJ のう ちJOI 君にとって覚えやすい方の値を返す. この関数をK 回を超えて呼び出した場合は不正解[2] となる. • void Answer(int I, int J, int X) この関数は,表に整数X が書かれたカードの番号を特定できたことを表す. 引数I, J, X は,以下の条件を満たしていなければならない. ◦0 ≦I ≦2N −1. ◦0 ≦J ≦2N −1. ◦I , J. ◦AI = AJ = X. これらを満たさない引数とともにAnswer を呼び出した場合は不正解[3] となる. 引数X は,以前のどの呼び出しにおける引数X とも異ならなければならない.これが満たされない 場合は不正解[4] となる. この関数は,ちょうどN 回呼び出さなければならない.これが満たされない場合は不正解[5] となる. 内部での使用のために他のルーチンを実装したり,グローバル変数を宣言したりするのは自由である.た だし,あなたの提出は標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはな らない. コンパイル・実行の方法 作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウン ロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルの サンプルも含まれている. 採点プログラムのサンプルは1 つのファイルからなる.そのファイルはgrader.c またはgrader.cpp である.作成したプログラムをテストするには,次のようにコマンドを実行する. • C の場合 gcc -std=c11 -O2 -o grader grader.c Memory2.c -lm 神経衰弱– 2 / 4 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 1 – Memory2 • C++ の場合 g++ -std=c++11 -O2 -o grader grader.cpp Memory2.cpp コンパイルが成功すれば,grader という実行ファイルが生成される. 実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラム のサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出 力に結果を出力する. 採点プログラムのサンプルの入力 採点プログラムのサンプルは標準入力から以下のデータを読み込む. • 1 行目には,整数T, N, K が空白を区切りとして書かれている.これらは,小課題の番号がT で,カー ドが2N 枚あり,JOI 君とのやりとりがK 回まで許されていることを表す. • 2 行目には,整数P0, P1, . . . , PN−1 が空白を区切りとして書かれている.これらはJOI 君にとっての 整数の覚えやすさを表す. • 3 行目には,整数A0, A1, . . . , A2N−1 が空白を区切りとして書かれている.これらはカードに書かれた 整数を表す. 採点プログラムのサンプルの出力 プログラムの実行が正常に終了した場合,採点プログラムのサンプルは標準出力へ以下の情報を1 行で 出力する(引用符は実際には出力されない). • 正解の場合,“Accepted” と出力する. • 不正解の場合,不正解の種類を“Wrong Answer [2]” のように出力する. 制限 すべての入力データは以下の条件を満たす. • 1 ≦N ≦50. • 0 ≦Pi ≦N −1 (0 ≦i ≦N −1). • Pi , Pj (0 ≦i < j ≦N −1). • 0 ≦Ai ≦N −1 (0 ≦i ≦2N −1). • どのx (0 ≦x ≦N −1) に対しても,Ai = x を満たすi (0 ≦i ≦2N −1) はちょうど2 つある. 神経衰弱– 3 / 4 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 1 – Memory2 小課題 小課題1 [10 点] 以下の条件を満たす. • T = 1. • K = 10 000. • Pi = i (0 ≦i ≦N −1). 小課題2 [50 点] 以下の条件を満たす. • T = 2. • K = 400. • Pi = i (0 ≦i ≦N −1). 小課題3 [40 点] 以下の条件を満たす. • T = 3. • K = 300. やりとりの例 採点プログラムのサンプルが読み込む入力の例と,それに対応するルーチンの呼び出しの例を以下に示す. 入力例 ルーチンの呼び出しの例 呼び出し 戻り値 1 3 10000 Flip(0, 2) 1 0 1 2 Flip(0, 4) 1 1 0 2 0 1 2 Flip(1, 2) 0 Answer(0, 4, 1) Flip(1, 3) 0 Flip(5, 2) 2 Flip(4, 5) 1 Answer(1, 3, 0) Answer(5, 2, 2) この例での関数の呼び出しは,必ずしも意味のある呼び出しとは限らないことに注意せよ. 神経衰弱– 4 / 4
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1 3 10000
0 1 2
1 0 2 0 1 2