## 10368 - Euclid's Game

Moderator: Board moderators

New poster
Posts: 4
Joined: Wed Sep 18, 2002 2:16 am

### 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
{
{
StringBuffer s = new StringBuffer("");
int car = -1;
try{
do{
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()
{
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=may-men;
n=men;
m=may;
if(m<n)
{
men=m;
may=n;
}
s=!s;
}

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]

acolovic
New poster
Posts: 2
Joined: Sat Oct 12, 2002 5:05 am
Location: USA

### 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]

Santiago Zanella
New poster
Posts: 10
Joined: Tue Oct 01, 2002 11:37 pm
Did you try drawing a decision tree? If you didn

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Santiago Zanella wrote:do you know you only need a winning strategy for Stan, don't you?
Does that make the solution easier somehow?

acolovic
New poster
Posts: 2
Joined: Sat Oct 12, 2002 5:05 am
Location: USA

### solved euclid's game finally

i got it to work with one while loop...
basically, just needed to find the strategy for stan.
thanks guys for help

jaivasanth
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?

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:
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

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
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.

kaiser-sose
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=a-b;}
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;
}
}

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
what ever you have done is general min-max code. the min-max 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

New poster
Posts: 3
Joined: Thu Feb 24, 2005 1:32 am

### 10368

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### try these..

Input:

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
``````
Output

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
``````
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.

Larry
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! =)

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

### 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.

DD
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 alpha-beta pruning (http://en.wikipedia.org/wiki/Alpha-beta_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 real-world problems?
If so, you need to read Elements of Programming Interviews.