When a guy goes into the bathroom, which urinal does he pick? Here we consider the following protocol: Each guy always chooses the urinal that puts him furthest from anyone else peeing. In case of a tie, he chooses the urinal closest to the entrance door (assume it to the left of the bathroom). Additionally, at least one empty urinal is required between any two guys. For instance, if there are five urinals, they fill up like this:

The first guy takes the left urinal, the second guy takes the right urinal, and the third guy takes the middle one. At this point, the urinals are jammed: no further guys can pee without awkwardness. But it’s pretty efficient; 60% of the urinals are used. By contrast, if there are seven urinals, they do not fill up so efficiently; less than 43% of the urinals are used:

There should be room for four guys to pee without awkwardness,
but because the third guy followed the protocol,
there are no options left for the fourth guy.
In order to increase efficiency, some walls can be placed between two urinals,
and then *independently* apply the protocol on each one of the parts, from
left to right. If we are allowed to place one wall in the last example,
efficiency would increase to more than 57%:

Placing more walls the efficiency would increase further, reaching 100% when using 6 walls. Your task in this problem is to compute the minimum number of walls necessary to reach a desired efficiency, given the number of urinals.

**Input**

Input consists of several cases. Every case has the number of urinals (between 1 and 500), and the desired percentage of efficiency (a natural number between 0 and 100).

**Output**

For every case, print the minimum number of walls needed to reach the required efficiency.

Public test cases

**Input**

1 95 2 50 2 51 5 80 5 81 7 42 7 43 7 57 7 58 7 100 15 75 65 79 67 77 100 91 500 98

**Output**

0 0 1 2 4 0 1 1 2 6 8 38 36 81 479

Information

- Author
- Albert Graells
- Language
- English
- Official solutions
- C++
- User solutions
- C++
- Event
- Setè Concurs de Programacio de la UPC - Final
- Date
- 2009-09-16