11249  Game
Moderator: Board moderators
11249  Game
I solve it like this:
if(a>b)swap(a,b);
if(a*(k+2)==b) it_is_losing
else it_is_winning
Am I missing something?? or I used a wrong algorithm??
please help me.
if(a>b)swap(a,b);
if(a*(k+2)==b) it_is_losing
else it_is_winning
Am I missing something?? or I used a wrong algorithm??
please help me.
不鸣则已,一鸣惊人.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I started reading this article very recently (and then stopped for some reason, go me):
http://sps.nus.edu.sg/~limchuwe/cgt/cgt1.htm
Wythoff's game is this problem with k=0.
I solved it but it didn't "feel right". I generated first 20 winning pairs for k<=4, found pattern and just generated them all.
I, too, started with (1,k+2) pair and then tried to figure out something out of it, but then gave up. Is there a way of telling who wins for any given k,a,b? Or that limit was there just so there could be alternate solutions?
http://sps.nus.edu.sg/~limchuwe/cgt/cgt1.htm
Wythoff's game is this problem with k=0.
I solved it but it didn't "feel right". I generated first 20 winning pairs for k<=4, found pattern and just generated them all.
I, too, started with (1,k+2) pair and then tried to figure out something out of it, but then gave up. Is there a way of telling who wins for any given k,a,b? Or that limit was there just so there could be alternate solutions?
WA
I found the way to generate the piles is (n, (k+2)*n) where n is the least unused number (see code), but I'm getting WA.... maybe I'm missing something obvious.
Code: Select all
Wrong Code
Last edited by baodog on Mon Jul 30, 2007 2:19 am, edited 1 time in total.
Limit of b/a
Given two piles (a,b) with b>a, that is LOSING for k=1,
The limit of b/a as a>+infinity,
appears to go to 1+sqrt(2).
So for k=1, there is O(1) solution.
a > floor(sqrt(2)*m)
b > floor( (2+sqrt(2))*m)
for some integer m.
Not sure about higher k !!!
The limit of b/a as a>+infinity,
appears to go to 1+sqrt(2).
So for k=1, there is O(1) solution.
a > floor(sqrt(2)*m)
b > floor( (2+sqrt(2))*m)
for some integer m.
Not sure about higher k !!!
Last edited by baodog on Mon Jul 30, 2007 3:24 am, edited 2 times in total.
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
I've found this paper  http://www.wisdom.weizmann.ac.il/~fraen ... mhoff5.pdf
Essentially it says the following about our problem:
Let n=k+1, phi=(n+sqrt(n^2+4))/2, alpha=1+1/phi, beta=1+phi.
Then the losing positions are (floor(alpha*x), floor(beta*x)), for x=0,1,2,...
So, this is the O(1) solution :)
Essentially it says the following about our problem:
Let n=k+1, phi=(n+sqrt(n^2+4))/2, alpha=1+1/phi, beta=1+phi.
Then the losing positions are (floor(alpha*x), floor(beta*x)), for x=0,1,2,...
So, this is the O(1) solution :)
I misunderstand the problem
when a = 2 and b = 5 and k = 1 I consider below scenario:
first we have (2, 5) and Alic take 2 stones from b and one stone from a so we have (1, 3) then Bob knows he cannot win but He has no choice for winning (if he remove one stone from a, Alic win. If he removes at least on stone from b Alice win) So Alice is the winner but sample output differ
when a = 2 and b = 5 and k = 1 I consider below scenario:
first we have (2, 5) and Alic take 2 stones from b and one stone from a so we have (1, 3) then Bob knows he cannot win but He has no choice for winning (if he remove one stone from a, Alic win. If he removes at least on stone from b Alice win) So Alice is the winner but sample output differ
 emotional blind
 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
But you are right..s1363 wrote:I misunderstand the problem
when a = 2 and b = 5 and k = 1 I consider below scenario:
first we have (2, 5) and Alic take 2 stones from b and one stone from a so we have (1, 3) then Bob knows he cannot win but He has no choice for winning (if he remove one stone from a, Alic win. If he removes at least on stone from b Alice win) So Alice is the winner but sample output differ
2 5 is winning position
sample input also says so..
1
1 4
2 5  WINNING
2 6  LOSING
1 3  LOSING
1 4  WINNING