Need help with Game Theory !

Revision en1, by SarvagyaAgarwal, 2016-01-06 04:14:03

Problem Statement:
On the eve of New Year in Dholakpur, Chota Bheem and Chutki are playing a game, described as follows.

There are two plates full of Laddus. Both can eat L (L>=1) laddus from any one plate or L laddus from both the plates in each step. They play the game alternatively and the last one to eat the laddu will be the winner.

As Chota Bheem wants to impress Chutki, he wants to make Chutki the winner. You have to help Chota Bheem in deciding who should play first.

Constraints:
1 <= Test cases(T) <= 105
0 <= a,b <= 106

As i could only come up with an O(TN2) approach which used O(N2) space(where N is max(a,b)), I wrote a brute force to see if any pattern existed but failed to find one.
What am i missing here ?
Thanks!
P.S : You can find the problem statement here.

Tags game-theory, dp, hackerearth

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English SarvagyaAgarwal 2016-01-06 04:16:43 10 Tiny change: 'deone.com/243T7t) to see i' -> 'deone.com/7bAAOK) to see i'
en1 English SarvagyaAgarwal 2016-01-06 04:14:03 1012 Initial revision (published)