Facebook Hacker Cup 2011 Round 1A (reprise) Wine Tasting [Solved]


01    ”’
02    @author Wonjohn Choi
03    @problemTitle Wine Tasting
04    @problemLink http://www.facebook.com/hackercup/problems.php/?round=123802894356576
05    @lang Python 31
06    ”’
07    inFile = open(“wine_tasting.txt”, “r”)
08    outFile = open(“wine_tasting_output.txt”,”w”)
09    nCase = int(next(inFile))
10
11    import math
12    for line in inFile:
13        m, n = tuple(map(int,line.split(‘ ‘)))
14        #m-n wrong
15        wrongWays = [0]*(m-n+1)
16        wrongWays[0] = 1
17        for i in range(1,len(wrongWays)):
18            wrongWays[i]=math.factorial(i)
19            for j in range(1, i+1):
20                wrongWays[i]-=math.factorial(i)/math.factorial(j)/math.factorial(i-j)*wrongWays[i-j]
21
22        answer = 0
23        for i in range(n,m+1):
24            answer+=math.factorial(m)/math.factorial(i)/math.factorial(m-i) * wrongWays[m-i]
25        outFile.write(str(int(answer%1051962371)))
26        outFile.write(‘\n’)
27    outFile.close()
28    inFile.close()


Leave a Reply

Your email address will not be published. Required fields are marked *