#2170. Dungeon 2

Dungeon 2

Dungeon 2

题目描述

Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 3 – Dungeon 2 ダンジョン2 (Dungeon 2) あなたはJust Ordinary Inventions 社を知っているだろうか? この会社の業務は「ただ平凡な発明(just ordinary inventions)」をすることである. JOI 君は,Just Ordinary Inventions 社で開発された最新のゲームで遊んでいる. このゲームは,いくつかの部屋といくつかの道からなるダンジョンを探索するゲームである.道はダン ジョン内の異なる2 つの部屋を結んでおり,双方向に移動可能である.どの異なる2 つの部屋についても, それらを結ぶ道は高々1 本しかなく,両端が同じ部屋であるような道は存在しない.また,ダンジョンの どの2 つの部屋の間も,何本かの道を使うことで互いに移動できることがわかっている.各部屋同士は非 常によく似ており,同じ本数の道が出ている部屋同士は,部屋の様子を見るだけではまったく区別ができ ない. このゲームでは,攻略を助けるために各部屋に目印と台座が用意されている.部屋から出ている道は,目 印を基準として1 本目,2 本目,. . . と数えることができる.ゲーム中にダンジョンの構造が変化すること はない.したがって,同じ部屋から同じ番号の道を使って移動すると,いつも同じ部屋にたどり着く.台 座にはプレイヤーが色を変更することができる宝石が1 個飾られている.宝石の色は色1,色2,. . . ,色 X のいずれかであり,ゲーム開始時の各部屋の宝石の色は色1 である.宝石の色はプレイヤーが操作しな い限り変更されることはない. JOI 君は,もしこのダンジョンの構造,すなわちダンジョンの部屋同士がどのように道で結ばれている かがわかれば,このゲームは簡単に攻略できてしまうことに気づいた.しかし,JOI 君がいろいろ試して もダンジョンの構造を決定することはできなかった.そこで,あなたはJOI 君に代わってダンジョンの構 造を決定するプログラムを書くことにした. 課題 ダンジョンを探索して,ダンジョンの構造を決定するプログラムを作成せよ.しかし,JOI 君はダンジョ ンの構造を完全に明かされることを望まなかったため,プログラムはダンジョンの構造を直接答えるので はなく,1 以上R 以下の各整数i に対して「最小でちょうどi 本の道を使うことで移動できる2 つの部屋の 組は何個あるか」の値(部屋の順序を入れ替えたものは同じ組とみなす) を解答しなければならない. ダンジョンを探索するために,あなたには次の行動を行うためのライブラリが提供される. • 現在いる部屋から,何本の道が出ているかを知る. • 現在いる部屋の台座に飾られている宝石の色を知る. • 現在いる部屋の台座に飾られている宝石の色を,指定した色にする(現在の色と同じ色を指定するこ ともできる).その後,部屋から出ている道を1 本選び,その道を使って他の部屋へ移動する. • 最後に使った道が,現在いる部屋から出ている道のうち何本目かを知る. ダンジョン2– 1 / 6 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 3 – Dungeon 2 実装の詳細 あなたは,JOI 君に解答する方法を実装した1 個のプログラムを書かねばならない.プログラムは dungeon2.h をインクルードすること. プログラムは,以下のルーチンを実装しなければならない. • void Inspect(int R) このルーチンは,最初に1 回だけ呼び出される. ◦引数R は,1 以上R 以下の各整数i に対して「最小でちょうどi 本の道を使うことで移動できる 2 つの部屋の組は何個あるか」の値(部屋の順序を入れ替えたものは同じ組とみなす) を解答し なければならないことを表す. また,次のルーチンを呼び出し,質問に答えなければならない. • void Answer(int D, int A) ◦引数D,A は,この呼び出しにおいて, 「最小でちょうどD 本の道を使うことで移動できる2 つ の部屋の組はA 個ある」ことを解答することを表す. ただし,Answer の呼び出しは以下の条件を満たすこと. ◦D は1 以上R 以下の整数でなければならない.これを満たさない場合,不正解[1] となる. ◦Answer を同じ引数D で2 回以上呼び出してはならない.これを満たさない場合,不正解[2] と なる. ◦Answer はちょうどR 回呼び出さなければならない.これを満たさない場合,不正解[3] となる. ◦A は最小でちょうどD 本の道を使うことで移動できる2 つの部屋の組の個数でなければならな い.これを満たさない場合,不正解[4] となる. Answer の呼び出しが不正解と判定された場合,それ以降のプログラムは実行されるとは限らない. これに加え,プログラム中では,以下のルーチンを呼び出すことができる. • void Move(int I, int C) ◦引数I は,プレイヤーが移動するために選ぶ道の番号である.この呼び出しの直後,プレイヤー は現在いる部屋から出ているI 本目の道を使って他の部屋まで移動する. ◦引数C は,部屋の移動を行う前に,現在いる部屋の台座に飾られている宝石の色を色C にする ことを表す. ただし,Move の呼び出しは以下の条件を満たすこと. ◦引数I は,プレイヤーが現在いる部屋から出ている道の本数をK として,1 以上K 以下の整数 でなければならない.これを満たさない場合,不正解[5] となる. ダンジョン2– 2 / 6 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 3 – Dungeon 2 ◦引数C は,宝石の色の種類がX 種類として,1 以上X 以下の整数でなければならない.X の値 は小課題ごとに定まっている.これを満たさない場合,不正解[6] となる. ◦Move を1 500 000 回より多く呼び出してはならない.呼び出した場合,不正解[7] となる. • int NumberOfRoads() ◦この関数は,プレイヤーが現在いる部屋から出ている道の本数を返す. • int LastRoad() ◦この関数は,プレイヤーが最後に使った道が,現在いる部屋から出ている道のうち何本目の道 であるかを返す.ただし,Move を一度も呼び出す前にこの関数が呼び出された場合は,−1 を 返す. • int Color() ◦この関数は,プレイヤーが現在いる部屋の台座に飾られている宝石の色を返す. ルーチンInspect が呼び出された後,答えの判定が行われる. 内部での使用のために他のルーチンを実装したり,グローバル変数を宣言するのは自由である.ただし, あなたの提出は標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない. コンパイル・実行の方法 作成したプログラムをテストするための,採点プログラムのサンプルが,コンテストサイトからダウン ロードできるアーカイブの中に含まれている.このアーカイブには,提出しなければならないファイルの サンプルも含まれている. 採点プログラムのサンプルは1 つのファイルからなる.そのファイルはgrader.c またはgrader.cpp である.作成したプログラムをテストするには,次のようにコマンドを実行する. • C の場合 gcc -std=c11 -O2 -o grader grader.c dungeon2.c -lm • C++ の場合 g++ -std=c++11 -O2 -o grader grader.cpp dungeon2.cpp コンパイルが成功すれば,grader という実行ファイルが生成される. 実際の採点プログラムは,採点プログラムのサンプルとは異なることに注意すること.採点プログラム のサンプルは単一のプロセスとして起動する.このプログラムは,標準入力から入力を読み込み,標準出 力に結果を出力する. ダンジョン2– 3 / 6 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 3 – Dungeon 2 採点プログラムのサンプルの入力 採点プログラムのサンプルは標準入力から以下のデータを読み込む. • 1 行目には,整数N, X, R が空白を区切りとして書かれている.これは,ダンジョンに部屋1,部屋 2,. . .,部屋N のN 個の部屋があり,宝石の色がX 種類あり,プログラムが解答すべき値がR 個で あることを表す. • 続く2N 行のうちの2i −1 行目(1 ≦i ≦N) には,整数Di が書かれており,部屋i からDi 本の道が 出ていることを表す.2i 行目(1 ≦i ≦N) には,Di 個の整数Ti1, Ti2, . . . , TiDi が空白を区切りとして書 かれている.これは,部屋i から出ているj (1 ≦j ≦Di) 本目の道を使って移動すると部屋Tij にた どり着くことを表す. • 続くR 行のうちのj 行目(1 ≦j ≦R) には,整数Aj が書かれている.これは,最小でちょうどj 本の 道を使うことで移動できる2 つの部屋の組がAj 個あることを表す.つまり,各j (1 ≦j ≦R) に対し て,Answer の引数D としてj,引数A としてAj を与えて呼び出した場合に採点プログラムのサンプ ルが正解と判定し,それ以外の場合に不正解と判定することを表す. 採点プログラムのサンプルは,プレイヤーの初期位置を部屋1 として,あなたの作成したルーチンを呼 び出す. 採点プログラムのサンプルの出力 プログラムの実行が正常に終了した場合,採点プログラムのサンプルは標準出力へ以下の情報を1 行で 出力する(引用符は実際には出力されない). • 正解の場合,関数Move を呼び出した回数が“Accepted : #move = 8” のように出力される. • 不正解の場合,不正解の種類が“Wrong Answer [1]” のように出力される. 制限 すべての入力データは以下の条件を満たす.N, Di, Tij の意味については「採点プログラムのサンプルの 入力」の項目を参照せよ. • 2 ≦N ≦200. • 3 ≦X ≦100. • 1 ≦R ≦200. • 1 ≦Di ≦N −1 (1 ≦i ≦N). • 1 ≦Ti j ≦N かつTij , i (1 ≦i ≦N, 1 ≦j ≦Di). ダンジョン2– 4 / 6 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 3 – Dungeon 2 • Ti1, Ti2, . . . , TiDi (1 ≦i ≦N) は互いに異なる. • 各i, j (1 ≦i ≦N, 1 ≦j ≦Di) に対し,TTijk = i を満たすk (1 ≦k ≦DTij) が存在する. • どの2 つの部屋の間も,何本かの道を使うことで互いに移動できる. 小課題 以下では,入力データにおけるダンジョンの部屋の数をN,道の本数をM とする. 小課題1 [17 点] 以下の条件を満たす. • N ≦50. • M ≦100. • X = 100. 小課題2 [27 点] 以下の条件を満たす. • N ≦50. • M ≦100. • X = 3. 小課題3 [56 点] • X = 3 を満たす. この小課題では,以下に従い得点が決定される. • この小課題の全てのテストケースにおける,次の値の最大値をL とおく. ◦Move の呼び出し回数をC としたときの,C M . • このとき,この小課題の得点は, ◦L ≦14 のとき,56 点. ◦14 < L ≦32 のとき,⌊70 −L⌋点. ダンジョン2– 5 / 6 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 3 – Dungeon 2 ⌊ ⌋ 54 −L ◦32 < L ≦64 のとき, 点. 2 ◦64 < L のとき,0 点. ここで,⌊x⌋はx を超えない最大の整数を表す. 採点システム上では,プログラムが正しく終了し,正解と判定された場合には詳細の欄にAccepted と 表示される.ただし,小課題3 の採点で,上のC, M が64 < C M となるテストケースについては,結果の 欄には不正解と表示されるので注意せよ. やりとりの例 採点プログラムのサンプルが読み込む入力の例と,それに対応するルーチンの呼び出しの例を以下に示す. 入力例 ルーチンの呼び出しの例 呼び出し 戻り値 4 3 3 Inspect(3) 1 NumberOfRoads() 1 2 LastRoad() -1 3 Move(1,2) 1 3 4 Color() 1 2 LastRoad() 1 2 4 NumberOfRoads() 3 2 2 3 Move(1,3) 4 Color() 2 2 Answer(1,4) 0 Answer(2,2) Answer(3,0) この例での関数の呼び出しは,必ずしも意味のある呼び出しとは限らないことに注意せよ. ダンジョン2– 6 / 6

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 3 3
1
2
3
1 3 4
2
2 4
2
2 3
4
2
0