루미 알고리즘

#1555플래티넘Bridge Building

PO 2023 결선코딩출제 Herman Lauenstein, Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Rut, who hasn't learned to swim, wants to cross a river. Fortunately, a bridge is being constructed over a section of the river, which can be represented as an N × M grid. Every hour, a bridge segment is built on a tile that was previously covered by water. For example, five bridge segments will have been built after five hours. Rut has obtained a list of the positions of the first bridge segments to be built, and she knows that she can cross the river when she can walk on the bridge from one side of the river to the other without having to swim any part of the way. She starts at row 0 and wants to reach row N-1. These two rows each have a landmass that she can use to walk along the entire river. She can move between tiles that are not covered by water by moving up, down, right, or left. She now wants to know if the given bridge segments are enough to cross, and if so, how many hours she needs to wait before the bridge is sufficiently completed for her to be able to reach the other side.

(그림은 원문 저장소에서 볼 수 있습니다)

Figure 1: Illustration of sample 1 after 4 and 7 hours. Only after 7 hours will there be a path to the other side.

Input

The first line of input contains three integers N, M (3 ≤ N, M ≤ 10^9), and T (1 ≤ T ≤ 10^5), the number of rows and columns in the grid, and the number of bridge segments to be built, respectively.

This is followed by T lines, where the i-th line contains two integers R (1 ≤ R ≤ N-2) and C (0 ≤ C ≤ M-1), the row and column where a tile is completed in the i-th hour. Note that in this problem, row 0 is the bottom row.

Output

If Rut can cross the river, print an integer: the minimum number of hours Rut needs to wait for the bridge to be sufficiently completed to walk to the other side. Otherwise, print “nej” (no).

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
110N ≤ 4
220N, M ≤ 50
330N, M ≤ 1000
415T ≤ 2000
525No additional constraints.

예제

예제 1

입력
7 3 8
2 1
1 0
4 1
5 1
2 0
3 0
4 0
3 1
출력
7

출처 표기

출처: Programmeringsolympiaden 2023년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.