Coding 공부

import sys

input = sys.stdin.readline

D,N,M = map(int,input().split())

arr = [0]+[int(input()) for _ in range(N)]

arr.sort()
arr.append(D)
left = 0
right = D
ans = float('inf')
while left<=right:
    mid = (left+right)//2
    cnt = 0
    post_ind = 0
    for ind in range(1,N+2):
        if arr[ind] - arr[post_ind] <= mid:
            cnt += 1
        else:
            post_ind = ind
    
    if cnt > M:
        right = mid -1
    else:
        left = mid + 1

print(left)

import sys
input = sys.stdin.readline

D,N,M = map(int,input().split())


arr = [D] + [int(input()) for _ in range(N)]

arr.sort()
left = 0
right = D
ans = 0
while left<=right:
    mid = (left+right)//2
    past_island = 0
    cnt = 0
    for island in arr:
        if island - past_island >= mid:
            cnt += 1
            past_island = island
    
    if cnt >= N-M+1:
        ans = max(ans,mid)
        left = mid + 1
    else:
        right = mid -1

print(ans)

import sys

input = sys.stdin.readline

N = int(input())
A= []
B = []
C = []
D = []
for _ in range(N):
    a,b,c,d = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)
part_one = {}
for a in A:
    for b in B:
        if part_one.get(a+b):
            part_one[a+b] += 1
        else:
            part_one[a+b] = 1
answer = 0
for c in C:
    for d in D:
        temp_sum = -(c+d)
        if part_one.get(temp_sum):
            answer += part_one[temp_sum]



print(answer)

# skrud3021 님 코드 공부한거
N = int(input())

A,B,C,D = [],[],[],[]


for _ in range(N):
    a,b,c,d = map(int,input().split())
    A.append(a)
    B.append(b)
    C.append(c)
    D.append(d)


ab_sum = [i+j for i in A for j in B]
ab_sum.sort()
ab_sum.append(2<<29+1)
cd_sum = [i+j for i in C for j in D]
cd_sum.sort(reverse=True)
cd_sum.append(2<<29+1)
ab_ind = 0
cd_ind = 0
result = 0
while ab_ind <N**2 and cd_ind<N**2:
    sum_mid = ab_sum[ab_ind] + cd_sum[cd_ind]
    if sum_mid > 0:
        cd_ind += 1
    elif sum_mid < 0:
        ab_ind += 1
    else:
        ab_start_ind = ab_ind
        cd_start_ind = cd_ind
        ab_value = ab_sum[ab_ind]
        cd_value = cd_sum[cd_ind]
        while ab_value == ab_sum[ab_ind]:
            ab_ind += 1
        while cd_value == cd_sum[cd_ind]:
            cd_ind += 1
        
        result = result + (ab_ind-ab_start_ind)*(cd_ind-cd_start_ind)

print(result)

def founded(cnt):
    global result
    if cnt == 15:
        if sum(list(map(sum,win_draw_defeat))) == 0:
            result = 1
            return
    else:
        origin_number = origin_team[cnt]
        next_number = next_team[cnt]
        for idx in range(3):
            origin_team_score = idx
            next_team_score = 2-idx
            if win_draw_defeat[origin_number][origin_team_score] > 0 and win_draw_defeat[next_number][next_team_score]:
                win_draw_defeat[origin_number][origin_team_score] -= 1
                win_draw_defeat[next_number][next_team_score] -= 1
                founded(cnt+1)
                win_draw_defeat[origin_number][origin_team_score] += 1
                win_draw_defeat[next_number][next_team_score] += 1


from collections import deque
origin_team = [0,0,0,0,0,1,1,1,1,2,2,2,3,3,4]
next_team = [1,2,3,4,5,2,3,4,5,3,4,5,4,5,5]
answer = []
for _ in range(4):
    score = deque(map(int,input().split()))
    win_draw_defeat = []
    result = 0
    for _ in range(6):
        temp = []
        for _ in range(3):
            temp.append(score.popleft())
        win_draw_defeat.append(temp)
    founded(0)
    answer.append(result)
print(*answer)

N,M = map(int,input().split())
arr =  [ int(input()) for _ in range(N)]
left = max(arr)
right = 100000001
answer = float('inf')
while left<=right:
    mid = (left+right)//2
    temp = mid
    cnt = 1
    for num in arr:
        if temp >= num:
            temp -= num
        else:
            temp = mid - num
            cnt += 1
    
    if cnt >M:
        left = mid + 1
    else:
        right = mid - 1
        answer = min(answer,mid)

print(answer)

N = int(input())
arr = [input() for _ in range(N)]

start = 0
end = N-1

result = []

while start <= end:
    if arr[start] < arr[end]:
        result.append(arr[start])
        start += 1
    elif arr[start] > arr[end]:
        result.append(arr[end])
        end -= 1
    else:
        next_start = start
        next_end = end
        flag = True
        while arr[next_end] == arr[next_start]:
            if next_end >0:
                next_end -= 1
            if next_start < N:
                next_start += 1
            if arr[next_start] < arr[next_end]:
                flag = True
            elif arr[next_start] > arr[next_end]:
                flag = False

        if flag:
            result.append(arr[start])
            start += 1
        else:
            result.append(arr[end])
            end -= 1




lens = len(result)

if lens <= 80:
    print(''.join(result))
else:
    for ind in range(lens//80+1):
        if ind == lens//80:
            print(''.join(result[ind*80:]))
        else:
            print(''.join(result[ind*80:(ind+1)*80]))

from collections import deque

def bfs(node):
    stack = deque()
    stack.append(node)

    while stack:
        node = stack.popleft()

        for next_node in graph[node]:
            if visited[next_node] == -1:
                visited[next_node] = visited[node] + 1

                stack.append(next_node)



N, M = map(int,input().split())
INF = float('inf')
visited = [-1]*(N+1)


visited[1] = 0

graph =[[] for _ in range(N+1)]


for _ in range(M):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
bfs(1)

max_value = max(visited)
max_ind = -1
for k in range(1,N+1):
    if visited[k] == max_value:
        max_ind = k
        break
print(max_ind,max_value,visited.count(max_value))

import sys
from collections import deque
input = sys.stdin.readline

for _ in range(int(input())):
    M,N = map(int,input().split())
    arr = []
    sange = []
    fire_set = set()
    visited = [[True]*M for _ in range(N)]
    for x in range(N):
        input_list = list(input().strip())
        for y in range(M):
            if input_list[y] == '*':
                fire_set.add((x,y))
            elif input_list[y] == '@':
                sange.append((x,y))
                visited[x][y] = False
                input_list[y] = '.'
        arr.append(input_list)
    
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    times = 0
    result = 'IMPOSSIBLE'
    flag = False
    while sange:
        new_sange = []
        new_fire = set()
        for fire in fire_set:
            for i in range(4):
                nx = fire[0] + dx[i]
                ny = fire[1] + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] == '.':
                        new_fire.add((nx,ny))
                        arr[nx][ny] = '*'
        for sa in sange:
            for i in range(4):
                nx = sa[0] + dx[i]
                ny = sa[1] + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if visited[nx][ny] and arr[nx][ny] == '.':
                        new_sange.append((nx,ny))
                        visited[nx][ny] = False
                else:
                    result = times+1
                    flag = True
                    break
        if flag:
            break
        times += 1
        sange = new_sange[:]
        fire_set = new_fire

    print(result)
                

import sys
from collections import deque
input = sys.stdin.readline

def bfs(stack):
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    while stack:
        x,y = stack.popleft()
        flag = visited[x][y] if visited[x][y] != 'FIRE' else 'FIRE'
        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 and (arr[nx][ny] == '.' or arr[nx][ny] == '@'):
                    if flag == 'FIRE':
                        visited[nx][ny] = flag
                    else:
                        visited[nx][ny] = flag + 1
                    stack.append((nx,ny))
            else:
                if flag != 'FIRE':
                    return flag + 1
    return 'IMPOSSIBLE'





for _ in range(int(input())):
    M,N = map(int,input().split())
    stack = deque()
    arr = []
    visited = [[-1]*M for _ in range(N)]
    for x in range(N):
        input_list = input()
        for y in range(M):
            if input_list[y] == '*':
                stack.append((x,y))
                visited[x][y] = 'FIRE'
            elif input_list[y] == '@':
                start = (x,y)
                visited[x][y] = 0
        arr.append(input_list)
    stack.append(start)
    print(bfs(stack))

import sys
input = sys.stdin.readline
def union_find(x,y):
    a = find_parent(x)
    b = find_parent(y)
    if a != b:
        make_set[b] = a
        friend_cnt[a] += friend_cnt[b]

    return a

def find_parent(A):
    if make_set[A] == A:
        return A
    make_set[A] = find_parent(make_set[A])
    return make_set[A]


T = int(input())

for tc in range(T):
    F = int(input())
    person_dict = {}
    cnt = 1
    make_set = [k for k in range(F*2+1)]
    friend_cnt = [1 for k in range(F*2+1)]
    for _ in range(F):
        x,y = input().split()
        if x not in person_dict:
            person_dict[x] = cnt
            friend_cnt[person_dict[x]] = 1
            cnt += 1
        if person_dict.get(y) == None:
            person_dict[y] = cnt
            friend_cnt[person_dict[y]] = 1
            cnt += 1
        x_num = person_dict[x]
        y_num = person_dict[y]
        k = union_find(x_num,y_num)
        print(friend_cnt[k])