Facebook Hacker Cup Online Round 1a - First or Last

firstlast.py

import sys

from fractions import Fraction

# Facebook Hacker Cup Online Round 1a - First or Last
# http://www.facebook.com/hackercup/problems.php?round=144428782277390

def main():
    with open(sys.argv[1]) as fp:
        input = fp.read().split()

        n = int(input[0])
        index = 1

        for i in range(1, n+1):
            r = int(input[index])
            t = int(input[index+1])
            index += 2

            pairs = []
            for j in range(t):
                over = int(input[index])
                norm = int(input[index+1])
                index += 2
                
                diff = abs(1.0/over - 1.0/norm)
                pairs.append((over, norm, j, diff))
            
            pairs.sort(key=lambda a: a[3], reverse=True)
            
            turns = []
            for j in range(r-1):
                turns.append(pairs[j][2])
                
            j = 0
            numerator = 1
            denominator = 1
            for p in pairs:
                if p[1] < p[0] and j < r-1:
                    numerator *= p[0] - 1
                    denominator *= p[0]
                    j += 1
                else:
                    numerator *= p[1] - 1
                    denominator *= p[1]
                
            f = Fraction(numerator, denominator)
            print "%d/%d" % (f.numerator, f.denominator)

if __name__ == '__main__':
    main()

https://www.facebook.com/profile.php?id=100071023028474