GCJ2011 Round 1A FreeCell Statistics

久々にGCJ2011の問題をPythonで解いてみる．
http://code.google.com/codejam/contest/dashboard?c=1145485
2011 Round1Aの問題はFreeCell Statisticsだけど，FreeCellは全く関係なくて，勝ち負けがハッキリしているゲームにおいて，Dを今日のゲーム回数，Gを今日のゲームを含む過去の総ゲーム数，Pdが今日の勝率，Pgをこれまで全ての勝率とし，今日はN回以下しかゲームをやらないとしたときに，与えられたN, Pd, Pgの組合せを成り立たせるような勝ち負けのパターンがあり得るかという問題．

考え方は意外と単純な場合分けで，

Pd == 0ならば100以外の任意のPgは成り立つ
Pd == 0なのにPg == 100はありえない
Pg != 100またはPd == pg == 100でPg != 0のときは，N以下の数d1がd1=100/gcd(100,Pd)であれば成り立つ

の分類で可能かどうかのチェックを行っていく．

#! c:/Python27/python.exe
# -*- coding: utf-8 -*-
from fractions import gcd

input  = 'gcj2011_r1a_large.in'
output = 'gcj2011_r1a_large_output.txt'

def algorithm(N, Pd, Pg):
    if Pd == 0:
        if Pg != 100: return 'Possible'
        else: return 'Broken'

    d1 = 100 / gcd(100, Pd)
    if N >= d1 and (Pg != 100 or Pg == Pd == 100) and Pg != 0: return 'Possible'
    else: return 'Broken'

if __name__ == '__main__':
    f = open(input)
    fout = open(output,'w')

    def process():
        N, Pd, Pg = ( int(x) for x in f.readline().rstrip().split(' ') )
        return algorithm(N, Pd, Pg)

    num_cases = int(f.readline().rstrip())

    for i in range(1, num_cases + 1):
        result = process()
        print "Case #" + str(i) + ":",result
        fout.write("Case #" + str(i) + ": " + str(result) + "\n")
    fout.close()
    f.close()

少しずつPythonにも慣れてきた感じがする．．．