Need Help In Game Theory Problem??

Revision en4, by nihal2001, 2021-03-04 11:34:47

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.

Tags #game-theory, grundy

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English nihal2001 2021-03-04 11:34:47 2 Tiny change: 'aints:**\n1 <= t <' -> 'aints:**\n\n1 <= t <'
en3 English nihal2001 2021-03-04 11:32:53 54
en2 English nihal2001 2021-03-04 11:29:27 8
en1 English nihal2001 2021-03-04 11:27:08 1367 Initial revision (published)