UVA 847 - A Multiplication Game

题目链接

题意：一个数一開始是1，每次轮流乘2-9，谁先大于n谁就赢，问谁胜

思路：博弈，找出必胜态。2-9为stan，10-18为ollie,19-162为stan...发现都是乘2乘9交替

代码：

#include <stdio.h>

#include <string.h>

#include <math.h>

long long n;

bool judge(long long n) {

	long long a = 1, b = 1;

	int flag = 1;

	while (1) {

		if (flag) {

			a = b + 1;

			b *= 9;

			if (a <= n && n <= b) return true;

  			flag = 0;

    	}

  		else {

  			a = b + 1;

  			b *= 2;

  			if (a <= n && n <= b) return false;

  			flag = 1;

  		}

 	}

}

int main() {

	while (~scanf("%lld", &n)) {

		printf("%s wins.\n", judge(n)?

"Stan":"Ollie");

 	}

	return 0;

}