No.393 2本の竹

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 105
作問者 :

horiesiniti / テスター :

37zigen

6 ProblemId : 1189 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2016-07-12 00:14:03

問題文

貴方は竹職人である。竹を切って顧客の要望に答える。

今貴方の手元には整数長の2本の竹がある。
そしてあなたの手元には複数人の顧客からの竹の長さの要求がある。一人の顧客は一つ、整数長の竹を要求している。

貴方は2本の竹を細かく切断して顧客の要求にこたえるが、全員の要望に応えられるかわからない。
そこで一人でも多くの客に竹を提供できるよう竹を切断することにした。

竹の長さと顧客からの要望リストが与えられるので最大何人に竹を提供できるか計算するプログラムを書いてほしい。

入力

 $d$ 
 $n_{1_{1}}$   $n_{2_{1}}$ 
 $m_{1}$ 
 $A_{1_{1}}$   $\dots$   $A_{m 1_{1}}$ 
 $\dots$ 
 $n_{1_{d}}$   $n_{2_{d}}$ 
 $m_{d}$ 
 $A_{1_{d}}$   $\dots$   $A_{m d_{d}}$

データセットは複数からなる。

データセットの数

d

が一行目に与えられる。

0 < d \leq 10

一つのデータセットは 2本の竹の長さ

$n_{1}$ $n_{2}$ が一行に与えられる。 $1 \leq n_{1}, n_{2} \leq 100000$

次の行に顧客の人数ｍが一行に与えられる。 $1 \leq m \leq 60$

その次の行に空白区切りで各顧客の要求竹長さ $a_{i}$ が与えられる。 $1 \leq a_{i} \leq 100000$

これで一つのデータセットであり、

d

件繰り返される。
各データセットごとに竹を提供できる顧客の最大数を答えよ。

i

番目のデータセットに対する答えは

u_{i}

である。

出力

 $u_{1}$ 
 $\dots$ 
 $u_{d}$

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

サンプル

サンプル1

入力

4
15 13
6
4 5 7 9 3 7
10 20
6
5 8 9 6 5 7
20 20
9
5 4 4 4 7 6 11 5 4
3 3
3
7 8 4

出力

4つのデータセットがある。 4 5 3と7 7などの切断が可能であり1つ目のデータセットは５人である
5 5と6 7などの切断が可能であり2つ目のデータセットは４人である
4 5 4 7と5 4 4 6等の切断が可能であり3つ目のデータセットは8人である。
4つ目はどの顧客の要求もかなえられないので0人となる。

サンプル2

入力

出力

5
2

二つのデータセットがある。一つ目は竹を一本目の竹を2 8で、2本目の竹を4 3 7で切ることで5人の顧客全員の要求にこたえられる。 2つ目のデータセットは7と5か7と7でもよいがとりあえず2人の要求にこたえられる。よって一つ目のデータセットには5 2つ目のデータセットには2と出力せよ。出力はデータセット一つごとに改行すること。

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