SP19139 BOILING - Boiling Vegetables

The trick to boiling vegetables is to make sure all

The input starts with a floating point number T with 2 decimal digits, 0.5 < T < 1, and a positive integer N 1 000. Next follow N positive integer weights w $ _{1} $ , w $ _{2} $ , ..., w $ _{N} $ . All weights are less than 10 $ ^{6.} $

Output the minimum number of cuts needed to make the ratio between the resulting minimum weight piece and the resulting maximum weight piece be above T. You may assume that the number of cuts needed is less than 500. To avoid issues with floating point numbers, you can assume that the optimal answer for ratio T is the same as for ratio T + 0.0001.