need help in this question
Pages: 12
The last time in Byteland, Chef defeated the magician in his challenge and won a gold coin.
The magician does not want to give up his coin so easily, so he gives Chef N
coins. One of them is real and the remaining N−1
are fake; all fake coins have equal weights, different from the weight of the real coin. The coins are otherwise indistinguishable.
Chef has to find the real coin by himself. To make it fair, the magician gives Chef a balance. The balance is magical — it stays balanced when the sums of weights of coins put on each side are equal, but if they are not equal, the balance tilts to a random side instead of the side with the greater sum of weights. Chef can only use this balance up to K
times; if he cannot uniquely determine which coin is the real one afterwards, he has to guess the real coin (he may make a guess in any way he wants).
If Chef uses the balance optimally, what is the minimum possible probability that he will correctly determine the real coin at the end? We are interested in the worst-case scenario where the position of the gold coin is fixed initially (but unknown to Chef).
Input
The first line of the input contains a single integer T
denoting the number of test cases. The description of T
test cases follows.
The first and only line of each test case contains two space-separated integers N
and K
.
Output
For each test case, print a single line containing one integer — the minimum probability that Chef will find the gold coin. Your output will be considered correct if its absolute error does not exceed 10−6
.
Constraints
1≤T≤2⋅10^5
1≤N≤10^18
0≤K≤10^9
Example Input
4
3 1
3 2
4 1
1 5
Example Output
0.500000
1.000000
0.500000
1.000000
Explanation
Example case 1: Chef takes two coins and puts them on the two sides of the balance. If the balance tilts, then one of these two coins is real. (Otherwise, they are both fake and Chef found the real coin; we do not consider this scenario, since it does not lead to the minimum probability.) Chef cannot use the balance any more, so he cannot determine which of these two coins is the real one. He has to guess one; this guess is correct with probability 1/2
.
Example case 2: The first use of the balance is the same as before. If the balance does not tilt, he knows the real coin. Otherwise, Chef replaces one coin on the balance. If the balance tilts again, the coin that was not replaced is the real one. Otherwise, the replaced coin is the real one.
please somebody help me in this question
The magician does not want to give up his coin so easily, so he gives Chef N
coins. One of them is real and the remaining N−1
are fake; all fake coins have equal weights, different from the weight of the real coin. The coins are otherwise indistinguishable.
Chef has to find the real coin by himself. To make it fair, the magician gives Chef a balance. The balance is magical — it stays balanced when the sums of weights of coins put on each side are equal, but if they are not equal, the balance tilts to a random side instead of the side with the greater sum of weights. Chef can only use this balance up to K
times; if he cannot uniquely determine which coin is the real one afterwards, he has to guess the real coin (he may make a guess in any way he wants).
If Chef uses the balance optimally, what is the minimum possible probability that he will correctly determine the real coin at the end? We are interested in the worst-case scenario where the position of the gold coin is fixed initially (but unknown to Chef).
Input
The first line of the input contains a single integer T
denoting the number of test cases. The description of T
test cases follows.
The first and only line of each test case contains two space-separated integers N
and K
.
Output
For each test case, print a single line containing one integer — the minimum probability that Chef will find the gold coin. Your output will be considered correct if its absolute error does not exceed 10−6
.
Constraints
1≤T≤2⋅10^5
1≤N≤10^18
0≤K≤10^9
Example Input
4
3 1
3 2
4 1
1 5
Example Output
0.500000
1.000000
0.500000
1.000000
Explanation
Example case 1: Chef takes two coins and puts them on the two sides of the balance. If the balance tilts, then one of these two coins is real. (Otherwise, they are both fake and Chef found the real coin; we do not consider this scenario, since it does not lead to the minimum probability.) Chef cannot use the balance any more, so he cannot determine which of these two coins is the real one. He has to guess one; this guess is correct with probability 1/2
.
Example case 2: The first use of the balance is the same as before. If the balance does not tilt, he knows the real coin. Otherwise, Chef replaces one coin on the balance. If the balance tilts again, the coin that was not replaced is the real one. Otherwise, the replaced coin is the real one.
please somebody help me in this question
Last edited on
@Dee123 why are you dividing into 4 equal groups.
dividing into 2 equal half's might give us minimum probability right
dividing into 2 equal half's might give us minimum probability right
If this is a Codechef problem, you should know that the Codechef adjudicators are aware of this forum, and that people use it to cheat on their contests. If you use this forum to try and cheat, you run the risk of being disqualified.
It's not me you have to convince. It's the Codechef judges. I'm just supplying information that may be relevant to you.
For N = 11 , k = 1,
The answer can be 1 / 8 by breaking in [ 4 , 4 , 3 ]
Answer can be 1 / 10 by breaking in [ 5, 5, 1 ]
It depends What "OPTIMALLY" means??
The answer can be 1 / 8 by breaking in [ 4 , 4 , 3 ]
Answer can be 1 / 10 by breaking in [ 5, 5, 1 ]
It depends What "OPTIMALLY" means??
@rish123y if you will break it in [5,5,1] then you wont be able to check for fake coin by weighing i think [4,4,3] is correct with 1/8 probability
for n=11 if we had k=3 then we could solve the problem with 1/4 probability worse case right ?
for n=11 if we had k=3 then we could solve the problem with 1/4 probability worse case right ?
closed account (1vRz3TCk)
For N = 11 , k = 1: If you split it [3,3,5] you have a 1:6 chance if it is shown to be on the scales and a 1:5 if not.
Can anyone who got AC explain what optimal means using a few examples like n=9 k=2,4,5 etc
The contest site hasn't explained the question well!!!
The contest site hasn't explained the question well!!!
When the problem says that you have to consider the worst case, it means that each time you use the scale the result will eliminate the least number of coins.
Take the site example of n=3, k=1. If you weigh two coins against each other, don't consider the case where the scale balances because that eliminates two coins. Only consider the case where the coin doesn't balance because that only eliminates one coin. Don't consider the real probability of each branch, only the probability of correctly picking the gold coin at the end of the weighing process after using an optimal strategy.
You have to figure out the optimal weighing strategy yourself. That's part of the problem.
Take the site example of n=3, k=1. If you weigh two coins against each other, don't consider the case where the scale balances because that eliminates two coins. Only consider the case where the coin doesn't balance because that only eliminates one coin. Don't consider the real probability of each branch, only the probability of correctly picking the gold coin at the end of the weighing process after using an optimal strategy.
You have to figure out the optimal weighing strategy yourself. That's part of the problem.
For n=4 and k=1 we can chose 2 coins on left side and 2 coins on right side of scale with one of them real.
This way the only possible use of balance will be made and now we have to guess out of 4 coins which is correct. This way answer should be 1/4=0.25 at the end in optimal way! Why the answer is 0.5???
This way the only possible use of balance will be made and now we have to guess out of 4 coins which is correct. This way answer should be 1/4=0.25 at the end in optimal way! Why the answer is 0.5???
closed account (1vRz3TCk)
| For n=4 and k=1 we can chose 2 coins on left side and 2 coins on right side of scale with one of them real. This way the only possible use of balance will be made and now we have to guess out of 4 coins which is correct. This way answer should be 1/4=0.25 at the end in optimal way! Why the answer is 0.5??? |
closed account (1vRz3TCk)
Using the scales only tells you if the real coin is on the scales or not, putting all the coins on the scales gives you no useful information. Putting half on the scales and half not means you can discount half the coins.
Pages: 12