78 - ZOJ Monthly, May 2009 - H
There are n horizon streets and n vertical streets in the the city. The intervals between two parallel streets are all the same. The two ends of each street connect to other cities. (See the picture below for detail)
One day, the police received a call which said there was a thief in the center of the city. This thief was really grotesque and his behavior was totally random. That means, at each cross, the thief would choose the 4 directions in random, then went in that direction to the next cross. By the way, if the thief reached the end of the street, he would escape to other cities. The policemen were so lazy that they only wanted to wait by the stump of a tree for the appearance of hares. Finally, they decided to wait for the thief at the end of the streets. Now, they want to know how many polices are required to ensure that the possibility to catch the thief will be at least p%. Can you help these lazy people?
The input has multiple cases.
The first line of the input is a single integer T (1 <= T <= 30) which is the number of test cases. Then T consecutive test cases follow.
In each test case, there is a single line which contains one integer n and one floating number p (n is odd, 1 <= n <= 33, 0 <= p <=100). n is the number of streets in horizontal, p is the required possibility.
Results should be directed to standard output. The output of each test case should be a single integer, which is the minimum number of policemen to ensure that the possibility to catch the thief will be at least p%.
3 1 25 1 26 3 0
1 2 0
Author: FAN, Xiang
Source: ZOJ Monthly, May 2009