Варіння овочів#6250
Хитрість у приготуванні овочів полягає в тому, щоб усі шматочки були приблизно однакового розміру. Якщо вони такими не є, то маленькі шматочки можуть переваритися, а великі залишитися сирими. На щастя, ви знаєте про кухонний ніж, хоча застереження ваших батьків щодо використання гострих інструментів досі у вас в голові. Тому ви хочете використовувати ніж якомога менше. Ви можете взяти шматок овоча вагою і розрізати його на дві частини з вагами w_{left} і w_{right}, де w_{left} + w_{right} = w. Цю операцію назвемо "розріз".
Знаючи розміри наявних шматків овочів, визначте мінімальну кількість розрізів, після яких співвідношення між найменшим і найбільшим шматком буде більше заданого порогового значення.
Спочатку подано дійсне число t~(0.5 < t < 1) з двома десятковими знаками і натуральне число n~(n \le 1000). Далі йдуть цілих додатних ваг w_1, w_2, ..., w_n. Усі ваги менші ніж 10^6.
Виведіть мінімальну кількість розрізів, після яких співвідношення між найменшим і найбільшим шматком буде більше . Вважайте, що число необхідних розрізів менше . Щоб уникнути проблем з дійсними числами, припустимо, що оптимальна відповідь для відношення буде такою ж, як і для відношення t + 0.0001.
Приклад 1
Приклад 2