2013
11-11

# Euclid’s Game

Two players, Stan and Ollie, play, starting with two natural numbers. Stan, the first player, subtracts any positive multiple of the lesser of the two numbers from the greater of the two numbers, provided that the resulting number must be nonnegative. Then Ollie, the second player, does the same with the two resulting numbers, then Stan, etc., alternately, until one player is able to subtract a multiple of the lesser number from the greater to reach 0, and thereby wins. For example, the players may start with (25,7):
         25 7
11 7
4 7
4 3
1 3
1 0

an Stan wins.

The input consists of a number of lines. Each line contains two positive integers giving the starting two numbers of the game. Stan always starts.

For each line of input, output one line saying either Stan wins or Ollie wins assuming that both of them play perfectly. The last line of input contains two zeroes and should not be processed.

34 12
15 24
0 0


Stan wins
Ollie wins


/* @author: */
import java.util.Scanner;
public class Main{
static boolean judge(int x,int y)
{
int t;
if(x< y) {t=x;x=y;y=t;}
if(x%y==0) return true;
if(x-y< y) return !judge(y,x-y);
return true;
}

public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int m,n;
while(sc.hasNext())
{
m=sc.nextInt();
n=sc.nextInt();
if(m==0&&n==0) break;
if(judge(m,n)) System.out.println("Stan wins");
else System.out.println("Ollie wins");
}
}
}

1. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。

2. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。