10368  Euclid's Game
Moderator: Board moderators
10368  Euclid's Game
hi!
i've tryed several times to solve this.... but i've still having WA...
that's my code... can anyone help me???
aahhhh... it's in JAVA...
[java]
import java.io.*;
import java.util.StringTokenizer;
class Main
{
static String ReadLn ()
{
StringBuffer s = new StringBuffer("");
int car = 1;
try{
do{
car = System.in.read();
if ((car < 0)  (car == '\n')) break;
else s.append((char) car);
} while(car > 0);
} catch (IOException e){return (null);}
if (car < 0)return null;
String aux=s.toString();
return aux.substring(0,aux.length()1);
}
public static void main (String[] args)
{
Main c1= new Main();
c1.procesar();
}
void procesar()
{
StringTokenizer st = new StringTokenizer(ReadLn());
int n=Integer.parseInt(st.nextToken());
int m=Integer.parseInt(st.nextToken());
int men,may;
while (!(n==0 && m==0))
{
if(n<m)
{
men=n;
may=m;
}
else
{
men=m;
may=n;
}
boolean s=true;
while (may < men*2)
{
may=maymen;
n=men;
m=may;
if(m<n)
{
men=m;
may=n;
}
s=!s;
}
st = new StringTokenizer(ReadLn());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
if(m==0 && n==0)
{
if(s)System.out.print("Stan wins");
else System.out.print("Ollie wins");
}
else
{
if(s)System.out.println("Stan wins");
else System.out.println("Ollie wins");
}
}
}
}
[/java]
i've tryed several times to solve this.... but i've still having WA...
that's my code... can anyone help me???
aahhhh... it's in JAVA...
[java]
import java.io.*;
import java.util.StringTokenizer;
class Main
{
static String ReadLn ()
{
StringBuffer s = new StringBuffer("");
int car = 1;
try{
do{
car = System.in.read();
if ((car < 0)  (car == '\n')) break;
else s.append((char) car);
} while(car > 0);
} catch (IOException e){return (null);}
if (car < 0)return null;
String aux=s.toString();
return aux.substring(0,aux.length()1);
}
public static void main (String[] args)
{
Main c1= new Main();
c1.procesar();
}
void procesar()
{
StringTokenizer st = new StringTokenizer(ReadLn());
int n=Integer.parseInt(st.nextToken());
int m=Integer.parseInt(st.nextToken());
int men,may;
while (!(n==0 && m==0))
{
if(n<m)
{
men=n;
may=m;
}
else
{
men=m;
may=n;
}
boolean s=true;
while (may < men*2)
{
may=maymen;
n=men;
m=may;
if(m<n)
{
men=m;
may=n;
}
s=!s;
}
st = new StringTokenizer(ReadLn());
n=Integer.parseInt(st.nextToken());
m=Integer.parseInt(st.nextToken());
if(m==0 && n==0)
{
if(s)System.out.print("Stan wins");
else System.out.print("Ollie wins");
}
else
{
if(s)System.out.println("Stan wins");
else System.out.println("Ollie wins");
}
}
}
}
[/java]
10368  Trying to figure out best strategy!
This seems like a very simple game, but I am getting stuck in finding a perfect strategy that both Stan and Ollie will use to win. If i always subtract the largest value made by multiples of the smaller number, from the bigger value of two numbers, it seems that I get the right result for some test cases. However, I think I am missing the winning strategy that both Stan and Ollie should use.... does somebody know the winning strategy we use at each step of the game? help appreciated...[cpp][/cpp]

 New poster
 Posts: 10
 Joined: Tue Oct 01, 2002 11:37 pm

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
solved euclid's game finally
I thought about it...
i got it to work with one while loop...
basically, just needed to find the strategy for stan.
thanks guys for help
i got it to work with one while loop...
basically, just needed to find the strategy for stan.
thanks guys for help

 New poster
 Posts: 10
 Joined: Tue Nov 26, 2002 4:19 pm
10368 Euclids Game...
How do i solve this problem?.. Any clues.....
And also how do i solve related problems....
For example.. this problem.....
There is a pile of sticks.... say K sticks...
There are 2 players.......
The players pick at alternate turns....
Each player can pick a maximum of all but one stick... and a minimum of 1
Suppose a player picks p sticks in his turn.. the next player can pick any number of sticks between 1 and 2*p^2
What is the optimal game strategy.........
Is it a Nim Game?
And also how do i solve related problems....
For example.. this problem.....
There is a pile of sticks.... say K sticks...
There are 2 players.......
The players pick at alternate turns....
Each player can pick a maximum of all but one stick... and a minimum of 1
Suppose a player picks p sticks in his turn.. the next player can pick any number of sticks between 1 and 2*p^2
What is the optimal game strategy.........
Is it a Nim Game?
You have to find some recursion in the problem and then solve it with recursive procedure or dynamic programming.
Typically, you can decompose problem into 'positions'. (in this problem, positions can be pairs of numbers) For every position you can say if it is winning (ie. there exists a move, that leads to the losing position) or losing (ie. all possible moves lead to winning position) for the player who should make a move.
You know some elementary winning positions from problem statement. Your task is to determine type of position given in input.
About problem you have posted. You didn't say what is a goal of the game (to have maximum number of sticks at the end of the game?, to take the last stick?), so it is hard to say, what is the optimal strategy
Typically, you can decompose problem into 'positions'. (in this problem, positions can be pairs of numbers) For every position you can say if it is winning (ie. there exists a move, that leads to the losing position) or losing (ie. all possible moves lead to winning position) for the player who should make a move.
You know some elementary winning positions from problem statement. Your task is to determine type of position given in input.
About problem you have posted. You didn't say what is a goal of the game (to have maximum number of sticks at the end of the game?, to take the last stick?), so it is hard to say, what is the optimal strategy
You can solve this problem by a simple recurtion and
the same mathod can be used in other programs similer
to this(847). Follow the following instructions to solve it:
define stan and ollie as 1 and 0 simaltaenuously. U can take
another things but this make the program easier. Now make a
simple recurtion for finding the winner with player(1=stan),
big number, small numer. run a for loop for returning
0 or 1(ollie or stan). The structure of the recursion will be
like:
int wins(int player, long big, long small)
{
long t;
if(big < small)
{
t = big;
big = small;
small = t;
}
if(!(big%small))
return player;
for(long i=1; i*small<big; i++)
{
if(wins(!player, small, big  (small*i)) == player )
return player;
}
return !player;
}
but this program will give u TLE!.
To avoid this problem use prunning to make it faster.
Do a simple change in the loop
for(long i=big/small; i>=1; i)
this will cut unnecessary calculation of ur program.
hope can help.
the same mathod can be used in other programs similer
to this(847). Follow the following instructions to solve it:
define stan and ollie as 1 and 0 simaltaenuously. U can take
another things but this make the program easier. Now make a
simple recurtion for finding the winner with player(1=stan),
big number, small numer. run a for loop for returning
0 or 1(ollie or stan). The structure of the recursion will be
like:
int wins(int player, long big, long small)
{
long t;
if(big < small)
{
t = big;
big = small;
small = t;
}
if(!(big%small))
return player;
for(long i=1; i*small<big; i++)
{
if(wins(!player, small, big  (small*i)) == player )
return player;
}
return !player;
}
but this program will give u TLE!.
To avoid this problem use prunning to make it faster.
Do a simple change in the loop
for(long i=big/small; i>=1; i)
this will cut unnecessary calculation of ur program.
hope can help.

 New poster
 Posts: 1
 Joined: Thu Apr 01, 2004 11:02 am
10368
does somebody have test cases?
what is wrong of that code?
thanks
#include <iostream>
using namespace std;
int main(){
int a,b,c;
cin>>a;
cin>>b;
while ((a!=0)  (b!=0)){
if (a<b) {c=a;a=b;b=c;}
int i=0;
while (b!=0) { i++;
if (a>=2*b) {b=0;} else {a=ab;}
if (a<b) {c=a;a=b;b=c;}
}
if (i%2==1) cout<<"Stan wins"<<endl;
else cout<<"Ollie wins"<<endl;
cin>>a;cin>>b;
}
}
what is wrong of that code?
thanks
#include <iostream>
using namespace std;
int main(){
int a,b,c;
cin>>a;
cin>>b;
while ((a!=0)  (b!=0)){
if (a<b) {c=a;a=b;b=c;}
int i=0;
while (b!=0) { i++;
if (a>=2*b) {b=0;} else {a=ab;}
if (a<b) {c=a;a=b;b=c;}
}
if (i%2==1) cout<<"Stan wins"<<endl;
else cout<<"Ollie wins"<<endl;
cin>>a;cin>>b;
}
}
what ever you have done is general minmax code. the minmax theorem is really nice and it is the only possible solution in most of the cases. however some games like this also have a nice closed form solution.
your method of pruning (btw, changing the order of the loops is not called pruning)
is just lucky. that is just a clue to others who might wanna try this problem.
bye
abi
your method of pruning (btw, changing the order of the loops is not called pruning)
is just lucky. that is just a clue to others who might wanna try this problem.
bye
abi

 New poster
 Posts: 3
 Joined: Thu Feb 24, 2005 1:32 am
10368
Could someone give me some inputs/outputs to test my program? I'm getting WA. Please help me.
try these..
Input:
Output
Hope it helps..
btw: I think it would be better if you gave a brief description of your algorithm. In that way everyone gets to learn and that should be the bottom line.
Code: Select all
1111111111 2
1 1
36 20
28 20
25 7
4 4
8 4
12 8
20 8
34 12
15 24
0 0
Code: Select all
Stan wins
Stan wins
Stan wins
Ollie wins
Stan wins
Stan wins
Stan wins
Ollie wins
Stan wins
Stan wins
Ollie wins
btw: I think it would be better if you gave a brief description of your algorithm. In that way everyone gets to learn and that should be the bottom line.

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
I think the brief description can come after confirming that it wasn't just typos and silly mistakes! =)
Check out http://www.algorithmist.com !
Re: 10368  Euclid's Game
Be aware that the input numbers doesn't fit in 32 bit signed integer.
I've receive AC only when I changed the solution to 64 bit signed integer.
I've receive AC only when I changed the solution to 64 bit signed integer.

 Experienced poster
 Posts: 145
 Joined: Thu Aug 14, 2003 8:42 am
 Location: Mountain View, California
 Contact:
Re: 10368  Euclid's Game
I think this problem is minmax problem with alphabeta pruning (http://en.wikipedia.org/wiki/Alphabeta_pruning).
Have you ever...
 Wanted to work at best companies?
 Struggled with interview problems that could be solved in 15 minutes?
 Wished you could study realworld problems?