Codeforces Beta Round #90
はい。
http://codeforces.com/contest/119
A. Epic Game
implementation
ざっくりと大意
・Simonは数aを受け取る、Antisimonは数bを受け取る。そしてn個の石がある。
・プレーヤーは、山から彼が受け取った定数の最大公約数と等しい石の数、および山に残された石の数をとるべきです。
・石(e,g,山には厳密により少ない石がある、1より残された、とる必要があること)の必要な数をとることができない場合、プレーヤーは失敗します。
方針のようなもの
・最大公約数を引いていくから0よりは小さくならないのかな?ならどっちのタイミングで0になったかみればOKかな??
#!/usr/bin/env python # -*- coding: UTF-8 -*- import sys, io a,b,n=map(int,raw_input().split()) ans=chk=0 def gcd(p,g): p,g=max(p,g),min(p,g) while p%g: p,g=g,p%g return g while 1: if ans%2==0: n-=gcd(a,n) else: n-=gcd(b,n) if n==0: print 0 if ans%2==0 else 1 exit() ans+=1
つい最近に最大公約数と最小公倍数は書いておいたのが役に立ってよかった。。
ほかの人の回答を見ててこれか??これが再帰か??というお手本を発見。多分コレが再帰。1240089のrng_58さんの回答。
def func(a,b,n): if n == 0: return 1 else: for i in range(a,0,-1): if a%i == 0 and n%i == 0: return 1 - func(b,a,n-i) a, b, n = raw_input().split(" ") ans = func(int(a),int(b),int(n)) print ans