2009년 예선이 눈앞으로 다가온 가운데, 졸려서 꾸벅꾸벅 감기는 눈을 부여잡고 돌았다. 올해 라운드 1은 다른 것 없이 파이썬만 가지고 해야 할 위기이기 때문에.. 파이썬으로 돌았다. C 빼곤 A, B 둘다 왕 평이함.
Problem A: Minimum Scalar Product
걍 그리디.
lang:py
f = open("d:\\incoming\\a-large-practice.in", "r")
o = open("d:\\incoming\\a-large-practice.out", "w")
cc = int(f.readline())
print cc, "cases"
for c in range(cc):
f.readline()
a = map(int, f.readline().split())
b = map(int, f.readline().split())
a.sort()
b.sort()
ret = 0
for i in range(len(a)):
ret += a[i] * b[-i-1]
o.write("Case #%d: %d\n" % (c+1, ret))
o.close()
Problem B: Milkshakes
모든 milkshake 를 unmalted 인 상태에서, 반드시 malted 여야 하는 flavor 들만 malt 시킨다. 이 프로세스가 converge 하면 그것이 답, 아니면 GG. malted 는 한 사람이 항상 한 가지만 좋아하기 때문에 반드시 malted 여야 하는 flavor 들이 쉽게 정해짐.
졸려서 구현이 구림
lang:py
inp = open("d:\\incoming\\b-large-practice.in", "r")
outp = open("d:\\incoming\\b.out", "w")
cc = int(inp.readline())
for c in range(cc):
n = int(inp.readline())
m = int(inp.readline())
l = [[] for i in range(m)]
for i in range(m):
likes = map(int, inp.readline().split())
t = likes[0]
for j in range(t):
a, b = likes[j*2+1:j*2+3]
a -= 1
l[i].append((a,b))
satisfied = False
malted = [0] * n
escape = False
while not satisfied and not escape:
satisfied = True
for i in range(m):
mi = -1
good = False
for flavor, malt in l[i]:
if malt == malted[flavor]:
good = True
break
if malt == 1:
mi = flavor
if not good:
satisfied = False
if mi == -1:
escape = True
break
else:
malted[mi] = 1
res = "Case #%d: " % (c+1)
if not satisfied:
res += "IMPOSSIBLE"
else:
res += " ".join(map(str, malted))
outp.write(res + "\n")
print res
outp.close()
Problem C: Numbers
(3 + sqrt(5))^n 의 정수부의 마지막 3자리를 구하는 문제. small 은 bc 나 calc 로 풀라고 하는데, 2.6 부터 포함된 decimal 모듈을 이용해 easy ride.. 하드는 아이디어는 알겠는데 졸리고 귀찮아서 전개하기 싫다. 나중에
lang:py
from decimal import *
getcontext().prec = 200
inp = open("d:\\incoming\\c-small-practice.in", "r")
outp = open("d:\\incoming\\c.out", "w")
cc = int(inp.readline())
three = Decimal(3)
five = Decimal(5)
m = three + five.sqrt()
for c in range(cc):
n = int(inp.readline())
last = "000" + str(m**n).split(".")[0]
last = last[-3:]
print "Case #%d: %s" % (c+1, last)
outp.write("Case #%d: %s\n" % (c+1, last))
outp.close()
