問題一覧 > 通常問題

No.527 ナップサック容量問題

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 216
作問者 : りあんりあん / テスター : 👑 Nafmo2Nafmo2
9 ProblemId : 1133 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-06-25 01:20:33

問題文

グレート岡山大国に住む大岡くんは, あるナップサックを持っていますが, 容量がどのくらいだったか忘れてしまいました.

ただ, ちょうどそこに $N$ 個の荷物があったので, 大岡くんは0-1ナップサック問題よろしくナップサック内の価値の最大値を求めてみました.

荷物の情報と価値の最大値の情報が与えられるので, 大岡くんのナップサックの容量として考えられる値の最小値と最大値を求めてください.

ただし, 不思議なことに大岡くんのナップサックの容量は必ず整数で, 1以上であることが保障されています.

また, 容量の最大値が定まらなかった場合, 最大値の代わりに "inf" と出力してください.

入力

$N$
$v_1$ $w_1$
:
$v_N$ $w_N$
$V$

1行目に, 品物の個数 $N$ が与えられます.

2行目から $N + 1$行目までの $N$ 行の間, 荷物の情報が与えられます.

このうち $i (1 \leq i \leq N)$ 行目には $i$ 番目の荷物の価値 $v_i$ と容積 $w_i$ が空白区切りで与えられます.

$N + 2$ 行目にナップサック内の価値の最大値 $V$ が与えられます.

入力は全て整数で, 以下の制約を満たします.

  • $1 \leq N \leq 100$
  • $1 \leq v_i, w_i \leq 1000$
  • $0 \leq V \leq 100000$
  • ナップサック内の価値の最大値が $V$ となるナップサックの容量 $W$ が, $1 \leq W \leq 100000$ に少なくとも一つ存在する

出力

$min$
$max$

1行目にナップサックの容量として考えられる値の最小値を,

2行目にナップサックの容量として考えられる値の最大値, または最大値が定まらない場合は "inf" を出力してください.

最後に改行してください.

サンプル

サンプル1
入力
3
5 3
9 8
3 2
8
出力
5
7

ナップサックの容量が $W$ のとき, 価値 $V$ はそれぞれ以下のようになります.

\begin{array}{c|cccccccc} \hline W & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ \hline V & 0 & 3 & 5 & 5 & 8 & 8 & 8 & 9 & 9 & 12 \\ \hline \end{array}

よって, $W = 5, 6, 7$ のときに $V = 8$ となるので, 最小値は5, 最大値は7です.

サンプル2
入力
4
33 4
114 514
123 456
3 14
0
出力
1
3

大岡くんのナップサックにはいずれの荷物も入らないことがわかりました.

サンプル3
入力
2
33 4
114 514
147
出力
518
inf

荷物がふたつとも入ってしまったので, 容量は518以上である, ということしかわかりませんでした.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。