BOILING - Boiling Vegetables

The trick to boiling vegetables is to make sure all pieces are about the same size. If they are not, the small ones get too soft or the large ones get undercooked (or both). Fortunately, you have heard of the kitchen knife, but your parents’ warnings of using sharp instruments still echoes in your head. Therefore you better use it as little as possible. You can take a piece of a vegetable of weight w and cut it arbitrarily in two pieces of weight wleft and wright, where wleft + wright = w. This operation constitutes a “cut”. Given a set of pieces of vegetables, determine the minimum number of cuts needed to make the ratio between the smallest and the largest resulting piece go above a given threshold.

Input

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 w1, w2, ..., wN. All weights are less than 106.

Output

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.

Example

Input 1:
0.99 3
2000 3000 4000

Output 1:
6
Input 2:
0.80 2
1000 1400

Output 2:
3

Added by:Fernando Fonseca [ITA]
Date:2014-03-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:NCPC 2013 (under CC BY-SA 3.0)

hide comments
2017-10-11 10:17:38
4
2014-03-26 21:37:05 Jacob Plachta
They don't need to be integers.
2014-03-24 16:47:42 Piyush Kumar
do wleft and wright need to be integers after each cut?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.