Варка овощей
Варка овощей
Хитрость варки овощей состоит в том, чтобы все кусочки были примерно одинакового размера. Если они не являются таковыми, то маленькие кусочки получаются слишком мягкими, а крупные недоваренными. К счастью, Вы слышали о кухонном ноже, хотя предупреждения Ваших родителей об использовании острых инструментов до сих пор находятся в Вашей голове. Поэтому Вы хотите использовать его как можно меньше. Вы можете взять кусок овоща весом w и разрезать его произвольным образом на две части с весами w_{left} и w_{right}, где w_{left} + w_{right} = w. Эту операцию назовем "разрез".
Зная размеры имеющихся кусков овощей, определить наименьшее количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше заданного порогового значения.
Входные данные
Начинается с действительного числа t~(0.5 < t < 1) с 2 десятичными цифрами и натурального числа n~(n \le 1000). Далее идут n целых положительных весов w_1, w_2, ..., w_n. Все веса меньше чем 10^6.
Выходные данные
Вывести минимальное количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше t. Считайте, что число необходимых разрезов меньше 500. Чтобы избежать проблем с действительными числами, предположим, что оптимальный ответ для отношения t будет таким же, как и для отношения t + 0.0001.
Пример
0.99 3 2000 3000 4000
6
0.80 2 1000 1400
3