JOI本戦恒例の真のラスボス。
id:qnighyさんに
「最後にナップサック問題をもってくるあたり、さすがJOIだな」
的な事を言われたけど、一瞬何のことか分からなくて、ちょっとして分かったんだけど、そのときにはもうすでに遅かったっていう。
本戦競技で疲れた選手たちに追い打ちをかける趣味の悪い難問である。
せっかくなので、問題形式にしてみようと思う。
あなたは昼食をレストラン「とき」で食べることになった。 あなたは与えられた 1000円分の食券で最高のランチタイムを楽しみたいと思っている。 そのためにあなたは、メニューの数 N、i 番目のメニューの値段 pi、i 番目のメニューの満足度 si が与えられたときに、 1000円を超えない範囲で満足度が最高になるようなメニューの選び方を出力するプログラムを組むことにした。 ただし、同じメニューを複数個注文することは出来る。入力
・1行目にはメニューの数を表す N (1 ≤ N ≤ 1000) が書かれている。 ・続く N 行にはメニューの値段と満足度が書かれており、 i+1 行目には、pi,si (1 ≤ pi,si ≤ 1000) が空白を区切りとして書かれている。ありきたりな問題ですが、暇なら書いてみて下さいw もしかすると来年役に立つかもw出力
出力は N 行からなり、i 行目には i 番目のメニューをいくつ注文すればいいかを出力する。
