You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
def solution(s):
ansList = []
ans = []
for i in range(1,len(s)):
numList = []
numStr = ''
if s[i] == '{':
i+=1
while(s[i] != '}'):
if s[i] == ',':
numList.append(numStr)
numStr = ''
else:
numStr += s[i]
i+=1
numList.append(numStr)
numsStr = ''
ansList.append(numList)
else:
pass
for i in range(1,len(ansList)+1):
for j in ansList:
if len(j)==i:
for k in range(0,i):
if j[k] not in ans:
ans.append(j[k])
ans = [int (i) for i in ans]
return ans
def solution(record):
name_dict = {}
record_list = []
for i in record:
record_list.append([(i.split(' '))])
for i in record_list:
for j in i:
if j[0] == 'Enter' or j[0] == 'Change':
name_dict[j[1]] = j[2]
ans_list = []
for i in record_list:
for j in i:
if j[0] == 'Enter':
result = str(name_dict[j[1]]) +'๋์ด ๋ค์ด์์ต๋๋ค.'
ans_list.append(result)
elif j[0] == 'Leave':
result = str(name_dict[j[1]]) + '๋์ด ๋๊ฐ์ต๋๋ค.'
ans_list.append(result)
return(ans_list)
def solution(p):
def hi(p):
# ์ ๋ ฅ์ด ๋น ๋ฌธ์์ด
if p == '':
# ๋น ๋ฌธ์์ด ๋ฐํ
return p
else:
left = 0
right = 0
u = ''
v = ''
#u, v๋ก ๋ฐํ
for i in p:
if left == right and left != 0:
v += i
else:
if i =='(':
left += 1
u += i
else:
right += 1
u += i
# u๊ฐ ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด ์ฒดํฌ
stack = []
flag = True
for i in u:
if i == '(':
stack.append(i)
else:
if len(stack) == 0:
flag = False
break
else:
stack.pop()
if len(stack)>0:
flag = False
# u๊ฐ ์ฌ๋ฐ๋ฅธ ๊ดํธ ๋ฌธ์์ด์ผ ๊ฒฝ์ฐ
if flag == True:
return u + hi(v)
elif flag == False:
new_str = '('
new_str += hi(v)
new_str += ')'
u = u[1:len(u)-1]
new_u = ''
for i in u:
if i =='(':
new_u += ')'
else:
new_u += '('
new_str += new_u
return new_str
return(hi(p))
def solution(s):
if len(s) == 1:
return 1
else:
ans_list = []
for j in range(1,int(len(s)/2)+1):
s_list = []
for i in range(0,int(len(s)/j)+1):
s_list.append(s[i*j:i*j+j])
tmp = ''
s2_list = []
for i in s_list:
if tmp == '':
cnt = 1
tmp = i
else:
if tmp == i:
cnt +=1
else:
if cnt == 1:
str_cnt = tmp
else:
str_cnt = str(cnt) + tmp
s2_list.append(str_cnt)
tmp = i
cnt = 1
if tmp != '':
if cnt == 1:
str_cnt = tmp
else:
str_cnt = str(cnt) + tmp
s2_list.append(str_cnt)
ans = ''
for i in s2_list:
ans += i
ans_list.append(len(ans))
return min(ans_list)
from itertools import combinations
def solution(nums):
def prime_list(n):
# ์๋ผํ ์คํ ๋ค์ค์ ์ฒด ์ด๊ธฐํ: n๊ฐ ์์์ True ์ค์ (์์๋ก ๊ฐ์ฃผ)
sieve = [True] * n
# n์ ์ต๋ ์ฝ์๊ฐ sqrt(n) ์ดํ์ด๋ฏ๋ก i=sqrt(n)๊น์ง ๊ฒ์ฌ
m = int(n ** 0.5)
for i in range(2, m + 1):
if sieve[i] == True: # i๊ฐ ์์์ธ ๊ฒฝ์ฐ
for j in range(i+i, n, i): # i์ดํ i์ ๋ฐฐ์๋ค์ False ํ์
sieve[j] = False
# ์์ ๋ชฉ๋ก ์ฐ์ถ
return sieve
prime = prime_list(3000)
ans_list = list(combinations(nums, 3))
ans = 0
for i in ans_list:
sum = 0
for j in i:
sum += j
if sum in prime:
ans+=1
return ans
def solution(n, computers):
def dfs(computers,visited,v):
visited[v]=1
for i in range(len(computers)):
if computers[v][i]==1 and visited[i]==0:
dfs(computers,visited,i)
visited = [0 for i in range(n)]
ans = 0
for i in range(n):
if visited[i] == 0:
dfs(computers,visited,i)
ans+=1
return ans
stack = []
visited = []
def solution(begin, target, words):
def dfs(word,depth):
if word == target:
stack.append(depth)
else:
for i in range(0,len(words)):
if visited[i] == 0:
diff = 0
for j in range(0,len(word)):
if word[j] != words[i][j]:
diff +=1
if diff == 1:
visited[i]=1
dfs(words[i],depth+1)
visited[i]=0
diff = 0
visited = [0 for i in range (len(words))]
dfs(begin,0)
if len(stack)==0:
return 0
else:
return min(stack)
import copy
def solution(tickets):
visited = [0 for i in tickets]
st = []
ans = []
def dfs(start,tickets,visited,cnt):
st.append(start)
if cnt >= len(tickets):
ans.append(copy.deepcopy(st))
for i in range(0,len(tickets)):
if tickets[i][0] == start and visited[i] == 0:
visited[i] = 1
dfs(tickets[i][1],tickets,visited,cnt+1)
visited[i] = 0
st.pop()
dfs("ICN",tickets, visited,0)
return sorted(ans)[0]
import math
def solution(numbers, hand):
ans = ''
loc = {1: (0,0), 2: (0,1), 3: (0,2),
4: (1,0), 5: (1,1), 6: (1,2),
7: (2,0), 8: (2,1), 9: (2,2),
'*': (3,0), 0: (3,1), '#': (3,2)}
left = '*'
right = '#'
for i in numbers:
if i == 1 or i == 4 or i == 7:
left = i
ans += 'L'
elif i == 3 or i == 6 or i == 9:
right = i
ans += 'R'
else:
# ๋ ์ ์ฌ์ด์ ๊ฑฐ๋ฆฌ ๊ณต์ X
lx = abs(loc[left][0] - loc[i][0])
ly = abs(loc[left][1] - loc[i][1])
ll = lx+ly
rx = abs(loc[right][0] - loc[i][0])
ry = abs(loc[right][1] - loc[i][1])
rl = rx+ry
if ll < rl:
left = i
ans += 'L'
elif ll > rl:
right = i
ans += 'R'
else:
if hand == "right":
right = i
ans += 'R'
else:
left = i
ans += 'L'
return(ans)
n = int(input())
p_list = []
for i in range(0,n):
p_info = input().split()
p_list.append(p_info)
p_rank = []
for i in range(0,n):
rank = 1
for j in range(0,n):
if i!=j and (p_list[i][0] < p_list[j][0] and p_list[i][1] < p_list[j][1]):
rank+=1
print(rank)
def solution(n, t, m, p):
s = "0"
def convert(number, base):
T = "0123456789ABCDEF"
q, r = divmod(number, base)
if q == 0:
return T[r]
else:
return convert(q, base) + T[r]
for i in range(1,t*m):
s += convert(i,n)
q = p-1
result = ""
for i in range(0,t):
result += s[q]
q += m
return(result)
import re
def solution(files):
answer = []
p = re.compile("([a-z\-\s]+)([0-9]+)(.*)")
s_list = []
for temp in files:
g = p.search(temp.lower())
head = g.group(1)
num = int(g.group(2))
s_list.append((head,num,temp))
s_list = sorted(s_list,key=lambda x:(x[0],x[1]))
for i in s_list:
answer.append(i[2])
return(answer)
n=input()
k=input()
ans = []
for i in range(len(n)):
ans.append(n[i])
if len(ans) >= len(k):
flag = True
for j in range(1, len(k)+1):
if ans[-j] != k[-j]:
flag = False
break
if flag:
for j in range(len(k)):
ans.pop()
if len(ans) == 0:
print("FRULA")
else:
print("".join(ans))
import sys
n,s = map(int,sys.stdin.readline().split())
arr = list(map(int,sys.stdin.readline().split()))
result,Sum,start,end = 100001,0,0,0
while True:
if Sum >= s:
Sum -= arr[start]
result = min(result,(end-start))
start+=1
elif end == n:
break
else:
Sum += arr[end]
end+=1
if result == 100001:
print(0)
else:
print(result)
def solution(n, times):
left = 0
right = max(times)*n
ans = right
while left <= right:
temp = 0
mid = (left+right)//2
for i in times:
temp += mid//i
if temp < n:
left = mid + 1
else:
if mid <= ans:
ans = mid
right = mid - 1
return ans
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
n = int(input())
board = [list(map(int, list(input()))) for _ in range(n)]
dq = deque()
visited = [[False]*n for _ in range(n)]
ans = 0
st = []
for i in range(n):
for j in range(n):
if visited[i][j] == False and board[i][j] == 1:
visited[i][j] = True
dq.append((i,j))
cnt = 1
ans+=1
while dq:
x,y = dq.popleft()
for k in range(4):
nx, ny = x+dx[k], y+dy[k]
if 0 <= nx < n and 0 <= ny < n:
if visited[nx][ny] == False and board[nx][ny] == 1:
dq.append((nx,ny))
cnt+=1
visited[nx][ny] = True
st.append(cnt)
print(ans)
st = sorted(st)
for i in st:
print(i)
from collections import deque
n,m,v = map(int, input().split())
board = [[0]*(n+1) for i in range(n+1)]
visited = [0 for i in range(n+1)]
for i in range(m):
x,y = map(int, input().split())
board[x][y] = 1
board[y][x] = 1
def dfs(v):
print(v,end=' ')
visited[v] = 1
for i in range(1,n+1):
if visited[i] == 0 and board[v][i] == 1:
dfs(i)
dfs(v)
print()
def bfs(v):
dq = deque()
dq.append(v)
visited[v] = 0
while dq:
v = dq.popleft()
print(v,end= ' ')
for i in range(1,n+1):
if visited[i] == 1 and board[v][i] == 1:
dq.append(i)
visited[i] = 0
bfs(v)
import sys
sys.setrecursionlimit(10 ** 9)
n = int(sys.stdin.readline())
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
i,j = map(int,sys.stdin.readline().split())
tree[i].append(j)
tree[j].append(i)
parents = [0 for _ in range(n+1)]
def dfs(start,tree,parents):
for i in tree[start]:
if parents[i] == 0:
parents[i] = start
dfs(i,tree,parents)
dfs(1,tree,parents)
for i in range(2,n+1):
print(parents[i])
import sys
sys.setrecursionlimit(10 ** 9)
from collections import deque
def solution(n, edge):
graph = [[] for _ in range(n+1)]
for i in range(len(edge)):
s,e = edge[i][0],edge[i][1]
graph[s].append(e)
graph[e].append(s)
visited = [0 for _ in range(n+1)]
dq = deque([[1,0]])
while dq:
cur_node, dist = dq.popleft()
for next_node in graph[cur_node]:
if visited[next_node] == 0 and next_node!=1:
dq.append([next_node,dist+1])
visited[next_node] = dist+1
return(visited.count(max(visited)))
import sys
n = int(sys.stdin.readline())
board = [[0]*(n+1) for i in range(n+1)]
visited = [0 for i in range(n+1)]
ex,ey = map(int,sys.stdin.readline().split())
m = int(sys.stdin.readline())
for i in range(m):
x,y = map(int,sys.stdin.readline().split())
board[y][x] = 1
board[x][y] = 1
def dfs(v,cnt):
visited[v] = 1
if v == ey:
print(cnt)
return
for i in range(1,n+1):
if visited[i] == 0 and board[v][i] == 1:
dfs(i,cnt+1)
dfs(ex,0)
if visited[ey] != 1:
print(-1)
import sys
n = int(input())
cost = []
dp = [[0 for _ in range(3)] for _ in range(n)]
for i in range(n):
cost.append(list(map(int,sys.stdin.readline().split())))
for i in range(n):
if i == 0:
dp[i][0] = cost[i][0]
dp[i][1] = cost[i][1]
dp[i][2] = cost[i][2]
else:
dp[i][0] = cost[i][0] + min(dp[i-1][1],dp[i-1][2])
dp[i][1] = cost[i][1] + min(dp[i-1][0],dp[i-1][2])
dp[i][2] = cost[i][2] + min(dp[i-1][0],dp[i-1][1])
print(min(dp[n-1][0],dp[n-1][1],dp[n-1][2]))
import sys
sys.setrecursionlimit(10**5)
dx = [-1,-1,-1,0,0,1,1,1]
dy = [-1,0,1,-1,1,-1,0,1]
w = h = 0
def dfs(x,y):
visited[x][y] = 1
for i in range(8):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<h and 0<=ny<w and board[nx][ny]==1 and visited[nx][ny]==0:
dfs(nx,ny)
while True:
w,h = map(int,sys.stdin.readline().split())
if w == 0 and h == 0:
break
else:
board = [[0 for col in range(w)] for row in range(h)]
for i in range(h):
arr = list(map(int,sys.stdin.readline().split()))
for j in range(w):
board[i][j] = arr[j]
visited = [[0]*w for _ in range(h)]
cnt = 0
for i in range(h):
for j in range(w):
if visited[i][j]==0 and board[i][j]==1:
dfs(i,j)
cnt+=1
print(cnt)
import sys
n = int(input())
graph = []
for i in range(n):
graph.append(list(map(int,sys.stdin.readline().split())))
for k in range(n):
for i in range(n):
for j in range(n):
if graph[i][j] == 1 or (graph[i][k] == 1 and graph[k][j] == 1):
graph[i][j] = 1
for row in graph:
for col in row:
print(col, end=' ')
print()
import sys
INF=2**32
n = int(input())
m = int(input())
cost = [[INF for _ in range(100)] for _ in range(100)]
for i in range(n):
cost[i][i] = 0
for _ in range(m):
a,b,c = map(int,sys.stdin.readline().split())
cost[a-1][b-1] = min(cost[a-1][b-1],c)
def floyd():
for k in range(n):
for i in range(n):
for j in range(n):
if i==j or j==k or k==i:
continue
elif cost[i][j] > cost[i][k] + cost[k][j]:
cost[i][j] = cost[i][k] + cost[k][j]
floyd()
for i in range(n):
for j in range(n):
if cost[i][j] == INF:
cost[i][j] = 0
for i in range(n):
for j in range(n):
if i == j:
print(0,end=' ')
else:
print(cost[i][j],end=' ')
print()
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
INF=sys.maxsize
v,e = map(int,input().split())
k = int(input())
graph = [[] for _ in range(v+1)]
dp = [INF] * (v+1)
heap = []
for i in range(e):
u,v,w = map(int,input().split())
# ๋ฐฉํฅ ๊ทธ๋ํ
graph[u].append([v,w])
def dijkstra(start):
dp[start] = 0
heappush(heap,[0,start])
while heap:
wei,now = heappop(heap)
for next_node, w in graph[now]:
next_wei = w + wei
if dp[now] < wei:
continue
if next_wei < dp[next_node]:
dp[next_node] = next_wei
heappush(heap,[next_wei,next_node])
dijkstra(k)
for i in dp[1:]:
if i != INF:
print(i)
else:
print('INF')
import sys
n = int(input())
arr = list(map(int,sys.stdin.readline().split()))
arr.sort()
m = int(input())
arr2 = list(map(int,sys.stdin.readline().split()))
def binary_search(val):
first, last = 0, n-1
while first<=last:
mid = (first+last)//2
if arr[mid] == val: return 1
if arr[mid] > val: last = mid-1
else: first = mid+1
return 0
for i in arr2:
print(binary_search(i), end=' ')
n = int(input())
left = 1
right = 1
Sum = 0
ans = 0
while left<=right and right<=n+1:
if Sum < n:
Sum += right
right+=1
elif Sum > n:
Sum -= left
left+=1
else:
ans+=1
Sum += right
right+=1
print(ans)
dp =[[0 for _ in range(32)] for _ in range(32)]
for i in range(0,31):
dp[0][i] = 1
for w in range(1,31):
for h in range(0,31):
if h == 0:
dp[w][h] = dp[w-1][1]
else:
dp[w][h] = dp[w-1][h+1] + dp[w][h-1]
while True:
n = int(input())
if n == 0:
break
else:
print(dp[n-1][1])
from collections import deque
dx = [-1,0,0,1]
dy = [0,1,-1,0]
for _ in range(int(input())):
m,n,k = map(int,input().split())
board = [[0]*(m) for _ in range(n)]
for _ in range(k):
x,y = map(int,input().split())
board[y][x] = 1
visited = [[0]*(m) for _ in range(n)]
def bfs(x,y):
visited[x][y] = 1
dq = deque()
dq.append((x,y))
while dq:
x,y = dq.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
else:
if visited[nx][ny] == 0 and board[nx][ny] == 1:
visited[nx][ny] = 1
dq.append((nx,ny))
cnt = 0
for i in range(n):
for j in range(m):
if visited[i][j] == 0 and board[i][j] == 1:
bfs(i,j)
cnt+=1
print(cnt)
INF = 2**32
n = int(input())
board = [[INF]*(50) for _ in range(50)]
for i in range(n):
arr = list(input())
for j in range(n):
if i == j:
board[i][j] = 0
else:
if arr[j] == 'Y':
board[i][j] = 1
def floyd():
for k in range(n):
for i in range(n):
for j in range(n):
if i==j or j==k or k==i:
continue
elif board[i][j] > board[i][k] + board[k][j]:
board[i][j] = board[i][k] + board[k][j]
floyd()
ans = 0
for i in range(n):
cnt = 0
for j in range(n):
if i == j:
continue
elif board[i][j] <=2:
cnt+=1
ans = max(ans,cnt)
print(ans)
n = int(input())
board = [input() for _ in range(n)]
def quad(x,y,n):
global ans
tmp = board[x][y]
for i in range(x,x+n):
for j in range(y,y+n):
if tmp != board[i][j]:
ans += '('
quad(x,y,n//2)
quad(x,y+n//2,n//2)
quad(x+n//2,y,n//2)
quad(x+n//2,y+n//2,n//2)
ans += ')'
return
if tmp == '0':
ans += '0'
else:
ans += '1'
ans = ''
quad(0,0,n)
print(ans)
import sys
n = int(input())
board = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]
minus_one = 0
zero = 0
one = 0
def quad(x,y,n):
global minus_one,zero,one
tmp = board[x][y]
for i in range(x,x+n):
for j in range(y,y+n):
if tmp != board[i][j]:
for k in range(3):
for l in range(3):
quad(x+k*n//3,y+l*n//3,n//3)
return
if tmp == -1:
minus_one += 1
elif tmp == 0:
zero += 1
elif tmp == 1:
one +=1
quad(0,0,n)
print(minus_one)
print(zero)
print(one)
import sys
INF=2**32
n,m = map(int,input().split())
board = [[INF]*n for _ in range(n)]
for i in range(m):
a,b = map(int,sys.stdin.readline().split())
board[a-1][b-1] = 1
for i in range(n):
board[i][i] = 0
def floyd():
for k in range(n):
for i in range(n):
for j in range(n):
if i==j or j==k or k==i:
continue
elif board[i][j] == 1 or (board[i][k] == 1 and board[k][j] == 1):
board[i][j] = 1
floyd()
cnt = [0]*n
for i in range(n):
for j in range(n):
if board[i][j] == 1:
cnt[i] += 1
cnt[j] += 1
print(cnt.count(n-1))
from collections import deque
m,n = map(int,input().split())
board = [list(map(int,input())) for _ in range(n)]
visited =[[-1]*m for _ in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def bfs():
while dq:
x,y = dq.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if visited[nx][ny] == -1:
if board[nx][ny] == 0:
visited[nx][ny] = visited[x][y]
dq.appendleft([nx,ny])
else:
visited[nx][ny] = visited[x][y]+1
dq.append([nx,ny])
dq = deque()
dq.append([0,0])
visited[0][0] = 0
bfs()
print(visited[n-1][m-1])
A=list(input())
B=list(input())
lcs=[[0 for _ in range(len(B)+1)] for _ in range(len(A)+1)]
for i in range(1,len(A)+1):
for j in range(1,len(B)+1):
if A[i-1]==B[j-1]:
lcs[i][j]=lcs[i-1][j-1]+1
else:
lcs[i][j]=max(lcs[i-1][j],lcs[i][j-1])
print(lcs[len(A)][len(B)])
import sys
from collections import deque
n,m = map(int,sys.stdin.readline().split())
tree = [[] for _ in range(n+1)]
inDegree = [0 for _ in range(n+1)]
dq = deque()
result = []
for _ in range(m):
s,e = map(int,sys.stdin.readline().split())
tree[s].append(e)
inDegree[e]+=1
for i in range(1,n+1):
if inDegree[i] == 0:
dq.append(i)
while dq:
a = dq.popleft()
result.append(a)
for t in tree[a]:
inDegree[t]-=1
if inDegree[t]==0:
dq.append(t)
print(*result)
import sys
input = sys.stdin.readline
def get_parent(x):
if parent[x] == x:
return x
p = get_parent(parent[x])
parent[x] = p
return p
def union(x,y):
x = get_parent(x)
y = get_parent(y)
if x != y:
parent[y] = x
def find_parent(x):
if parent[x] == x:
return x
return find_parent(parent[x])
n,m = map(int,input().split())
parent = {}
for i in range(n+1):
parent[i] = i
for _ in range(m):
z,x,y = map(int,input().split())
if not z:
union(x,y)
else:
if find_parent(x) == find_parent(y):
print("YES")
else:
print('NO')
from collections import deque
n,m = map(int,input().split())
board = [list(map(str,input())) for _ in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
def bfs(x,y):
visited =[[0]*(m) for _ in range(n)]
visited[x][y] = 1
dq = deque()
dq.append((x,y))
num = 0
while dq:
x,y = dq.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
else:
if visited[nx][ny] == 0 and board[nx][ny] == 'L':
visited[nx][ny] = visited[x][y] + 1
num = max(num,visited[nx][ny])
dq.append((nx,ny))
return num-1
cnt = 0
for i in range(n):
for j in range(m):
if board[i][j] == 'L':
cnt = max(cnt,bfs(i,j))
print(cnt)
import sys
from collections import deque
import math
input = sys.stdin.readline
K,N = map(int,input().split())
lan = [int(sys.stdin.readline()) for _ in range(K)]
lan.sort()
left = 1
right = max(lan)
while left<=right:
mid = (left+right)//2
lines = 0
for i in lan:
lines += i//mid
if lines >= N:
left = mid+1
else:
right = mid-1
print(right)
import sys
from collections import deque
import math
input = sys.stdin.readline
N,M= map(int,input().split())
board = [[0]*M for _ in range(N)]
for i in range(N):
arr = input()
for j in range(len(arr)-1):
board[i][j] = int(arr[j])
dx = [-1,1,0,0]
dy = [0,0,1,-1]
def bfs():
dq = deque()
dq.append((0,0,1))
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
visited[0][0][1] = 1
while dq:
x,y,z = dq.popleft()
if x == N-1 and y == M-1:
return visited[x][y][z]
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= N or ny <0 or ny >= M:
continue
else:
if board[nx][ny] == 1 and z == 1:
visited[nx][ny][0] = visited[x][y][1] + 1
dq.append((nx,ny,0))
elif board[nx][ny] == 0 and visited[nx][ny][z] == 0:
visited[nx][ny][z] = visited[x][y][z] + 1
dq.append((nx,ny,z))
return -1
print(bfs())
import sys
from collections import deque
import math
input = sys.stdin.readline
INF=2**32
N,M = map(int,input().split())
board = [[INF]*N for _ in range(N)]
for i in range(M):
a,b = map(int,sys.stdin.readline().split())
board[a-1][b-1] = 1
board[b-1][a-1] = 1
for i in range(N):
board[i][i] = 0
def floyd():
for k in range(N):
for i in range(N):
for j in range(N):
if i==j or j==k or k==i:
continue
else:
board[i][j] = min(board[i][j],board[i][k]+board[k][j])
floyd()
ans = []
for i in board:
ans.append(sum(i))
for i in range(N):
if ans[i] == min(ans):
print(i+1)
break
import sys
from collections import deque
import math
import copy
input = sys.stdin.readline
N,M,T = map(int,input().split())
board = [list(map(int, input().split())) for _ in range(N)]
visited = [[[0]*2 for _ in range(M)] for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,1,-1]
def bfs():
dq = deque()
dq.append((0,0,0,0))
visited[0][0][0] = 1
while dq:
x,y,cnt,sw = dq.popleft()
if board[x][y] == 2:
sw = 1
if x == N-1 and y == M-1:
return cnt
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if sw == 1:
if 0<=nx<N and 0<=ny<M and visited[nx][ny][sw] == 0:
visited[nx][ny][sw] = cnt + 1
dq.append((nx,ny,cnt+1,sw))
else:
if 0<=nx<N and 0<=ny<M and visited[nx][ny][sw] == 0 and board[nx][ny] != 1:
visited[nx][ny][sw] = cnt + 1
dq.append((nx,ny,cnt+1,sw))
return -1
ans = bfs()
if 0 <= ans <= T:
print(ans)
else:
print("Fail")
import sys
from collections import deque
import math
import copy
import heapq
input = sys.stdin.readline
n,k = map(int,input().split())
gem = []
for i in range(n):
m,v = map(int,input().split())
gem.append((m,v))
bag = []
for i in range(k):
c = int(input())
bag.append(c)
gem.sort()
bag.sort()
heap = []
j = 0
ans = 0
for i in range(k):
while j<n and bag[i]>=gem[j][0]:
heapq.heappush(heap,-gem[j][1])
j+=1
if heap:
temp = heapq.heappop(heap)
ans += abs(temp)
print(ans)
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
visited = [[False]*n for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
idx = 1
# ์ฌ ๋ฒํธ ๋ถ์ด๊ธฐ
def dfs(x,y):
visited[x][y] = True
board[x][y] = idx
for i in range(4):
nx,ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if not visited[nx][ny] and board[nx][ny]:
dfs(nx,ny)
for i in range(n):
for j in range(n):
if board[i][j] and not visited[i][j]:
dfs(i,j)
idx+=1
# ์ต์๊ฐ ์ ์ฅ
ans = 10**9
# ์ฌ์์ ์ฌ๋ผ๋ฆฌ ๊ฑฐ๋ฆฌ ์ฐพ๊ธฐ
def bfs(idx):
global ans
dq = deque()
dist = [[-1]*n for _ in range(n)]
for i in range(n):
for j in range(n):
if board[i][j] == idx:
dq.append((i,j))
dist[i][j] = 0
while dq:
x,y = dq.popleft()
for i in range(4):
nx,ny = x + dx[i], y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if board[nx][ny] and board[nx][ny] != idx:
ans = min(ans,dist[x][y])
return
if not board[nx][ny] and dist[nx][ny] == -1:
dist[nx][ny] = dist[x][y] + 1
dq.append((nx,ny))
for i in range(1,idx+1):
bfs(i)
print(ans)
import sys
from collections import deque
import math
input = sys.stdin.readline
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
dp = [[0]*n for _ in range(n)]
dp[0][0] = 1
for i in range(n):
for j in range(n):
if board[i][j] == 0:
continue
if i + board[i][j] < n:
dp[i+board[i][j]][j] += dp[i][j]
if j + board[i][j] < n:
dp[i][j+board[i][j]] += dp[i][j]
print(dp[n-1][n-1])
import sys
from collections import deque
import math
input = sys.stdin.readline
sys.setrecursionlimit(10000)
m,n = map(int,input().split())
board = [list(map(int, input().split())) for _ in range(m)]
dp = [[-1]*n for _ in range(m)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def dfs(x,y):
if x == 0 and y == 0:
return 1
if dp[x][y] == -1:
dp[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < m and 0 <= ny < n:
if board[x][y] < board[nx][ny]:
dp[x][y] += dfs(nx,ny)
return dp[x][y]
print(dfs(m-1,n-1))
import sys
from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
board = [list(input().strip()) for _ in range(n)]
visited = [[[0]*64 for _ in range(m)] for _ in range(n)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
def bfs(x,y):
dq = deque()
dq.append((x,y,0,0))
visited[x][y][0] = 1
while dq:
x,y,key,dist = dq.popleft()
if board[x][y] == '1':
return dist
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < m and visited[nx][ny][key] == 0 and board[nx][ny] != '#':
#print(nx,ny,board[nx][ny],dist)
if board[nx][ny].isupper():
if key & 1 << (ord(board[nx][ny]) - 65):
visited[nx][ny][key] = visited[x][y][key] +1
dq.append((nx,ny,key,dist+1))
elif board[nx][ny].islower():
nKey = key | (1 << ord(board[nx][ny]) - 97)
if visited[nx][ny][nKey] == 0:
visited[nx][ny][nKey] = visited[x][y][key] + 1
dq.append((nx,ny,nKey,dist+1))
else:
visited[nx][ny][key] = visited[x][y][key] + 1
dq.append((nx,ny,key,dist+1))
return -1
for i in range(n):
for j in range(m):
if board[i][j] == '0':
print(bfs(i,j))
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
k = int(input())
st = list(input().split())
node = [0,1,2,3,4,5,6,7,8,9]
visited = [0,0,0,0,0,0,0,0,0,0]
ans = []
def dfs(v,cnt,num,idx):
if cnt == k:
ans.append(num)
else:
for i in node:
if visited[i] == 0:
if st[idx] == '<':
if v >= i:
continue
else:
if v <= i:
continue
visited[i] = True
dfs(i,cnt+1,num+str(i),idx+1)
visited[v] = False
for i in node:
visited[i] = 1
dfs(i,0,str(i),0)
print(ans[-1])
print(ans[0])
import copy
def solution(m, n, board):
# ์ด๊ธฐ ๋ฐฐ์ด
n_board = [[0]*n for _ in range(m)]
for i in range(m):
for j in range(n):
n_board[i][j] = board[i][j]
flag = True;
while flag:
# ์ง์ธ ๋ธ๋ก ๋ด์ ๋ฐฐ์ด
tmp_board = copy.deepcopy(n_board)
# ์ง์ธ ๋ธ๋ก ์ ํํ๊ธฐ
flag = False;
for x in range(m):
for y in range(n):
if x+1 < m and y+1 < n and n_board[x][y] != '0' and (n_board[x][y] == n_board[x+1][y] and n_board[x][y] == n_board[x][y+1] and n_board[x][y] == n_board[x+1][y+1]):
tmp_board[x][y] = '0'
tmp_board[x+1][y] = '0'
tmp_board[x][y+1] = '0'
tmp_board[x+1][y+1] = '0'
flag = True;
after_board = []
# ๋ธ๋ก ์ง์ฐ๊ณ ์๋๋ก ๋ด๋ฆฌ๊ธฐ
for i in range(n):
tmp_list = []
for j in range(m):
if tmp_board[j][i] != '0':
tmp_list.append(tmp_board[j][i])
after_board.append(tmp_list)
# ๋ง์ง๋ง ์ฐ์ฐํ ๋ฐฐ์ด
last_board = [['0']*n for _ in range(m)]
for i in range(n):
cnt = len(after_board[i])
idx = 0
for j in range(m):
if cnt == m:
last_board[j][i] = after_board[i][idx]
idx+=1
else:
cnt+=1
n_board = last_board
ans = 0
for i in range(m):
for j in range(n):
if last_board[i][j] == '0':
ans+=1
return ans
def solution(msg):
table = {}
num = 65
for i in range(1,27):
table[chr(num)] = i
num+=1
w = 0
c = 0
ans = []
while True:
# ํ์ฌ๊ธ์ + ๋ค์๊ธ์๊ฐ ์ฌ์ ์ ์๋ค๋ฉด w๋ ๋ณํ์์, c = c + 1
c += 1
# c๊ฐ ๋ง์ง๋ง ์ธ๋ฑ์ค ๋ฒํธ๋ผ๋ฉด while๋ฌธ ์ข ๋ฃ
if len(msg) == c:
ans.append(table[msg[w:c]])
break
# ํ์ฌ๊ธ์ + ๋ค์๊ธ์๊ฐ ์ฌ์ ์ ์๋ค๋ฉด w = c, c = c + 1
if msg[w:c+1] not in table:
table[msg[w:c+1]] = len(table) + 1
ans.append(table[msg[w:c]])
w = c
return ans
def attach(x, y, M, key, board):
for i in range(M):
for j in range(M):
board[x+i][y+j] += key[i][j]
def detach(x, y, M, key, board):
for i in range(M):
for j in range(M):
board[x+i][y+j] -= key[i][j]
def rotate90(arr):
return list(zip(*arr[::-1]))
def check(board, M, N):
for i in range(N):
for j in range(N):
if board[M+i][M+j] != 1:
return False
return True
def solution(key, lock):
M, N = len(key), len(lock)
if key == lock:
return True
board = [[0] * (M*2 + N) for _ in range(M*2 + N)]
# ์๋ฌผ์ ์ค์ ๋ฐฐ์น
for i in range(N):
for j in range(N):
board[M+i][M+j] = lock[i][j]
rotated_key = key
# ๋ชจ๋ ๋ฐฉํฅ (4๋ฒ ๋ฃจํ)
for _ in range(4):
rotated_key = rotate90(rotated_key)
for x in range(1, M+N):
for y in range(1, M+N):
# ์ด์ ๋ฃ์ด๋ณด๊ธฐ
attach(x, y, M, rotated_key, board)
# lock ๊ฐ๋ฅ check
if(check(board, M, N)):
return True
# ์ด์ ๋นผ๊ธฐ
detach(x, y, M, rotated_key, board)
return False
import sys
import heapq
input = sys.stdin.readline
n = int(input())
heap = []
for i in range(n):
heapq.heappush(heap,int(input()))
if len(heap) == 1:
print(0)
else:
ans = 0
while len(heap) > 1:
Sum = heapq.heappop(heap) + heapq.heappop(heap)
ans += Sum
heapq.heappush(heap,Sum)
print(ans)
h,w = map(int,input().split())
arr = list(map(int,input().split()))
maxH = 0
maxIdx = 0
for i in range(len(arr)):
if maxH < arr[i]:
maxH = arr[i]
maxIdx = i
total = 0
temp = 0
for i in range(0,maxIdx+1):
if arr[i] > temp:
temp = arr[i]
total += temp
temp = 0
for i in range(len(arr)-1,maxIdx,-1):
if arr[i] > temp:
temp = arr[i]
total += temp
print(total-sum(arr))
n,k = map(int,input().split())
bag = [(0,0)]
for i in range(n):
w,v = map(int,input().split())
bag.append((w,v))
dp = [[0]*(k+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(1,k+1):
w = bag[i][0]
v = bag[i][1]
if j >= w:
dp[i][j] = max(v+dp[i-1][j-w],dp[i-1][j])
else:
dp[i][j] = dp[i-1][j]
print(dp[n][k])
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
n,m = map(int,input().split())
graph = [[] for _ in range(n)]
for i in range(m):
a,b = map(int,input().split())
graph[a].append(b)
graph[b].append(a)
visited = [False for _ in range(n)]
def dfs(v,depth):
global ans
visited[v] = True
if depth >= 4:
ans = True
return
for next_node in graph[v]:
if not visited[next_node]:
dfs(next_node,depth+1)
visited[next_node] = False
ans = False
for i in range(n):
dfs(i,0)
visited[i] = False
if ans:
print(1)
exit()
print(0)
from itertools import combinations
def solution(orders, course):
Dict = {}
for i in orders:
arr = []
for j in i:
arr.append(j)
#print(arr)
for j in course:
if j <= len(arr):
#print(j)
n_course = list(combinations(arr,j))
for k in n_course:
elem = ''.join(sorted(k))
#print(elem)
if elem not in Dict:
Dict[elem] = 1
else:
Dict[elem] += 1
ans = []
for i in course:
Max = 2
for j in Dict:
if i == len(j):
Max = max(Max,Dict[j])
for j in Dict:
if i == len(j) and Max == Dict[j]:
ans.append(j)
return(sorted(ans))
import sys
from heapq import heappush, heappop
INF = sys.maxsize
def solution(n, s, a, b, fares):
graph = [[] for _ in range(n+1)]
for i in fares:
# ๋ฌด๋ฐฉํฅ ๊ทธ๋ํ
graph[i[0]].append([i[1],i[2]])
graph[i[1]].append([i[0],i[2]])
def dijkstra(start,target):
dp = [INF for i in range(n+1)]
heap = []
dp[start] = 0
heappush(heap,[0,start])
while heap:
wei,now = heappop(heap)
if dp[now] < wei:
continue
for next_node, w in graph[now]:
next_wei = w + wei
if next_wei < dp[next_node]:
dp[next_node] = next_wei
heappush(heap,[next_wei,next_node])
return dp[target]
ans = dijkstra(s,a) + dijkstra(s,b)
for i in range(1,n+1):
if s!= i:
ans = min(ans,dijkstra(s,i) + dijkstra(i,a) + dijkstra(i,b))
return ans
n,m = map(int,input().split())
arr = [0] + list(map(int,input().split()))
def dfs(index,snow,depth):
global ans
if depth > m:
return
if depth <= m:
ans = max(ans,snow)
if index <= n-1:
dfs(index+1,snow+arr[index+1],depth+1)
if index <= n-2:
dfs(index+2,snow//2+arr[index+2],depth+1)
return
ans = -1
dfs(0,1,0)
print(ans)
from collections import deque
dx = [0,0,1,-1]
dy = [1,-1,0,0]
n,m = map(int,input().split())
board = [list(map(str, input())) for _ in range(n)]
def bfs(x,y):
dq = deque()
dq.append((x,y))
visited = [[False]*m for _ in range(n)]
cnt = 0
while dq:
x,y = dq.popleft()
for k in range(4):
nx,ny = x+dx[k],y+dy[k]
if 0 <= nx < n and 0 <= ny < m:
if visited[nx][ny] == False:
if board[nx][ny] == 'O':
dq.append((nx,ny))
visited[nx][ny] = True
elif board[nx][ny] == 'P':
dq.append((nx,ny))
cnt+=1
visited[nx][ny] = True
if cnt == 0:
print('TT')
else:
print(cnt)
for i in range(n):
for j in range(m):
if board[i][j] == 'I':
bfs(i,j)
from collections import deque
n = int(input())
s = input()
if s.count('C') == 0:
print("NO OUTPUT")
else:
dq = deque()
NUM = ''
for i in s:
if i == 'S':
if NUM != '':
dq.append(int(NUM))
NUM = ''
dq.append('-')
elif i == 'M':
if NUM != '':
dq.append(int(NUM))
NUM = ''
dq.append('*')
elif i == 'U':
if NUM != '':
dq.append(int(NUM))
NUM = ''
dq.append('/')
elif i == 'P':
if NUM != '':
dq.append(int(NUM))
NUM = ''
dq.append('+')
elif i == 'C':
result = 0
if NUM != '':
dq.append(int(NUM))
NUM = ''
cnt = 0
while dq:
x = dq.popleft()
if cnt == 0:
result = x
cnt+=1
if x == '-':
y = dq.popleft()
result -= y
if x == '+':
y = dq.popleft()
result += y
if x == '/':
y = dq.popleft()
if result < 0 and y > 0:
result *= -1
result //= y
result *= -1
elif result > 0 and y < 0:
y *= -1
result //= y
result *= -1
else:
result //= y
if x == '*':
y = dq.popleft()
result *= y
print(result,end=' ')
dq.append(result)
else:
NUM += i
