All the solutions are available now on the site. I used a simple recursive solution for this one. At every step we try to eliminate half the coins. Sorry if the winProbability function looks a little obscure. I should have simply treated the root differently and the code would look a little nicer. I could have implemented a lookup table, but it wasn't necessary for my submission to finish in time.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
|
#include <iostream>
using namespace std;
double winProbability(uint64_t, uint64_t, uint64_t);
int main()
{
std::ios::sync_with_stdio(false);
uint64_t T, N, K;
cin >> T;
for (int i = 0; i < T; i++)
{
cin >> N >> K;
cout << winProbability(N, K, 0) << '\n';
}
return 0;
}
double winProbability(uint64_t unknownCoins, uint64_t remainingAttempts, uint64_t fakeCoins)
{
if (unknownCoins == 1)
return 1.0;
if (remainingAttempts == 0)
return 1/double(unknownCoins);
if (unknownCoins%2 == 1 || (unknownCoins>>1)%2 == 0 || (unknownCoins>>1) <= fakeCoins)
return winProbability(unknownCoins-(unknownCoins>>1), remainingAttempts-1, fakeCoins+(unknownCoins>>1));
else
return winProbability((unknownCoins>>1)+1, remainingAttempts-1, fakeCoins+(unknownCoins>>1)-1);
}
|
There is a special case when unknownCoins mod 2 == 0 and (unknowncoins>>1) mod 2 == 1. For example:
n = 10, k = 1. We would like to eliminate 5 coins. The only way to do this is to weigh 5 coins against 5 other coins. This only works if we have identified at least 5 fake coins already. Otherwise, we measure a group of 3 == 3 and only get to eliminate 4 coins.
n = 10, k = 1 : weigh 3 == 3 and guess 1/6
However:
n = 20, k = 2 : 1/5 because:
n = 20, k = 2 : weigh 5 == 5
n = 10, k = 1 : weigh 5 == 5 using known fakes from the last step.
n = 5, k = 0 : guess 1/5
for n = 13, k = 3: weigh 3 == 3 and the scale will balance, we're left with 7unkwown coins and 2 tries.
n = 7, k = 2 : weigh 2 == 2
n = 3, k = 1 : weigh 1 == 1
n = 2, k = 0 : No more tries, guess 1/2.