KATHTHI2 - Coin Fight
Sathish and Kathiresan are known for Coin Fight. Kathiresan kept on tossing a biased coin repeatedly. Then he decided to solve the following problem.
Find the number of tosses for which the probability of getting exactly K heads is maximum. In case of a tie, return the minimum number of tosses.
In other words, find the minimum n such that probability (exactly K heads with n tosses) >= probability (exactly K heads with m tosses) for any m!=n.
Input:
The first line consists of an integer t, the number of test cases. For each test case you are given an integer K, the number of heads required and a float p, the probability to get a head when the coin is tossed.
Output:
For each test case find the number of tosses required as defined.
Input Constraints:
1 <= t <= 100
1 <= K <= 100
0.00 < p <= 1.00
p will always contain a maximum of 2 decimal places
Sample
Input: 3 5 1.00 1 0.50 2 0.30 Output: 5 1 6
hide comments
vl4deee11:
2024-10-07 23:36:37
nice problem |
|
David:
2022-01-07 19:17:59
The computations in this problem are very sensitive to double operations and rounding issues.
|
|
suhash:
2020-04-30 19:10:03
In the input constraints: "p will always contain 2 decimal places" is incorrect (verified with asserts).
|
|
smso:
2019-04-16 08:14:25
Direct computation of probability with binomial results in either overflow or precision problem. Use the mode instead. |
|
vaibhav2303:
2018-11-04 21:21:53
Why is the answer for {k=100, p=0.2} [spoiler] and not [spoiler] Last edit: 2019-03-11 23:45:14 |
|
nadstratosfer:
2017-10-02 11:42:22
AC'd via shotgun debugging. Hopefully one day I'll understand why my solution works ;) |
Added by: | cegprakash |
Date: | 2016-10-22 |
Time limit: | 3s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: BF GOSU |