eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Варка овощей

Варка овощей

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Хитрость варки овощей состоит в том, чтобы все кусочки были примерно одинакового размера. Если они не являются таковыми, то маленькие кусочки получаются слишком мягкими, а крупные недоваренными. К счастью, Вы слышали о кухонном ноже, хотя предупреждения Ваших родителей об использовании острых инструментов до сих пор находятся в Вашей голове. Поэтому Вы хотите использовать его как можно меньше. Вы можете взять кусок овоща весом 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.

Пример

Входные данные #1
0.99 3
2000 3000 4000
Выходные данные #1
6
Входные данные #2
0.80 2
1000 1400
Выходные данные #2
3
Источник 2013 ACM Nordic (NCPC), Октябрь 5, Задача B