Posts

def distance(x1, y1, x2, y2, r_squared):
    dist_sq = (x2 - x1) ** 2 + (y2 - y1) ** 2
    return dist_sq <= r_squared

def solve():

    N, R, D, X, Y = map(int, input().split())

    graph = [[0, 0]]
    for _ in range(N):
        graph.append(list(map(float, input().split())))

    v = [False] * (N + 1)
    
    q = deque([(X, Y, 0)])
    
    result = 0.0
    
    r_sq = R * R

    while q:
        cur_x, cur_y, count = q.popleft()

        for i in range(1, N + 1):
            target_x, target_y = graph[i]

            if not v[i] and distance(cur_x, cur_y, target_x, target_y, r_sq):
                v[i] = True

                result += (D / (2 ** count))
                
                q.append((target_x, target_y, count + 1))

    print(result)
solve()

N, M = map(int, input().split())
grid = [list(input().strip()) for _ in range(M)]
visited = set()

dxy = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(x, y, team):
    q = deque([(x, y)])
    visited.add((x, y))
    count = 1
    
    while q:
        x, y = q.popleft()
        
        for dx, dy in dxy:
            nx, ny = x + dx, y + dy
            
            if not(0 <= nx < M and 0 <= ny < N):
                continue
            if (nx, ny) in visited:
                continue
            if grid[nx][ny] != team:
                continue
            visited.add((nx, ny))
            q.append((nx, ny))
            count += 1
    return count

white_power = 0
blue_power = 0

for i in range(M):
    for j in range(N):
        if (i, j) in visited:
            continue
        team = grid[i][j]
        count = bfs(i, j, team)
        if team == 'W':
            white_power += count ** 2
        else:
            blue_power += count ** 2

print(white_power, blue_power)

def bfs(n):
    q = deque([1])
    while q:
        cur = q.popleft()
        for n_num in (cur * 10 + 0, cur * 10 + 1):
            if len(str(n_num)) > 100:
                continue
            
            if n_num % n == 0:
                return n_num
            q.append(n_num)

while True:
    n = int(input())
    if n == 0:
        break

    print(bfs(n))

O(2^100) (worst case, but pruned by modulo check)

n = int(input())
cards = list(map(int, input().split()))

ans = n - 2

# 모든 가능한 두 카드 조합 (i, j)에 대해 확인
for i in range(n):
    for j in range(i + 1, n):
        if (cards[j] - cards[i]) % (j - i) != 0:
            continue
        d = (cards[j] - cards[i]) // (j - i)
        cnt = 0
        
        for k in range(n):
            expected = cards[i] + (k - i) * d
            if cards[k] != expected:
                cnt += 1
        
        ans = min(ans, cnt)

print(ans)

input = sys.stdin.readline

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

graph = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

def bfs(start):
    q = deque([(start, 0)])
    visited = [-1] * (N + 1)
    visited[start] = 0
    
    while q:
        cur_node, d = q.popleft()
        for n_node in graph[cur_node]:
            if visited[n_node] != -1:
                continue
            visited[n_node] = d + 1
            q.append((n_node, d + 1))

    return visited[1:]

print(*bfs(R), sep='\n')

D, N = map(int, input().split())
oven = list(map(int, input().split()))
doughs = list(map(int, input().split()))

min_oven = oven[0]
for i in range(1, D):
    min_oven = min(min_oven, oven[i])
    oven[i] = min(oven[i], min_oven)

oven_i = D - 1
dough_i = 0

while dough_i < N:
    if oven[oven_i] < doughs[dough_i]:
        # 못들어감
        oven_i -= 1
        if oven_i < 0:
            # 다 들어갈 수 없음
            print(0)
            break
    else:
        dough_i += 1
        oven_i -= 1

else:
    print(oven_i + 2)

from collections import defaultdict, deque

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

taller = defaultdict(list)
shorter = defaultdict(list)

for _ in range(M):
    a, b = map(int, input().split())
    taller[a].append(b)
    shorter[b].append(a)

def bfs(graph, start):
    visited = set()
    q = deque([start])
    while q:
        node = q.popleft()
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                q.append(n)
    return visited

result = 0
for i in range(1, N+1):
    visited_taller = bfs(taller, i)
    visited_shorter = bfs(shorter, i)
    # 앞 뒤의 키를 모두 탐색 가능할 경우
    if len(visited_taller) + len(visited_shorter) == N - 1:
        result += 1

print(result)

n, w, L = map(int, input().split())
trucks = list(map(int, input().split()))

bridge = deque([0] * w)
t = 0
cur_w = 0
i = 0

while i < n:
    t += 1
    cur_w -= bridge.popleft()
    if cur_w + trucks[i] <= L:
        bridge.append(trucks[i])
        cur_w += trucks[i]
        i += 1
    else:
        bridge.append(0)

t += w
print(t)

field = list(map(list, [input() for _ in range(12)]))

dyx = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def bfs(sy, sx):
    visited = set()
    q = [(sy, sx)]
    visited.add((sy, sx))
    while q:
        y, x = q.pop(0)
        for dy, dx in dyx:
            ny, nx = y + dy, x + dx
            if not(0 <= ny < 12 and 0 <= nx < 6):
                continue
            if (ny, nx) in visited:
                continue
            
            if field[ny][nx] == field[sy][sx]:
                visited.add((ny, nx))
                q.append((ny, nx))
    
    if len(visited) >= 4:
        for y, x in visited:
            field[y][x] = '.'
        return True
    return False

cnt = 0
while True:
    is_remove = False
    for i in range(12):
        for j in range(6):
            if field[i][j] == '.':
                continue

            if bfs(i, j):
                is_remove = True

    if not is_remove:
        break

    # 블록 내리기
    for j in range(6):
        stack = []
        for i in range(11, -1, -1):
            if field[i][j] == '.':
                continue
            
            stack.append(field[i][j])
            field[i][j] = '.'
        
        i = 11
        while stack:
            field[i][j] = stack.pop(0)
            i -= 1

    cnt += 1

print(cnt)