[UVa] 10368 - Euclid's Game

題意:
(from luckycat)


解法:
對於每一步都能夠確定輸贏，而每一步最多可能有兩種操作。
假設 較大數 為 a、較小數 為 b
首先判斷 a 是否能被 b 整除，若可則贏。
若否，則考慮兩種可能。
一種可能是必須可行的，就是以 b 減 a 減到無法減為止。
另一種並不是每次都可行，就是當 a/b > 1 的時候，以 b 減 a 減到剩一次減的機會，
輪給對方。
再遞迴檢查對於每種情況是否皆可能贏。

注意:

程式碼:

	/**
	* Tittle: 10368 - Euclids Game
	* Author: Cheng-Shih, Wong
	* Date: 2015/07/21
	*/
	// include files
	#include <bits/stdc++.h>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	// declarations
	int a, b;
	// functions
	bool win( int a, int b )
	{
	if( a%b == 0 ) return true;
	bool ret = false;
	ret |= !win( b, a%b );
	if( a/b > 1 )
	ret |= !win( a%b+b, b );
	return ret;
	}
	// main function
	int main( void )
	{
	while( scanf( "%d%d", &a, &b )==2 && (a|b) ) {
	if( a < b ) swap( a, b );
	printf( "%s wins\n", win(a,b) ? "Stan":"Ollie" );
	}
	return 0;
	}

view raw 10368 - Euclid's Game.cpp hosted with ❤ by GitHub