We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Thanks but I still can't see how you determine the winner without doing the operations. I think the last paragraph is the part I'm having trouble understanding. For example the popcounts of 6 and 5 are both 2, so how did popcount(6 - 1) tell you # of 1s before last 1 and # of 0s after last 1? (1 '1' before the first one and 61 '0's after the last '1'). I can't figure out how you determine the winner without doing the operations (right shifting by 1 or clearing left most bit).
This update (Update: If they set counter to 1, Richard wins, because its Louise' turn and she cannot make a move.) also doesn't make sense to me. If Louise can't make a move and n does not change then richard can't make a move either, and nobody ever makes a valid move, so by the rules of the game there should be no winner..?
Here is my submission so you can see that I understand how the operations look in binary, I just still dont get how popcount(n - 1)&1 tells you the winner.
int main(void)
{
size_t t;
scanf("%zu", &t);
while (t--)
{
uint64_t n;
scanf("%lu", &n);
uint64_t player = 0;
while (n != 1) {
uint64_t v;
if ((v = n & (n - 1))) {
v = __builtin_clzl(n);
n ^= 0x8000000000000000 >> v;
}
else {
n >>= 1;
}
player ^= 1;
}
printf("%s\n", player == 0 ? "Richard" : "Louise");
}
return 0;
}
__builtin_clzl(n) gives the # of leading 0's before leftmost set bit
Counter game
You are viewing a single comment's thread. Return to all comments →
Thanks but I still can't see how you determine the winner without doing the operations. I think the last paragraph is the part I'm having trouble understanding. For example the popcounts of 6 and 5 are both 2, so how did popcount(6 - 1) tell you # of 1s before last 1 and # of 0s after last 1? (1 '1' before the first one and 61 '0's after the last '1'). I can't figure out how you determine the winner without doing the operations (right shifting by 1 or clearing left most bit).
This update (Update: If they set counter to 1, Richard wins, because its Louise' turn and she cannot make a move.) also doesn't make sense to me. If Louise can't make a move and n does not change then richard can't make a move either, and nobody ever makes a valid move, so by the rules of the game there should be no winner..?
Here is my submission so you can see that I understand how the operations look in binary, I just still dont get how popcount(n - 1)&1 tells you the winner.
__builtin_clzl(n) gives the # of leading 0's before leftmost set bit