To piss or not to piss P72202


Statement
 

pdf   zip

html

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