e-olymp
favorite Saytın davamlılığını təmin etmək üçün sizin köməyinizə ehtiyacımız vardır, ətrafli məlumat üçün bannerə klikləyin

Варка овощей

prb6250 Хитрость варки овощей состоит в том, чтобы все кусочки были примерно одинакового размера. Если они не являются таковыми, то маленькие кусочки получаются слишком мягкими, а крупные недоваренными. К счастью, Вы слышали о кухонном ноже, хотя предупреждения Ваших родителей об использовании острых инструментов до сих пор находятся в Вашей голове. Поэтому Вы хотите использовать его как можно меньше. Вы можете взять кусок овоща весом w и разрезать его произвольным образом на две части с весами wleft и wright, где wleft + wright = w. Эту операцию назовем "разрез".

Зная размеры имеющихся кусков овощей, определить наименьшее количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше заданного порогового значения.

Входные данные

Начинается с действительного числа t (0.5 < t < 1) с 2 десятичными цифрами и натурального числа n (n1000). Далее идут n целых положительных весов w1, w2, ..., wn. Все веса меньше чем 106.

Выходные данные

Вывести минимальное количество разрезов, после выполнения которых соотношение между наименьшим и наибольшим куском будет больше t. Считайте, что число необходимых разрезов меньше 500. Чтобы избежать проблем с действительными числами, предположим, что оптимальный ответ для отношения t будет таким же, как и для отношения t + 0.0001.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
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
Mənbə 2013 ACM Nordic (NCPC), Октябрь 5, Задача B