問題一覧 > 通常問題

No.733 分身並列コーディング

レベル : / 実行時間制限 : 1ケース 1.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 80
作問者 : りあんりあん / テスター : confconf
10 ProblemId : 1132 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-09-07 07:53:45

おことわり

想定解は Python3 では TLE しますが PyPy3 で提出すれば AC することが確認されています。

問題文

りあんくんは忍者の末裔で、分身をすることが可能です。

今日りあんくんはプログラミングコンテストに参加していて、考察の結果、全ての問題の解法とコーディングにかかる時間がわかりました。ただ、考察に随分時間を使ってしまって、コーディングをする時間があと $T$ 分しか残っていません。

そこで、得意の分身を使って並列にコーディングをすることにしました。ただ、分身するにも人数分PCを用意するにもコストがかかるので、なるべく分身する人数を少なくしたいです。

なので、時間内に全完するのに必要な最少の分身人数(何人で並列にコーディングすれば時間内に全完できるか)を求めてください。


なお、PC間でのコードのコピペをすることができないので、一つの問題は複数のPCで分担せず一台のPCで書き切らなければいけません。

入力

$T$
$N$
$t_1$
:
$t_N$

1行目に、コンテストの残り時間 $T$ が与えられます。

続いて2行目に、問題の数 $N$ が与えられます。

続いて3行目から $N$ 行の間、$i$ 番目の問題の実装にかかる時間 $t_i$ が与えられます。

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

  • $1 \le T \le 2000$
  • $1 \le N \le 17$
  • $1 \le t_i \le T$

出力

時間内に全完するのに必要な最少の分身人数を出力してください。

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

サンプル

サンプル1
入力
5
3
1
5
3
出力
2

1番目と3番目の問題を1人目が、2番目の問題を2人目が解くと2人で時間内に全完することができます。

サンプル2
入力
9
4
5
5
5
5
出力
4

一人一問ずつしか解けません。

サンプル3
入力
10
6
2
2
2
3
5
6
出力
2

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