Problem B. Kingdom Rush 問題紹介
Kingdom Rush というタワーディフェンスゲームをモチーフにしたということですが、、、あまりそんな感じはしません。もちろんゲームのことを何も知らなくても問題は解けます。
この問題に出てくる Kingdom Rush では、ステージ(level)をクリアして星(★)を集めていきます。各ステージでは最大2つまで星を獲得できます。
この問題に出てくる Kingdom Rush では、ステージ(level)をクリアして星(★)を集めていきます。各ステージでは最大2つまで星を獲得できます。
- 1つ星条件(星いくつ持っていること)を達成していれば星を1つ獲得します。
- 2つ星条件(星いくつ持っていること)を達成していれば星を2つ獲得します。
- 既に1つ星を獲得したステージでも2つ星条件を達成していればもう1つ星を獲得できます。(各ステージで2つまで星を獲得できます)
全ての星(ステージ数×2)を集めるのにかかる最短手数(ゲーム数)を求める問題です。
※ステージの星条件によっては解がないケースもあります。
例:
- ステージ1: 1つ星条件=星0個 2つ星条件=星1個
- ステージ2: 1つ星条件=星0個 2つ星条件=星2個
このとき、次の手順で進めると最短手数で全ての星をコンプリートすることができます。
- ステージ1の1つ星条件(星0個)を達成しているので星1つ獲得
- ステージ1の2つ星条件(星1個)を達成しているのでもう1つ獲得
- ステージ2の2つ星条件(星2個)を達成しているので星2つ獲得
入力データ:
最初の行は問題数 T。以降 T問の問題データが続きます。
問題データの1行目はステージ数 N。
その後N行、各ステージの1つ星条件 ai と2つ星条件 bi がスペース区切りで続きます。
データ制限:
- 1 ≤ T ≤ 100 (問題数は100問)
- Small input の場合:1 ≤ N ≤ 10 (最大10ステージ)Large input の場合:1 ≤ N ≤ 1000 (最大1000ステージ)
- 0 ≤ ai ≤ bi ≤ 2001 (1つ星条件、2つ星条件)
0 件のコメント:
コメントを投稿