시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 10 | 8 | 8 | 80.000% |
あなたは 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 つの部屋の組は何個あるか」の値 (部屋の順序を入れ替えたものは同じ組とみなす) を解答しなければならない.
ダンジョンを探索するために,あなたには次の行動を行うためのライブラリが提供される.
あなたは,JOI 君に解答する方法を実装した 1 個のプログラムを書かねばならない.プログラムは dungeon2.h
をインクルードすること.
プログラムは,以下のルーチンを実装しなければならない.
void Inspect(int R)
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] となる.C
は,宝石の色の種類が X
種類として,1 以上 X 以下の整数でなければならない.X の値は小課題ごとに定まっている.これを満たさない場合,不正解 [6] となる.int NumberOfRoads()
int LastRoad()
Move
を一度も呼び出す前にこの関数が呼び出された場合は,−1 を返す.int Color()
ルーチン Inspect
が呼び出された後,答えの判定が行われる.
内部での使用のために他のルーチンを実装したり,グローバル変数を宣言するのは自由である.ただし,あなたの提出は標準入力・標準出力,あるいは他のファイルといかなる方法でもやりとりしてはならない.
採点プログラムのサンプルは標準入力から以下のデータを読み込む.
Answer
の引数 D
として j,引数 A
として Aj を与えて呼び出した場合に採点プログラムのサンプルが正解と判定し,それ以外の場合に不正解と判定することを表す.採点プログラムのサンプルは,プレイヤーの初期位置を部屋 1 として,あなたの作成したルーチンを呼び出す.
プログラムの実行が正常に終了した場合,採点プログラムのサンプルは標準出力へ以下の情報を 1 行で 出力する (引用符は実際には出力されない).
Accepted : #move = 8
” のように出力される.Wrong Answer [1]
” のように出力される.以下では,入力データにおけるダンジョンの部屋の数を N,道の本数を M とする.
この小課題では,以下に従い得点が決定される.
Move
の呼び出し回数を C としたときの, C/M .ここで,⌊x⌋ は x を超えない最大の整数を表す.
採点システム上では,プログラムが正しく終了し,正解と判定された場合には詳細の欄に Accepted
と 表示される.ただし,小課題 3 の採点で,上の C, M が 64 < C/M となるテストケースについては,結果の 欄には不正解と表示されるので注意せよ.
採点プログラムのサンプルが読み込む入力の例と,それに対応するルーチンの呼び出しの例を以下に示す.
入力例 | ルーチンの呼び出しの例 | |
---|---|---|
呼び出し | 戻り値 | |
4 3 3 1 2 3 1 3 4 2 2 4 2 2 3 4 2 0 |
Inspect(3) |
|
NumberOfRoads() |
1 |
|
LastRoad() |
-1 |
|
Move(1,2) |
||
Color() |
1 |
|
LastRoad() |
1 |
|
NumberOfRoads() |
3 |
|
Move(1,3) |
||
Color() |
2 |
|
Answer(1,4) |
||
Answer(2,2) |
||
Answer(3,0) |
この例での関数の呼び出しは,必ずしも意味のある呼び出しとは限らないことに注意せよ.
C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)