No.247 Pseudo Linear Programming Problem
タグ : / 解いたユーザー数 180
作問者 :
yuki2006
Problem Statement
Let the function be $\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$.
Find the minimum value of $\displaystyle \sum_{i=1} ^N x_i$ under the constraint $f(x_1,x_2,\dots,x_N)=C$.
Here, $x_i$ are non-negative integer variables, and $a_i$,$C$ are integer constants greater than or equal to 1.
If there is no non-negative integer solution, output $-1$.
Input
$C$ $N$ $a_1\ a_2\ \dots\ a_N$
All inputs are given as integers.
$1 \le C \le \ 100000=10^5$
$1 \le N \le 100$
$1 \le a_i \le \ 100000=10^5$
Output
Output the minimum value of $\displaystyle \sum_{i=1} ^N x_i$ under the constraint of the problem.
Sample
Sample 1
Input
10 3 3 2 1
Output
4
In this case, the function $f$ is $3x_1+2x_2+x_3 $. Under the constraint $3x_1+2x_2+x_3=10 $, the solutions include
$(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)$
and many others, but
the minimum value of $\sum_{i=1} ^N x_i$ is $4$, attained at $(x_1,x_2,x_3)=(3,0,1)$.
Sample 2
Input
20 4 3 7 12 25
Output
4
When $(x_1,x_2,x_3,x_4)=(2,2,0,0)$, the value is $4$.
Sample 3
Input
100 3 90 9 12
Output
-1
There is no non-negative integer solution satisfying $90x_1+9x_2+12x_3 =100$, so output $-1$.
Sample 4
Input
100 1 50
Output
2
Sample 5
Input
100000 4 100000 50000 25000 12500
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。