KATHTHI2 - Coin Fight

no tags 

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
David: 2022-01-07 19:17:59

The computations in this problem are very sensitive to double operations and rounding issues.
When using floating point arithmetic: (a/b)*c does not equal (a*b)/c

suhash: 2020-04-30 19:10:03

In the input constraints: "p will always contain 2 decimal places" is incorrect (verified with asserts).

Reply by cegprakash: better late than never: modified the statement to "p will always contain a maximum of 2 decimal places"

Last edit: 2023-09-08 16:37:24
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