문제

문제를 고르고 내장 에디터에서 풀이를 작성해 보시기 바랍니다. 채점기가 실제 테스트 케이스로 코드를 바로 검증하고, 아카이브의 문제들도 자유롭게 둘러볼 수 있습니다.

전체 결과문제 5746개

제목	난이도	유형	정답자	시간 제한	메모리 제한	채점
Безопасное путешествие행성 n개와 간선 m개가 주어질 때, 같은 행성을 두 번 방문하지 않는 특정 탐욕적 이동이 모든 행성을 방문하고 시작 행성으로 돌아오는 단순 그래프를 구성한다.	어려움8	그래프그리디+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Гонки на колесницах평면 직선 그래프와 체크포인트 경로, 이동 속도와 회전 속도가 주어질 때, 연속한 체크포인트 사이의 이동 방향을 정해 총 시간을 최소화한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	8초	1024 MB	지문만 제공
Сеть дорог동심 사각형 고리 도로와 서로 교차하지 않는 방사형 도로가 주어질 때 두 점 사이의 최단 거리를 구하거나, 경로가 없으면 -1을 출력한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Достойный финал아주 큰 판에서 흰 체커가 방향을 최대 두 번만 바꾸며 연속으로 대각선 점프를 할 때, 잡을 수 있는 검은 체커의 최대 개수를 구한다.	어려움8	그래프DFS+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Помогите спасти Землю!히어로가 최대 15명이고 충돌하는 쌍이 주어질 때, 지도자가 없는 행성에 충돌 쌍이 남지 않도록 하면서 모든 히어로를 타이탄에서 지구로 옮기는 100000회 이하의 왕복 순서를 찾는다.	어려움8	그래프비트 연산+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Поиск корабля각 질의 (v,k)마다 s에서 출발한 배가 최단 경로 k번 이동으로 v에 도달할 수 있는지, 도달할 수 있다면 현재 위치가 유일한지 판정한다. 이때 최단 경로는 지나온 간선 수를 뜻한다. 힌트, 지나온 간선 수 k번 이동 후 멈춘 것인지에 대한 판단이다. 힌트, 도착점 v까지의 최단 거리 d(v)와 k의 관계를 이용한다. 힌트, k가 d(v)보다 작으면 불가능하고, k=d(v)면 v가 유일하다. 힌트, k>d(v)이고 같은 레벨에 다른 정점이 있으면 여러 위치가 가능하다. k>d(v)이고 도달 가능한 다른 정점이 없다면 그 위치가 유일하다. BFS로 거리와 레벨별 정점 수를 구해 각 질의를 O(1)에 처리한다.	어려움8	그래프BFS+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Макс и расстоянияn×n 거리 행렬이 주어질 때 이를 만들어 내는 비감소 정수 배열 x와 두 순열 a, b를 복원하거나 불가능함을 판정한다.	어려움8	그래프행렬+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Подарок Диппера문자 간 치환 비용이 주어질 때, s를 어떤 더 짧은 문자열의 반복으로 바꾸는 최소 비용을 구한다.	어려움8	최단 경로그래프+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Хэллоуин무방향 그래프의 각 정점에서 나가는 선의 절반 이하만 지우면서, 남은 선이 두 그룹 사이에만 놓이도록 정점을 둘로 나누는 문제입니다.	어려움8	그래프그리디+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Граф인접하지 않은 두 정점 사이에 간선을 추가했을 때 정확히 하나의 새로운 단순 사이클이 생기는 정점 쌍의 수를 센다.	어려움8	그래프DFS+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Ломать --- не строить각 점에서 두 개의 선분이 나가는 평면 그래프가 주어질 때, 모든 점에서 선분 하나씩을 지워 남은 선분이 서로 교차하지 않도록 할 수 있는지 판정한다.	어려움8	그래프기하+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Допрыгни, если сможешь!중간 빙산에 막히지 않으면서 첫 빙산 봉우리에서 마지막 봉우리까지 이동할 때 필요한 최소 밧줄 길이를 구한다.	어려움8	기하그래프+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
성게 밭성게 밭 그래프가 주어질 때, 하나를 채집하면 맞닿은 성게를 채집할 수 없게 되는 조건에서 최대로 채집할 수 있는 성게의 수를 구한다.	어려움8	그래프동적 계획법+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Миньоны развлекаются가중치가 있는 무방향 그래프의 모든 단순 사이클 가운데 최소 간선 가중치와 최대 간선 가중치의 합을 최대로 만드는 사이클을 찾고, 사이클이 없으면 0을 출력한다.	어려움8	그래프DFS+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
마라톤각 학생 j(벌점 j점)마다 1번에서 N번까지 정확히 j+1개의 체크포인트를 지나는 최소 시간을 구해 그 합을 998244353으로 나눈 나머지를 출력한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Ликантропия신호가 뉴런에 도달할 때마다 늑대 정령이 최대 k개의 시냅스를 끊을 수 있을 때, 신호가 심장에 닿지 못하게 막을 수 있는지 판정한다.	어려움8	그래프게임 이론+1	아직 제출이 없습니다	5초	1024 MB	지문만 제공
Заправки정점 n을 제외한 모든 정점이 두 개의 나가는 간선을 가지는 방향 그래프가 주어질 때, 1에서 n으로 가는 모든 경로가 같은 수의 표시된 정점을 지나도록 표시할 수 있는지 판정한다.	어려움8	동적 계획법그래프+1	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Боги그래프의 정점을 두 줄로 나열해서 충돌하는 모든 쌍을 선분으로 이었을 때 선분끼리 교차하지 않게 만든다.	어려움8	그래프DFS+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
One Walk무방향 그래프의 모든 간선에 방향을 주어 S에서 E로 가는 보행이 정확히 하나가 되도록 하거나, 불가능하면 -1을 출력한다.	어려움8	그래프DFS+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Эвакуация각 도로에 이동 시간과 시간당 용량이 있는 방향 그래프에서 K대의 차가 도시 1에서 도시 n까지 갈 수 있는 최소 시간을 구하고, T분 안에 불가능하면 도착하지 못하는 차의 수를 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Секретная лаборатория라벨이 붙은 n개 정점의 완전 그래프에서 비순환 방향 그래프의 개수를 10^9+7로 나눈 나머지를 구한다.	어려움8	조합론동적 계획법+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Пёсик연결된 무방향 그래프가 주어질 때, 고른 정점을 한 번씩만 지나는 가장 긴 단순 사이클을 찾아 출력한다.	어려움8	그래프그리디+1	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Parties각 도시의 지지 정당이 바뀔 때마다 같은 정당을 지지하는 두 도시 사이 최단 거리를 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Шахматная доска검은색과 흰색으로 칠해진 격자가 주어질 때, 두 방향의 대각선 전체를 다시 칠해 체스판 무늬로 만드는 최소 횟수를 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Новая игра숫자가 적힌 n×m 격자에서 양수면 그만큼 오른쪽이나 아래로, 음수면 그만큼 왼쪽이나 위로 말을 옮기며 최적의 플레이로 이기는 사람을 가리거나 무승부를 판정한다.	어려움8	그래프동적 계획법+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Железнодорожные перевозки양방향 철도망에서 생산지, 가공지, 도시 수요를 고려해 연간 얻을 수 있는 최대 이익을 구한다.	어려움8	그래프동적 계획법+1	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Усердные бобры무한한 나무 줄에서 비버가 주어진 열 개의 규칙에 따라 행동할 때 언젠가 행복 상태에 도달하는지 판정한다.	어려움8	시뮬레이션그래프+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Разложение графа2n-1의 분할이 주어질 때 K_{2n}의 변을 주어진 차수의 인자들로 나누어 구성한다.	어려움8	조합론그래프+1	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Разработка микросхем논리 회로의 입력이 초기값에서 최종값으로 바뀔 때 게이트와 배선의 임의 지연을 허용해 모든 출력이 과도 값을 갖지 않을지를 판정합니다.	어려움8	그래프그리디+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Слепые флибы이진 단어 w가 주어질 때, 1부터 \|w\|까지의 각 k에 대해 w를 무한히 반복한 문자열과 비교했을 때 k개 상태의 눈먼 플립이 가질 수 있는 최대 예측 능력을 구한다.	어려움8	동적 계획법그래프+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Три цвета이분 그래프의 각 간선을 0, 1, 2 색으로 칠해 인접한 두 정점의 간선 색 합이 다르도록 만들고, 불가능하면 -1을 출력한다.	어려움8	그래프수학+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Принцип <<горячей картошки>>각 노드의 고정된 라우팅 일정과 패킷 발생 시각이 주어질 때, 충돌 없이 목적지에 도달하도록 최대 개수의 패킷을 고른다.	어려움8	그래프시뮬레이션+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Great Wall of Flatland서로 겹치지 않고 변으로 연결된 삼각형 합집합의 경계에 놓인 변들의 길이를 모두 더한다.	어려움8	기하그래프+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
기지방호매일 C[1]에서 시작해 주어진 진법 l[k]로 끝나도록 T개의 진법을 배열할 때, 연속한 진법 사이 해밍 거리의 제곱 합을 최소로 만드는 루틴의 총피로도를 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Planning Locations of Bus Stops각 랜드마크마다 맨해튼 거리 상한 안에서 정류장을 하나씩 배치해, 서비스가 잇는 정류장 쌍 거리 합을 최소화한다.	어려움8	최단 경로그래프+2	아직 제출이 없습니다	8초	1024 MB	지문만 제공
Railroad Maintenance역과 노선의 이분 그래프에서 다리 역할을 하는 노선의 수를 센다.	어려움8	그래프DFS+1	아직 제출이 없습니다	40초	1024 MB	지문만 제공
Hey Google, Drive!명령이 남북과 동서를 각각 같은 확률로 뒤바꿀 수 있는 상황에서 어떤 시작-끝 쌍을 확률 1에 가깝게 도달할 수 있는지 판별한다.	어려움8	BFS그래프+2	아직 제출이 없습니다	60초	1024 MB	지문만 제공
Love Letter나이가 모두 다른 용들이 있고, 나이 차이만큼 시간이 걸려 편지를 보내되 친구 사이는 0의 시간이 걸린다. 용 1에서 모든 용까지의 최단 시간을 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	2.5초	1024 MB	지문만 제공
Rikkis teleporter도로는 1시간, 텔레포터는 K시간이 걸리고 균등 무작위 도시로 이동시킬 때 각 도시에서 1번 도시까지 가는 최소 기댓값을 구한다.	어려움8	그래프그리디+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Internet Monopoly연결 상태에서 간선이 온라인으로 추가될 때, 모든 최소 신장 트리가 정확히 K개의 저렴한 간선을 쓰도록 가격을 정할 수 있는지 판정한다.	어려움8	그래프최소 신장 트리+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Magical Plants식물이 임계 조건에 따라 하루에 1미터씩 자랄 때, 모든 식물이 K미터가 되는 최소 일수와 그 식재 순서를 구한다.	어려움8	그리디그래프+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Lühisõnum 7주어진 소문자 단어들을 모두 부분 문자열로 포함하는 가장 짧은 문자열을 구한다.	어려움8	문자열트라이+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Lühisõnum 9주어진 행성 이름들을 모두 부분 문자열로 포함하는 가장 짧은 소문자 문자열을 구한다.	어려움8	문자열동적 계획법+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Ralli süvakosmoses간선 k의 연료 비용이 2^k인 무방향 연결 그래프에서 두 정점 사이의 최소 연료 비용을 1e9+7로 나눈 나머지를 여러 질의에 대해 구한다.	어려움8	그래프최소 신장 트리+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Maksulised teelõigud고속도로 위 임의의 두 지점 사이에서 고속도로를 따라가는 경로가 항상 최적이 되도록 각 구간에 부과할 수 있는 통행료 합의 최댓값을 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
RingteedS가 모든 사이클에 포함된다는 조건에서 S에서 출발하는 비반복 경로가 끝날 수 있는 서로 다른 정점의 수를 센다.	어려움8	그래프DFS	아직 제출이 없습니다	1초	1024 MB	지문만 제공
차원문값의 차의 제곱만큼 마나를 쓰는 교환으로 순열을 재배열해 모든 도시를 방문하는 하나의 순환을 만들고, 최소 마나와 교환 순서를 구한다.	어려움8	그래프그리디+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
우주비행사 정민두 격자에서 매초 블랙홀이 지그재그 기류를 따라 생기고, 3초가 걸리는 차원 이동 게이트를 이용해 우주선까지 가는 최단 시간을 구한다.	어려움8	BFS그래프+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
치즈버거각 체인점은 배송 시간이 가장 짧은 농장 중 가장 싼 치즈를 사며, 그 가격을 출력하거나 불가능하면 -1을 출력한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Žemėlapio atkūrimas여러 번의 국소 변환으로 만들어진 그래프가 주어졌을 때, 변환 이전 그래프에서 각 정점의 차수가 1부터 5였던 개수를 각각 구한다.	어려움8	그래프수학+1	아직 제출이 없습니다	1초	1024 MB	지문만 제공
King Animesh decides to have a voyage to the sun모든 완전 매칭의 비용이 같아지는 완전 이분 그래프로 유일하게 완성되는 일부 간선 비용이 주어질 때, 모든 간선 비용 제곱의 합을 구한다.	어려움8	그래프수학+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Animesh does not gift Malvika on her birthday모든 행과 열이 1을 적어도 n-3개 포함하는 인접 행렬로 주어진 그래프 G와 동형인 라벨 그래프의 개수를 세어 1e9+7로 나눈 나머지를 구합니다.	어려움8	그래프조합론+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
V정점에 정수가 적힌 그래프에서 정점 하나와 이웃 두 개를 골라 두 이웃에 같은 k를 더하는 연산을 반복해 모든 값을 같게 만들 수 있는지 판정합니다.	어려움8	그래프수학+1	아직 제출이 없습니다	2초	1024 MB	지문만 제공
차량 배치각 차량이 사전순 최단 경로로 1번 지점에 도착할 때 도착 시간이 겹치지 않도록 차량을 배치하는 경우의 수를 구한다.	어려움8	그래프BFS+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Bad Bunny연결된 무방향 그래프에서 각 질의 (s, d)마다 s에서 d로 가는 모든 단순 경로가 지나는 정점의 수를 구한다.	어려움8	그래프DFS+2	아직 제출이 없습니다	6초	1024 MB	지문만 제공
Arc of Triumph 9주어진 석조 아치를 모든 블록이 항상 안정한 상태로 쌓아 올리려면 임시 나무 블록이 최소 몇 개 필요한지와 그 배치 순서를 구한다.	어려움8	시뮬레이션그리디+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Arc of Triumph 10계획된 아치를 한 블록씩 쌓되 매 순간 모든 블록이 안정하도록 임시 나무 블록을 최소로 써서 건설 순서를 출력한다.	어려움8	시뮬레이션그리디+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
The Deer Hunter조용한 칸과 시끄러운 칸으로 이루어진 격자에서 P-22가 몰래 접근한 뒤 달아나는 사슴을 잡되, 경계에 도달하기 전에 잡을 수 있는 최소 추격 시간을 구한다.	어려움8	그래프BFS+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Fortification각 지점의 방어 작업 시간과 도로가 물에 잠기는 시각이 주어질 때, 차고지 1에서 출발해 돌아오는 경로로 방어할 수 있는 지점 수의 최댓값을 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Water Contamination침수된 연결로 오염원이 확산될 때, 오염된 장소에서 중요한 장소로 가는 경로를 모두 끊는 최소 간선 수를 구한다.	어려움8	그래프최소 신장 트리	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Margučiai각 노드에 들어오는 간선이 최대 하나인 방향 그래프에서 시작 노드를 최대 M개 골라 도달할 수 있는 노드 수의 최댓값을 구한다.	어려움8	그래프그리디+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Flea각 칸의 화살표 방향으로 최대 K칸씩 점프해 사각형 밖으로 나갈 수 있는 시작 칸의 수를 센다.	어려움8	그래프DFS+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Exceeding Limits길이와 제한속도가 있는 도로 그래프에서 1번에서 n번까지 최단 시간이 t 이하가 되도록 모든 제한속도에 더할 최소 속도 x를 구한다.	어려움8	이분 탐색최단 경로+1	아직 제출이 없습니다	8초	1024 MB	지문만 제공
목걸이 만들기N개 구슬의 고리와 M개 구슬이 나무 모양 장식으로 붙은 목걸이 두 개가 주어질 때, 두 목걸이가 같은지 판정한다.	어려움8	그래프트리+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
그래프 게임홀수 사이클이 생기지 않도록 간선을 하나씩 K개 추가하고, 불가능하면 NO를 출력하는 문제입니다.	어려움8	그래프유니온 파인드+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Journey of the Robber각 도시의 부가 순위로 주어진 트리에서, 모든 도시에 대해 자신보다 부유한 도시 중 가장 가까운 곳을 찾고 거리가 같으면 더 가난한 쪽을 고른다.	어려움8	트리그래프+2	아직 제출이 없습니다	4.5초	1024 MB	지문만 제공
Meeting Point가중 무방향 그래프에서 P에서 Q로 가는 모든 최단 경로가 G를 지나고 G가 그 중점이 되는 모든 Q를 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	0.5초	1024 MB	지문만 제공
International Irregularities감염도 순으로 정렬된 국가들과 격리 비용이 주어질 때, 각 출발지와 도착지 사이의 최단 이동 시간을 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
꼬치구이고기, 파, 버섯으로 채워진 격자에서 버섯을 끝으로 하는 길이 3의 직선(가로, 세로, 대각선) 중 나머지 두 칸이 고기와 파인 꼬치의 최대 개수를 구한다. 버섯은 재사용할 수 있지만 고기와 파는 한 번만 쓴다.	어려움8	그래프완전 탐색+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Impartial StringsS와 T가 부분 문자열로 나타나는 횟수가 같은 문자열만 생성하는 유한 오토마타를 만들 수 있는지 판정한다.	어려움8	동적 계획법그래프+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
A Complex Problem여러 복잡도 클래스 사이의 부분집합 및 진부분집합 관계가 주어질 때, 이와 모순되지 않는 서로 다른 클래스 개수의 최솟값과 최댓값을 구한다.	어려움8	그래프유니온 파인드+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Building RoadsN개의 점이 주어질 때 최소 신장 트리를 만들고, 두 점 사이 최단 거리 중 가장 긴 값인 지름을 최소화하여 출력한다.	어려움8	최소 신장 트리그래프+1	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Journey of Recovery예정된 항공편과 계획된 여정이 주어질 때, 여정 중 한 편이 취소되면 최적으로 재경로를 짜서 도착이 얼마나 늦어지는지 최악의 경우를 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	8초	1024 MB	지문만 제공
Hamster단위 격자 위에 놓인 벽 조각들이 주어질 때, 닫힌 영역이 생기도록 추가해야 하는 단위 벽 조각의 최소 개수를 구한다.	어려움8	그래프유니온 파인드+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Королевская задача가중치가 있는 방향 그래프에서 a에서 b로 가는 모든 경로의 가중치 XOR을 다시 XOR한 값을 구하고, 정의되지 않으면 -1을 출력한다.	어려움8	그래프DFS+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Mostovi두 끝점을 제거했을 때 남은 n-2개 노드의 그래프가 연결되지 않게 되는 간선의 수를 센다.	어려움8	그래프DFS+1	아직 제출이 없습니다	3초	1024 MB	지문만 제공
제곱수 원순열1부터 N까지를 원형으로 배치해 이웃한 두 수의 합과 처음과 끝의 합이 모두 제곱수가 되도록 한다.	어려움8	그래프백트래킹+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Assigning Fares트리 위에서 주어진 각 경로의 방향을 정해 방문 순서대로 역 요금 구역이 증가하도록 번호를 매기고, 최댓값을 최소화하거나 불가능을 판정한다.	어려움8	그래프위상 정렬+2	아직 제출이 없습니다	6초	1024 MB	지문만 제공
스패닝 최소 트리정점 N개, 간선 M개이며 가중치가 1부터 M까지 하나씩인 단순 그래프를 만들어 최소 스패닝 트리 가중치 합이 정확히 S가 되도록 하거나, 불가능하면 -1을 출력한다.	어려움8	그래프최소 신장 트리+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Петя и монеты서로 다른 재료로 만들어진 동전 쌍들이 주어지고 구리 동전이 정확히 하나일 때, 구리일 수 있는 동전을 모두 찾는다.	어려움8	그래프BFS+1	아직 제출이 없습니다	6초	1024 MB	지문만 제공
Блуждания в большом городе그래프가 주어질 때, 매 단계 임의 선택을 하는 학생이 유한한 시간 안에 반드시 t에 도달할 수 있는지 판정하고, 보장되는 최소 시간을 구한다.	어려움8	그래프BFS+2	아직 제출이 없습니다	5초	1024 MB	지문만 제공
Дорога на олимпиаду간선이 추가되고 삭제되는 가중 무향 그래프에서 두 도시 사이의 간선 두 개 이하 최소 비용 경로를 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Data Center Maintenance각 고객 데이터의 복제본 두 개가 서로 다른 시간에 유지되도록, 유지보수 시각을 한 시간 미루는 데이터 센터의 최소 집합을 구한다.	어려움8	그래프유니온 파인드+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Дома в Берляндии가족 수가 다른 두 거주 교차점 사이의 최단 거리를 구한다.	어려움8	그래프BFS+1	아직 제출이 없습니다	2초	1024 MB	지문만 제공
Включи свет, закрой двери!방의 수가 50 이하이고 문의 수가 100 이하인 미로를 탐험하면서 모든 방의 불을 켜고 현재 방을 제외한 모든 방을 잠그는 문제로, 질의 횟수는 30000을 넘지 않아야 한다.	어려움8	그래프DFS+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
План бегства각 방에서 신호가 울리면 가장 가까운 K개의 출구가 번호 순으로 닫힐 때, 남은 출구 중 가장 가까운 방을 찾고 없으면 -1을 출력한다.	어려움8	그래프BFS+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
페인트 칠하기색이 칠해진 무방향 그래프에서 이동 경로로 각 건물을 목표 색으로 칠할 수 있는지 판정하고, 방문 횟수 1,000,000 이하의 실제 방문 순서를 출력한다. 색 c의 도로로 건물에 들어가면 그 건물은 c로 덧칠된다.	어려움8	그래프DFS+2	아직 제출이 없습니다	1.5초	1024 MB	지문만 제공
두 체스판두 체스판에 룩이 N개씩 있고, 교환을 통해 각 체스판에서 같은 행이나 열에 룩이 겹치지 않게 만드는 최소 교환 횟수를 구한다.	어려움8	그래프조합론+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Отличная лекция각 학생에 대해, 강의의 함의를 순서대로 들을 때 학생이 거짓이라 믿는 명제를 처음으로 도출하게 되는 시점을 구한다.	어려움8	그래프유니온 파인드+2	아직 제출이 없습니다	3초	1024 MB	지문만 제공
Walk Swapping사이클 위 두 동전 배치가 주어질 때, 인접한 두 정점의 동전을 연속으로 교환하는 걷기로 처음 배치를 최종 배치로 바꾸는 최소 교환 횟수를 구한다.	어려움8	그래프동적 계획법+1	아직 제출이 없습니다	1초	2048 MB	지문만 제공
빨리 기다리기배차 간격을 무시하고 최대 K번 버스를 즉시 출발시킬 수 있을 때 1번 정류장에서 N번 정류장까지의 최소 이동 시간을 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	2초	1024 MB	지문만 제공
저녁 뭐 먹지?2절 조항이 하나씩 추가될 때마다 지금까지의 모든 조항을 동시에 만족시키는 배정이 존재하는지 판정하는 문제다.	어려움8	그래프유니온 파인드+2	아직 제출이 없습니다	2.5초	1024 MB	지문만 제공
Pay2Win보스 패턴을 돈을 내고 건너뛰어 매 라운드마다 N번 구역에 도착해야 할 때, H번의 라운드를 버티는 데 드는 최소 비용이 가장 큰 시작 구역을 찾는다.	어려움8	그래프시뮬레이션+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공
Galaxy Quest3차원 공간의 행성과 행성 사이 고속도로가 주어질 때, 각 임무마다 목표 행성에 시간 안에 도착하는 데 필요한 최소 연료를 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	5초	1024 MB	지문만 제공
Isolated Island울타리로 나뉜 평면 영역에서 바다까지 가는 최소 비용이 같은 인접 영역 쌍이 있는지 판정한다.	어려움8	그래프기하+2	아직 제출이 없습니다	8초	1024 MB	지문만 제공
Keys방과 문으로 이루어진 무방향 그래프에서 열쇠를 앨리스(0에서 1)와 밥(1에서 0)에게 나눠 주되, 앨리스가 가는 길에 열쇠를 두면 밥이 주워 쓸 수 있게 하는 경로와 열쇠 배분을 구한다.	어려움8	그래프DFS+2	아직 제출이 없습니다	4초	1024 MB	지문만 제공
Labelled Paths각 정점 t마다 s에서 t로 가는 경로 중 간선 레이블을 이어 붙인 문자열이 사전순으로 가장 작은 경로를 출력하고, 도달할 수 없으면 0을 출력한다.	어려움8	문자열정렬+2	아직 제출이 없습니다	15초	1024 MB	지문만 제공
What's your ETA?양 끝 정류장의 재난 코드 합이 소수인 도로만 이용해 1번에서 N번 정류장까지 가는 최단 시간을 구한다.	어려움8	그래프최단 경로+2	아직 제출이 없습니다	1.5초	512 MB	지문만 제공
약간 모자라지만 착한 친구야캠퍼스에서 출발해 모든 동네를 정확히 한 번씩 방문하고 다시 캠퍼스로 돌아오는 닫힌 경로 가운데, 사진 촬영 순서 제약을 지키면서 걸리는 시간이 최소인 경로를 찾는다.	어려움8	동적 계획법비트 연산+2	아직 제출이 없습니다	1초	512 MB	지문만 제공
파댕이의 학교 탈출 대작전!정해진 주기 경로를 따라 움직이는 선생님들이 있는 격자에서, 학생이 5의 배수 시각에만 이동해 교실 (1,1)에서 (N,M)까지 가서 K만큼 식사하고 T 안에 교실로 돌아올 수 있는지 판정한다.	어려움8	BFS시뮬레이션+2	아직 제출이 없습니다	1초	1024 MB	지문만 제공