- 1 名前：（-＿-）さん [2017/06/17(土) 01:03:47.26 ID:6krL9hqz0.net]
- ヒッキーが競技プログラミングするスレ
関連スレ
ヒッキーのプログラミングするスレ 10 (旧 プログラミング雑談 in HIKIKO)
matsuri.2ch.net/test/read.cgi/hikky/1495307533/l50
ヒッキーのプログラミングするスレ (共同作業)
matsuri.2ch.net/test/read.cgi/hikky/1491250289/l50
- 312 名前：Div2 A or B (1/2) mailto:sage [2017/08/25(金) 22:13:19.21 ID:5Cg5j47b0.net]
- 東京ドーム君はディナーとして、（お湯を注いで）K分待つタイプのカップ麺にお湯を注ぎました。
ただ待つのが嫌いな東京ドーム君は、N個のゲームから複数（全てでも、一つもない場合も含めて）で遊んで暇潰しすることに決めました。
各ゲームは1分単位で遊べて、それぞれ最低ゲーム時間と最大ゲーム時間が決まっています。
下限時間が0のゲームは遊ばないという選択も可能（0分遊ぶという解釈）ですが、それより大きな下限を持つゲームは必ず遊ばなければなりません。
東京ドーム君はそれぞれのゲームの時間内で全てのゲームを（1分単位で）遊んで、丁度K分の暇潰しになるよう計画を立てました。
例えば、3個のゲームがあった場合、ゲーム1, ゲーム2, ゲーム3の遊ぶ時間が、順番に
7分以上29分以下
5分以上11分以下
1分以上17分以下
でなければならない初期条件として、
15分のカップラーメンの出来上がり待ちの間に遊ぶゲームの分数は(x1,x2,x3)という組で(7,5,3)と計画可能です。（ゲーム切り替えには時間を要しないものとします）
しかし東京ドーム君は野心的なので、このような時間の組の決め方を全て知りたくなりました。
東京ドーム君が全列挙してみると
9 5 1
8 6 1
8 5 2
7 7 1
7 6 2
7 5 3
となりました。
東京ドーム君は全列挙後にその成果を眺めていたところ、あることを閃きました。それは、
・実際にそれぞれのゲームを遊ぶ時間の最小値を見ると、そのゲームの初期条件の下限時間以上になる
・実際にそれぞれのゲームを遊ぶ時間の最大値を見ると、その変数の初期条件の上限値以下になる
というものです。例から見ても実際 ゲーム1, ゲーム2, ゲーム3は、順番に
7分以上9分以下
5分以上7分以下
1分以上3分以下
の時間しか出てきていません。
つまり、初期条件の幅を、実際はもっと狭められうるのではないかと予感しました。
しかし東京ドーム君はカップ麺が伸びてしまうので、一般に全列挙を一々して確かめている暇がありません。
あなたが東京ドーム君の代わりに、初期条件を狭めてみてください。但し、必ず狭められるとは限りません。
ちなみに出題では、可能な値の組み合わせが少なくとも1つあることが保証された入力しかありません。
- 313 名前：Div2 A or B (2/2) mailto:sage [2017/08/25(金) 22:13:32.93 ID:5Cg5j47b0.net]
- 入力:
N K
x1l x1u
x2l x2u
:
xNl xNu
一行目にゲームの個数N(1≦N≦100)と、カップ麺のお湯を注いだ後の待ち時間K分(0≦K≦10^8)
二行目以降、N行に渡る、各々のゲームの下限分数xil (i行目)と上限分数xiu (i行目) (i = 1... N; xil≦xiu; 0≦xil,xiu≦10^6)
出力:
x'1l x'1u
:
x'Nl x'Nu
i行目、
xilの実際に取り得る分数の最小値をx'il、
xiuの実際に取り得る分数の最大値をx'iu、としてN行
サンプル:
入力:
3 15
7 29
5 11
1 17
出力:
7 9
5 7
1 3
──────
入力:
3 55
7 29
5 11
1 17
出力:
27 29
9 11
15 17
──────
入力:
5 120
7 29
5 11
1 17
30 50
7 19
出力:
23 29
5 11
11 17
44 50
13 19
──────
入力:
5 14500
0 1000
1000 2000
2000 3000
3000 4000
4000 5000
出力:
500 1000
1500 2000
2500 3000
3500 4000
4500 5000
|
 |
