No.247 線形計画問題もどき
yuki2006問題文
関数$\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(x_1,x_2,\dots,x_N)=C$の制約下での $\displaystyle \sum_{i=1} ^N x_i$の最小値を求めてください。
ただし、$x_i$は非負の整数変数であり、$a_i$,$C$は1以上の整数の定数であるとする。
この時、非負の整数解がなければ$-1$を出力してください。
入力
$C$ $N$ $a_1\ a_2\ \dots\ a_N$
入力は全て整数で与えられる。
$1 \le C \le \ 100000=10^5$
$1 \le N \le 100$
$1 \le a_i \le \ 100000=10^5$
出力
問題の制約下での $\displaystyle \sum_{i=1} ^N x_i$の最小値を求めてください。
サンプル
サンプル1
入力
10 3 3 2 1
出力
4
この時、関数$f$は$3x_1+2x_2+x_3 $である。$3x_1+2x_2+x_3=10 $の制約下での解の組は
$(x_1,x_2,x_3)=(0,1,8)$
$(x_1,x_2,x_3)=(0,0,10)$
$(x_1,x_2,x_3)=(0,2,6)$
$(x_1,x_2,x_3)=(1,2,3)$
$(x_1,x_2,x_3)=(3,0,1)$
$(x_1,x_2,x_3)=(0,5,0)$
など多数存在するが、
$\sum_{i=1} ^N x_i$の最小値は$(x_1,x_2,x_3)=(3,0,1)$ の時の$4$である。
サンプル2
入力
20 4 3 7 12 25
出力
4
$(x_1,x_2,x_3,x_4)=(2,2,0,0)$のとき $4$になる。
サンプル3
入力
100 3 90 9 12
出力
-1
$90x_1+9x_2+12x_3 =100$を満たす非負の整数の解は存在しないため $-1$を出力する。
サンプル4
入力
100 1 50
出力
2
サンプル5
入力
100000 4 100000 50000 25000 12500
出力
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。