USACO 2016 February

1. Milk Pails

X,Y의 수가 1000이하로 작으므로 M에 들어갈수 있는 조합을 전부 탐색하면 된다.

with open("pails.in", "r") as f:
    x, y, m = map(int, f.readline().strip().split())

ans = 0
for i in range(m//x+1):
    for j in range(m//y+1):
        if x*i + y*j <= m:
            ans = max(ans, x*i + y*j)

with open("pails.out", "w") as f:
    f.write(str(ans)+"\n")

2. Circular Barn

입력이 크지 않아서 리스트를 회전시키면서 전부 탐색했다. 실제 리스트를 회전시키지 않고 a[j%n]의 형태로 인덱스만 탐색하는 방법도 있다.

a = []
with open("cbarn.in", "r") as f:
    n = int(f.readline().strip())
    for _ in range(n):
        a.append(int(f.readline().strip()))

ans = float("inf")

for i in range(n):
    cur = 0
    for j in range(1, n):
        cur += a[j]*j
    ans = min(ans, cur)
    l = a.pop()
    a.insert(0, l)

with open("cbarn.out", "w") as f:
    f.write(str(ans)+"\n")

3. Load Balancing

N의 값은 작으나 좌표의 값이 크므로 좌표를 일일히 스캔할수는 없다. 각각의 소의 위치를 기준으로 x, y를 가로지르는 펜스를 구성하고 사분면에 해당하는 소의 수를 세는 방식으로 구성하면 100*100개의 조합에 대해서만 각각의 소가 어떤 사분면에 해당하는지 세면 된다.

xpos = []
ypos = []
with open("balancing.in", "r") as f:
    n, b = map(int, f.readline().strip().split())
    for _ in range(n):
        x, y = map(int, f.readline().strip().split())
        xpos.append(x)
        ypos.append(y)

ans = n # 한점에 모든 소가 모여있는 경우가 최악의 경우
for x in xpos:
    for y in ypos:
        xdiv = x+1
        ydiv = y+1
        d1 = d2 = d3 = d4 = 0
        for i in range(n):
            if xpos[i] < xdiv and ypos[i] > ydiv:
                d1 += 1
            elif xpos[i] > xdiv and ypos[i] > ydiv:
                d2 += 1
            elif xpos[i] < xdiv and ypos[i] < ydiv:
                d3 += 1
            else:
                d4 += 1
        m = max(d1, d2, d3, d4)
        ans = min(m, ans)

with open("balancing.out", "w") as f:
    f.write(str(ans)+"\n")