Məsələlər
Варка овощей
Варка овощей
\includegraphics{https://static.e-olymp.com/content/b2/b2a36b51ee765e8dae0acd79f38795e8d6f59ca4.jpg}
Хитрость варки овощей состоит в том, чтобы все кусочки были примерно одинакового размера. Если они не являются таковыми, то маленькие кусочки получаются слишком мягкими, а крупные недоваренными. К счастью, Вы слышали о кухонном ноже, хотя предупреждения Ваших родителей об использовании острых инструментов до сих пор находятся в Вашей голове. Поэтому Вы хотите использовать его как можно меньше. Вы можете взять кусок овоща весом $w$ и разрезать его произвольным образом на две части с весами $w_{left}$ и $w_{right}$, где $w_{left} + w_{right} = w$. Эту операцию назовем "\textbf{разрез}".
Зная размеры имеющихся кусков овощей, определить наименьшее количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше заданного порогового значения.
\InputFile
Начинается с действительного числа $t~(0.5 < t < 1)$ с $2$ десятичными цифрами и натурального числа $n~(n \le 1000)$. Далее идут $n$ целых положительных весов $w_1, w_2, ..., w_n$. Все веса меньше чем $10^6$.
\OutputFile
Вывести минимальное количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше $t$. Считайте, что число необходимых разрезов меньше $500$. Чтобы избежать проблем с действительными числами, предположим, что оптимальный ответ для отношения $t$ будет таким же, как и для отношения $t + 0.0001$.
Giriş verilənləri #1
0.99 3 2000 3000 4000
Çıxış verilənləri #1
6
Giriş verilənləri #2
0.80 2 1000 1400
Çıxış verilənləri #2
3