USACO 2016 January

1. Promotion Counting

플래티넘으로 올라간 수를 센 후 그 수를 골드 시작수에서 제하고 골드 승급을 세는 방식으로 반복하면 된다.

a = []
with open("promote.in", "r") as f:
    for _ in range(4):
        a.append(list(map(int, f.readline().strip().split())))

ans = [0]*3

ans[2] = a[3][1] - a[3][0]
ans[1] = a[2][1] - (a[2][0] - ans[2])
ans[0] = a[1][1] - (a[1][0] - ans[1])

with open("promote.out", "w") as f:
    for res in ans:
        f.write(str(res)+"\n")

2. Angry Cows

전체 입력의 크기가 크지 않으므로, 그냥 왼쪽과 오른쪽의 연쇄폭발을 전부 시뮬레이션 하면 된다. 연쇄 폭발시 폭발에 삼켜지는 부분은 그냥 갯수만 체크하고, 마지막 폭발이 닫은 부분에서 다음 연쇄폭발이 일어나는 것만 주의하면 된다.

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

ans = 0
a.sort()

for i in range(n):
    num = 1
    exp = 1
    l = r = lm = rm = i
    l_flag = r_flag = True
    while True:
        l_cnt = r_cnt = 0
        while l-1 >= 0 and a[l-1] >= a[lm] - exp and l_flag:
            num += 1
            l -= 1
            l_cnt += 1
        while r + 1 < n and a[r+1] <= a[rm] + exp and r_flag:
            num += 1
            r += 1
            r_cnt += 1

        if l_cnt == 0:
            l_flag = False
        if r_cnt == 0:
            r_flag = False

        lm = l
        rm = r
        if l_cnt or r_cnt:
            exp += 1
        else:
            break
    ans = max(num, ans)

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

3. Mowing the Field

2차원 배열을 만들어서 적절한 값으로 초기화 한 후, 이동 경로를 시뮬레이션 하면서 이미 거쳐간 곳을 다시 지나는 경우의 최소값을 찾으면 된다.

a = []
b = [[-100]*2200 for _ in range(2200)]
with open("mowing.in", "r") as f:
    n = int(f.readline().strip())
    for _ in range(n):
        d, m = f.readline().strip().split()
        a.append((d, int(m)))

x = 1100
y = 1100
ans = float('inf')
t = 0
b[y][x] = 0
for d, l in a:
    dy = dx = 0
    if d == 'N':
        dy = - 1
    elif d == 'S':
        dy += 1
    elif d == 'E':
        dx = 1
    elif d == 'W':
        dx = -1
    for i in range(l):
        t += 1
        y += dy
        x += dx
        if b[y][x] != -100:
            ans = min(t - b[y][x], ans)
        b[y][x] = t

with open("mowing.out", "w") as f:
    if ans == float('inf'):
        f.write(str("-1\n"))
    else:
        f.write(str(ans)+"\n")