cur_num = 2
stack = [1]
result = ['+']
for _ in range(n):
    target = int(input())
    if not stack:
        stack.append(cur_num)
        result.append('+')
        cur_num += 1
    while stack and stack[-1] < target:
        stack.append(cur_num)
        result.append('+')
        cur_num += 1
    if stack and stack[-1] == target:
        stack.pop()
        result.append('-')
        continue

if len(stack) == 0:
    print(*result, sep='\n')
else:
    print('NO')

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

dxy = ((1, 2), (2, 1), (-1, 2), (2, -1), (1, -2), (-2, 1), (-1, -2), (-2, -1))

x, y = map(int, input().split())

enemy_list = [tuple(map(int, input().split())) for _ in range(M)]
result = [0] * M

q = deque([(x, y, 1)])
find_cnt = 0
visited = set([(x, y)])

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

    for dx, dy in dxy:
        n_x, n_y = cur_x + dx, cur_y + dy
        if (n_x, n_y) in visited:
            continue
        if (n_x, n_y) in enemy_list:
            enemy_idx = enemy_list.index((n_x, n_y))
            if result[enemy_idx] != 0:
                continue
            result[enemy_idx] = t
            find_cnt += 1
        if find_cnt == M:
            break
        q.append((n_x, n_y, t + 1))
        visited.add((n_x, n_y))
    else:
        continue
    break

print(*result)

from collections import Counter, defaultdict

input = sys.stdin.readline
print = sys.stdout.write

N = int(input())

students = [int(input()) for _ in range(N)]
MAX_STUDENT = max(students) + 1

counter = Counter(students)
toktok = defaultdict(int)

for i in range(1, MAX_STUDENT):
    for j in range(i, MAX_STUDENT, i):
        if j in counter:
            toktok[j] += counter[i]

print("\n".join(str(toktok[s] - 1) for s in students) + "\n")

import heapq

def nag_int(s):
    """음수 정수를 반환"""
    return -int(s)

TC = int(input())
for t in range(TC):
    N, M = map(int, input().split())
    importance_list = list(map(nag_int, input().split()))
    q = deque([(i, im) for i, im in enumerate(importance_list)])
    heapq.heapify(importance_list)

    cnt = 1
    cur_min = heapq.heappop(importance_list)

    while q:
        i, im = q.popleft()
        if i == M and cur_min == im:
            # M 번째 출력되면 끝
            break
        elif cur_min == im:
            # 출력 가능하면 다음으로
            cur_min = heapq.heappop(importance_list)
            cnt += 1
        else:
            # 출력 안되면 대기열 맨 뒤로
            q.append((i, im))
    print(cnt)

N, K = map(int, input().split())
durability = deque(map(int, input().split()))
belt = deque([False] * (N * 2)) # belt 위에 로봇이 있는지 여부

PUT_IDX = 0
OUT_IDX = N - 1
round_num = 1

while True:
    # 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
    durability.rotate()
    belt.rotate()

    # 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다.
    belt[OUT_IDX] = False


    # 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
    for i in range(N - 2, -1, -1):
        # 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
        if not belt[i]:
            continue
        n_i = i + 1
        if not belt[n_i] and durability[n_i] >= 1:
            durability[n_i] -= 1
            belt[i] = False
            belt[n_i] = True
    
    # 언제든지 로봇이 내리는 위치에 도달하면 그 즉시 내린다.
    belt[OUT_IDX] = False

    # 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
    if durability[PUT_IDX]:
        durability[PUT_IDX] -= 1
        belt[PUT_IDX] = True
        
    # 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
    if durability.count(0) >= K:
        break
    round_num += 1

print(round_num)

from collections import defaultdict, deque

INF = float('inf')

def floyd(n, dist_list):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist_list[i][j] = min(dist_list[i][j], dist_list[i][k] + dist_list[k][j])

    min_sum = INF
    result = 0
    for i, sum_dist in enumerate(map(sum, dist_list), start=1):
        if min_sum > sum_dist:
            min_sum = sum_dist
            result = i

    return result

def main():
    N, M = map(int, input().split())

    dist_list = [[INF] * N for _ in range(N)]
    for i in range(0, N):
        dist_list[i][i] = 0

    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        dist_list[a][b] = 1
        dist_list[b][a] = 1
    
    print(floyd(N, dist_list))


if __name__ == "__main__":
    main()

from itertools import permutations

N = int(input())
hit_result = [list(map(int, input().split())) for _ in range(N)]

max_score = 0
# permutations는 애초에 중복 없음 → set() 필요 없음
for perm in permutations([i for i in range(1, 9)]):  # 1번 선수 제외 순열
    order = list(perm[:3]) + [0] + list(perm[3:])  # 0번(1번 선수) 4번 타자 고정

    score = 0
    idx = 0  # 타석 순서 인덱스
    for inning in hit_result:
        out = 0
        base1, base2, base3 = 0, 0, 0  # 각 루의 주자 (0/1)
        while out < 3:
            result = inning[order[idx]]
            if result == 0:
                out += 1
            elif result == 1:
                score += base3
                base1, base2, base3 = 1, base1, base2
            elif result == 2:
                score += base3 + base2
                base1, base2, base3 = 0, 1, base1
            elif result == 3:
                score += base3 + base2 + base1
                base1, base2, base3 = 0, 0, 1
            elif result == 4:
                score += base3 + base2 + base1 + 1
                base1, base2, base3 = 0, 0, 0
            idx = (idx + 1) % 9

    max_score = max(max_score, score)

print(max_score)

INF = float("inf")


def floyd(n, dist_list):
    """플로이드 워셜"""

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                dist_list[i][j] = min(
                    dist_list[i][j], dist_list[i][k] + dist_list[k][j]
                )

    return dist_list


def print_result(dist_list):
    """결과 출력"""
    for dist in dist_list[1:]:
        for d in dist[1:]:
            print(d if d != INF else 0, end=" ")
        print()


def main():
    n = int(input())
    m = int(input())

    dist_list = [[INF] * (n + 1) for _ in range(n + 1)]

    for _ in range(m):
        a, b, c = map(int, input().split())
        dist_list[a][b] = min(dist_list[a][b], c)

    for i in range(1, n + 1):
        dist_list[i][i] = 0

    dist_list = floyd(n, dist_list)
    print_result(dist_list)


if __name__ == "__main__":
    main()

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다.

출력

주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 최대 가짓수를 출력하시오.

슬라이딩 윈도우 기법을 사용하는 문제이다.

from collections import defaultdict

N, d, k, c = map(int, input().split())
sushi_list = [int(input()) for _ in range(N)]

counter = defaultdict(int)
kind = 0

for i in range(k):
    if counter[sushi_list[i]] == 0:
        kind += 1
    counter[sushi_list[i]] += 1

# 쿠폰
max_kind = kind + (1 if counter[c] == 0 else 0)

for i in range(1, N):
    remove = sushi_list[i - 1]
    counter[remove] -= 1
    if counter[remove] == 0:  # 더 이상 없으면 종류 수 감소
        kind -= 1

    cur = sushi_list[(i + k - 1) % N]
    if counter[cur] == 0:
        kind += 1
    counter[cur] += 1

    # 쿠폰
    total = kind + (1 if counter[c] == 0 else 0)
    max_kind = max(max_kind, total)  # 최대 종류 수 갱신

print(max_kind)