10368 - Euclid's Game

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10368 - Euclid's Game

Post by nicopadu »

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=may-men;
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]
acolovic
New poster
Posts: 2
Joined: Sat Oct 12, 2002 5:05 am
Location: USA

10368 - Trying to figure out best strategy!

Post by acolovic »

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

Post by Santiago Zanella »

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:

Post by Stefan Pochmann »

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

Post by acolovic »

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
jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

10368 Euclids Game...

Post by jaivasanth »

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:

Post by marian »

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

Post by Jalal »

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: 8)

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. :wink:
kaiser-sose
New poster
Posts: 1
Joined: Thu Apr 01, 2004 11:02 am

10368

Post by kaiser-sose »

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

Post by abishek »

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
Rolando_de_Gilead
New poster
Posts: 3
Joined: Thu Feb 24, 2005 1:32 am

10368

Post by Rolando_de_Gilead »

Could someone give me some inputs/outputs to test my program? I'm getting WA. Please help me.
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

try these..

Post by sohel »

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:

Post by Larry »

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

Post by Leonid »

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

Post by DD »

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.
Post Reply

Return to “Volume 103 (10300-10399)”