12 Mar 2020
|
Python
USACO
PS
USACO 2016 US open (Bronze)
1. Diamond Collector
시작과 끝에 두개의 포인터를 두고 크기 차이가 k 이하면 뒤쪽을 전진, 이상이되면 앞쪽을 전진하는 방법으로 풀었다.
a = []
with open("diamond.in", "r") as f:
n, k = map(int, f.readline().strip().split())
for _ in range(n):
a.append(int(f.readline().strip()))
a.sort()
f = l = 0
tot = 1
ans = 0
while True:
if f == n or l == n-1:
break
if a[l+1] - a[f] <= k:
l += 1
tot += 1
else:
f += 1
tot -= 1
ans = max(ans, tot)
with open("diamond.out", "w") as f:
f.write(str(ans)+"\n")
2. Bull in a China Shop
입력이 크지 않아서 리스트를 회전시키면서 전부 탐색했다.
실제 리스트를 회전시키지 않고 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")
11 Mar 2020
|
Python
USACO
PS
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")
10 Mar 2020
|
Python
USACO
PS
USACO 2016 January
플래티넘으로 올라간 수를 센 후 그 수를 골드 시작수에서 제하고 골드 승급을 세는 방식으로 반복하면 된다.
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")
09 Mar 2020
|
Python
USACO
PS
USACO 2015 December
1. Fence Painting
입력 크기가 작아서 그냥 집합으로 만들어서 합집합으로 처리했다.
with open("paint.in", "r") as f:
a, b = map(int, f.readline().strip().split())
c, d = map(int, f.readline().strip().split())
ans = len(set(range(a, b)) | set(range(c, d)))
with open("paint.out", "w") as f:
f.write(str(ans)+"\n")
2. Speeding Ticket
마찬가지로 입력크기가 작아서 그냥 리스트에 속도를 넣은 후 전부 탐색했다.
r = []
b = []
with open("speeding.in", "r") as f:
n, m = map(int, f.readline().strip().split())
for _ in range(n):
length, lim = map(int, f.readline().strip().split()) # length, limit
r += [lim]*length
for _ in range(m):
length, lim = map(int, f.readline().strip().split()) # length, speed
b += [lim]*length
ans = 0
for i in range(100):
if r[i] < b[i]:
ans = max(b[i]-r[i], ans)
with open("speeding.out", "w") as f:
f.write(str(ans)+"\n")
3. Contaminated Milk
각각의 사람이 먹은 우유의 종류별 최소 시간을 저장한 배열을 만든 후, 해당 배열에서 아픈 사람이 아프기 시작한 시점 전에 먹은 우유의 종류를 골라낸 이후, 해당 우유를 몇명이 섭취했는지 최대값을 구하면 된다.
sick = []
with open("badmilk.in", "r") as f:
n, m, d, s = map(int, f.readline().strip().split())
b = [[200]*m for _ in range(n)]
for _ in range(d):
p, milk, t = map(int, f.readline().strip().split())
b[p-1][milk-1] = min(b[p-1][milk-1], t)
for _ in range(s):
p, t = map(int, f.readline().strip().split()) # person, sick_time
sick.append([p-1, t])
ans = 0
res = [0]*m
for p, t in sick:
for i in range(m):
if b[p][i] < t:
res[i] += 1
for r in range(m):
if res[r] == s:
cnt = 0
for i in range(n):
if b[i][r] != 200:
cnt += 1
ans = max(ans, cnt)
with open("badmilk.out", "w") as f:
f.write(str(ans)+"\n")
08 Mar 2020
|
Python
USACO
PS
USACO 2015 US open (Bronze)
1. Moocryption
보드판을 전부 훑으면서 OXX의 패턴이 나타나는 문자열의 수를 전부 카운트 한다. 암호화가 한번은 되야 하므로
O의 자리에 M이 들어가거나 X의 자리에 O가 들어있으면 카운트하면 안된다.
b = []
with open("moocrypt.in", "r") as f:
n, m = map(int, f.readline().strip().split())
for _ in range(n):
b.append(list(f.readline().strip()))
d = dict()
dx = [1, 1, 0, -1, -1, -1, 0, 1]
dy = [0, -1, -1, -1, 0, 1, 1, 1]
for i in range(n):
for j in range(m):
for k in range(8):
if 0 <= i+dy[k]*2 < n and 0 <= j+dx[k]*2 < m:
if b[i][j] != 'M' and b[i][j] != b[i+dy[k]][j+dx[k]] == b[i+dy[k]*2][j+dx[k]*2] != 'O':
res = b[i][j]+b[i+dy[k]][j+dx[k]]+b[i+dy[k]*2][j+dx[k]*2]
if res in d:
d[res] += 1
else:
d[res] = 1
with open("moocrypt.out", "w") as f:
if d.values():
f.write(str(max(d.values()))+'\n')
else:
f.write("0\n")
2. Bessie Gets Even
각각의 변수가 짝수냐 홀수냐에 따라 수식의 결과가 달라진다는 점을 이용해서, 각각의 변수의 숫자를 짝수와 홀수의 수로 구분하면 2**7 꼴의 수의 조합만으로 결과를 찾아낼 수 있다.
d = {"B": [0, 0], "E": [0, 0], "S": [0, 0], "I": [0, 0], "G": [0, 0], "O": [0, 0], "M": [0, 0]}
with open("geteven.in", "r") as f:
n = int(f.readline())
for _ in range(n):
w, num = f.readline().strip().split()
num = int(num)
if num % 2 == 0:
d[w][0] += 1
else:
d[w][1] += 1
ans = 0
for b in range(2):
for e in range(2):
for s in range(2):
for i in range(2):
for g in range(2):
for o in range(2):
for m in range(2):
if ((b+e+s+s+i+e)*(g+o+e+s)*(m+o+o)) % 2 == 0:
ans += d['B'][b] * d['E'][e] * d['S'][s] * d['I'][i] * d['G'][g] * d['O'][o] * d['M'][m]
with open("geteven.out", "w") as f:
f.write(str(ans)+'\n')
3. Trapped in the Haybales
일단 짚단의 거리순으로 정렬한 후, 하나의 구간당 왼쪽과 오른쪽을 뚫을 수 있는지 확인하고 전체 크기 안에서 가로막히는 구간이 존재한다면 해당 구간을 정답에 추가하면 된다.
a = []
with open("trapped.in", "r") as f:
n = int(f.readline())
for _ in range(n):
a.append(list(map(int, f.readline().strip().split()))) # size, position
a.sort(key=lambda x: x[1])
ans = 0
for i in range(n-1):
dist = a[i+1][1] - a[i][1]
lm = i
rm = i+1
while lm >= 0 and rm <= n-1:
broke = False
curdist = a[rm][1] - a[lm][1]
if curdist > a[lm][0]:
lm -= 1
broke = True
if curdist > a[rm][0]:
rm += 1
broke = True
if not broke:
break
if lm >= 0 and rm <= n-1:
ans += dist
with open("trapped.out", "w") as f:
f.write(str(ans)+'\n')
4. Palindromic Paths
N=18 일때 처음부터 끝까지 완전탐색으로 찾아가는 경우의 수는 36!/(18!18!)이다.
(아래로 가는 경로를 A, 오른쪽으로 가는 경로를 B라고 하면 결국 A와 B를 18개씩 사용하는 수열이므로, 전체 경우의 수 36!에, A, B가 각각 18번 나오므로 서로 순서가 바뀌어도 동일하니 나누어 주면 됨)
이 상태로는 탐색해야 할 크기가 너무 크므로 시작점에서 출발하고, 끝에서 거슬러 올라오는 탐색을 돌린 후 대각선에서 만나는 것을 탐색하면 경우의 수가 22^17번으로 줄어든다.
b = []
with open("palpath.in", "r") as f:
n = int(f.readline())
for _ in range(n):
b.append(list(f.readline().strip()))
ans = 0
cand = set()
cand2 = set()
def f(y, x, path):
path += b[y][x]
if x+y == n-1:
cand.add((path, x))
return
f(y+1, x, path)
f(y, x+1, path)
def f2(y, x, path):
path += b[y][x]
if x+y == n-1:
cand2.add((path, x))
return
f2(y - 1, x, path)
f2(y, x - 1, path)
f(0, 0, '')
f2(n-1, n-1, '')
ans = set()
for r in cand & cand2:
ans.add(r[0])
with open("palpath.out", "w") as f:
f.write(str(len(ans))+'\n')
