So I am kind of stuck in a problem related to game theory!

Any help will be appreciated!

**Problem:**

Anjali and Vaibhavi are playing a game with a pile of N coins. In this game, Anjali and Vaibhavi make their respective moves

alternately, starting with Anjali.

In a turn, a player can remove x coins from the pile if x satisfies: 1<= x <= n

x & n = 0 (bitwise and of x and n is 0.)

where 'n' is the size of the pile in the current turn.

The player who is unable to make a move loses the game.

Given the initial number of coins in a pile, determine who would win the game.

Assume that both the players play optimally throughout the game.

**Input Format:**

First-line denotes t i.e. number of test cases

Next ‘t’ lines contain n where n is the number of coins in the pile as the game commences.

**Output Format:**

For each test case, print the winning player’s name (case sensitive).

**Constraints:**

1 <= t <= 10^5

1 <= n <= 10^18

**Sample Input:**

5

1

2

3

4

5

**Sample Output:**

Vaibhavi

Anjali

Vaibhavi

Anjali

Anjali

**Explanation:**

1st test case: Anjali can't make a move so Vaibhavi wins.

2nd test case: Anjali can remove 1 coin because 1&2=0 then 1 coin left so Vaibhavi can't make a move so Anjali wins.

3rd test case: Anjali can't make a move, so Vaibhavi wins.

And so on.

Auto comment: topic has been updated by nihal2001 (previous revision, new revision, compare).Auto comment: topic has been updated by nihal2001 (previous revision, new revision, compare).Auto comment: topic has been updated by nihal2001 (previous revision, new revision, compare).Where did you get this problem?

This problem was asked in a programming contest conducted on 1st march by coding ninjas!

any help will be appreciated!

I think it's got something with the segments of 1s and 0s in the binary representation of n, but I can't really figure it out.

Have you checked this thread though? https://discuss.codechef.com/t/coding-ninjas-problem-help-in-approach/86320/3

I think this approach kinda make sense.

Really Interesting problem for me!

Note that this problem only relate to binary representation of n.

If Anjali lose, we assign $$$f(n) = 0$$$, otherwise, $$$f(n - x) = 0$$$ for some $$$1 \leq x \leq n, x \And n = 0$$$. and we assign f(n) = $$$n - x$$$ for smallest such x.

we can use following brute force code to compute small f(n). and see the case $$$f(n) = 0$$$

`0`

,`111`

,`11001`

,`1101101`

,`110000111100111`

)I claim that Anjali Win for T, and Vaibhavi win for FFirst it is easy to see that if n is odd, then $$$f(n) = f(n/2)$$$, so we may assume n is even.

Secondly,

`101010010 -> 011000110`

), otherwise we can move the rightmost 1 to the end, and the rest pair by pair(example:`101010110 -> 011001101`

)Finally, Vaibhavi win for $$$n = 0$$$ which belongs to F, end the prove.

Thanks for the reply, first of all! i was able to get your bruteforce solution , but your proof of the second part assuming cases F and t is not clear to me!

it would be very helpful if you could explain it more clearly !

My comments document my entire thought process on this unfamiliar issue. No offense is meant in any way.

If we are in the case of F, at which point 1's appear in pairs adjacent to each other, at which point no reasonable x will change the value of a 1 in an odd position, we observe that the leftmost changing bit necessarily happens to be a 1 in an even position that becomes a 0, which causes it to become T

If we are in the case of T, we can can make the original non-adjacent 1s next to each other, and if there is an extra 1 throw him to the far right.

Translated with www.DeepL.com/Translator (free version)

In this type of problems (Being Clueless) , I follow the below steps :

1. I generally do brute force for some small numbers.

So,I have manually observed that,for

`N = 1,3,6,7,12,13,15,24`

the answer is`"Vaibhavi"`

for this problem.2. I search that sequence in OEIS.

For those who don't know aboot OEISSee this !

3.Most of the times, I get a idea / formula about that pattern from OEIS. Like in this problem, the idea is Numbers in whose binary expansion there are no 1-runs of odd length followed by a 0 to their right.

4.I write code following that idea. For this problem, Here is my code.

5.I submit.

P.S : This trick does not work always.

Thank You !SpoilerHope this helps.

Hey, thanks for the reply! I didn't noticed that this can also be decoded using OEIS. but i was looking some more kind of proof of this.

You are welcome.