레이팅 미적용JOI 国はN 個の州からなり,それぞれ1 からN までの番号が付けられている.2022 年,JOI 国では大統
領選挙が開催されることになった.この選挙では各州で投票が行われ,勝った候補者がその州に割り当てら
れている1 票を獲得する.
さて,大統領選挙に出馬する理恵さんは,演説によって自身への信頼度を上げ,選挙で勝とうと考えた.
演説により,具体的には次のことが起こる.
• 州i (1 ≦i ≦N) での合計演説時間がAi 時間に達すると,その州に割り当てられている1 票を獲得で
きる.
• 州i (1 ≦i ≦N) での合計演説時間がBi 時間に達すると,協力者1 人を得ることができる.得られた
協力者は,それ以降演説を行い,合計演説時間を増やすことができる.
• ただし,州i からの協力者を得られない場合もあり,その場合はBi = −1 として情報が与えられる.
それ以外の場合は,Bi ≧Ai であることが保証される.
なお,州i (1 ≦i ≦N) で獲得した協力者が州i 以外で演説をすることや,1 つの州で同時に2 人以上が演
説をすることも可能である.たとえば,ある州で同時に2 人がx 時間演説をした場合,この州の合計演説時
間は2x 時間増加する.ただし,演説時間が整数である必要はない.また,州の間を移動する時間は無視で
きるものとする.
投票日が近いので,理恵さんは目標のK 票をできるだけ早く獲得したい.
州の数と各州の情報が与えられたとき,K 票を集めるまでにかかる時間の最小値を求めるプログラムを作
成せよ.
• 1 ≦N ≦500.
• 1 ≦K ≦N.
• 1 ≦Ai ≦1 000 (1 ≦i ≦N).
• Ai ≦Bi ≦1 000 またはBi = −1 (1 ≦i ≦N).
- (5 点) Bi = −1 (1 ≦i ≦N).
- (5 点) Bi = −1 またはBi = Ai (1 ≦i ≦N).
- (11 点) N ≦7.
- (12 点) N ≦20.
- (33 点) N ≦100.
- (11 点) K = N.
- (23 点) 追加の制約はない.
第21 回日本情報オリンピック(JOI 2021/2022) 本選
2022 年2 月13 日(オンライン開催)
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N
K
A1 B1
A2 B2
...
AN BN
第21 回日本情報オリンピック(JOI 2021/2022) 本選
2022 年2 月13 日(オンライン開催)
標準出力に,K 票を集めるまでにかかる時間の最小値を1 行で出力せよ.正解との絶対誤差が0.01 以下
であるような答えを出力すれば,正答とみなされる.出力は以下のいずれかの形式でなければならない.
• 整数.(例:123,0,-2022)
• 整数,半角ピリオド,0 から9 までの数字を並べた列,をその順にスペースなどで区切らず続けた形
式.出力する小数点以下の桁数に制限はない.(例:123.4,-123.00,0.00288)
たとえば,1.23456e+05 や1.23456e5 のような指数表記で出力してはならない.
3
3
1 5
2 3
4 5
5.500000000000000
7
4
4 -1
11 -1
6 -1
12 -1
36 -1
11 -1
20 -1
32.000000000000000
5
3
4 -1
5 -1
6 -1
7 7
8 8
11.500000000000000
7
5
28 36
11 57
20 35
19 27
31 33
25 56
38 51
62.166666666666664
20
14
106 277
175 217
170 227
164 245
118 254
139 261
142 270
185 200
162 241
153 239
128 264
103 299
147 248
158 236
160 232
183 205
194 197
135 260
153 234
128 260
644.203571428571422