問題一覧 > 通常問題

No.247 線形計画問題もどき

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 173
作問者 : yuki2006
16 ProblemId : 678 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-12-06 19:49:56

問題文

関数f(x1,x2,…,xN)=∑i=1Naixi=a1x1+a2x2+⋯+aNxN\displaystyle f(x_1,x_2,\dots,x_N)=\sum_{i=1} ^N a_i x_i=a_1x_1+a_2x_2+\dots+a_Nx_N とする。
この時f(x1,x2,…,xN)=Cf(x_1,x_2,\dots,x_N)=Cの制約下での ∑i=1Nxi\displaystyle \sum_{i=1} ^N x_iの最小値を求めてください。
ただし、xix_iは非負の整数変数であり、aia_i,CCは1以上の整数の定数であるとする。
この時、非負の整数解がなければ−1-1を出力してください。

入力

CC
NN 
a1 a2 … aNa_1\ a_2\ \dots\ a_N

入力は全て整数で与えられる。
1≤C≤ 100000=1051 \le C \le \ 100000=10^5
1≤N≤1001 \le N \le 100
1≤ai≤ 100000=1051 \le a_i \le \ 100000=10^5

出力

問題の制約下での ∑i=1Nxi\displaystyle \sum_{i=1} ^N x_iの最小値を求めてください。

サンプル

サンプル1
入力
10
3
3 2 1
出力
4

この時、関数ffは3x1+2x2+x33x_1+2x_2+x_3 である。3x1+2x2+x3=103x_1+2x_2+x_3=10 の制約下での解の組は
(x1,x2,x3)=(0,1,8)(x_1,x_2,x_3)=(0,1,8)
(x1,x2,x3)=(0,0,10)(x_1,x_2,x_3)=(0,0,10)
(x1,x2,x3)=(0,2,6)(x_1,x_2,x_3)=(0,2,6)
(x1,x2,x3)=(1,2,3)(x_1,x_2,x_3)=(1,2,3)
(x1,x2,x3)=(3,0,1)(x_1,x_2,x_3)=(3,0,1)
(x1,x2,x3)=(0,5,0)(x_1,x_2,x_3)=(0,5,0)
など多数存在するが、
∑i=1Nxi\sum_{i=1} ^N x_iの最小値は(x1,x2,x3)=(3,0,1)(x_1,x_2,x_3)=(3,0,1) の時の44である。

サンプル2
入力
20
4
3 7 12 25
出力
4

(x1,x2,x3,x4)=(2,2,0,0)(x_1,x_2,x_3,x_4)=(2,2,0,0)のとき 44になる。

サンプル3
入力
100
3
90 9 12
出力
-1

90x1+9x2+12x3=10090x_1+9x_2+12x_3 =100を満たす非負の整数の解は存在しないため −1-1を出力する。

サンプル4
入力
100
1
50
出力
2

サンプル5
入力
100000
4
100000 50000 25000 12500
出力
1

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