D - 救急車 (Ambulance) Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

The IOI Kingdom is represented as a square grid of L rows and L columns. The rows are numbered 1, 2, \ldots, L from top to bottom and the columns are numbered 1, 2, \ldots, L from left to right. A cell at row i (1 \le i \le L) and column j (1 \le j \le L) is denoted as cell (i, j).

Recently, due to a widespread infection in the IOI Kingdom, the demand for improved medical facilities has increased. In response, the king, Bitaro, has decided to build hospitals in the four corners of the grid, which are cell (1, 1), cell (1, L), cell (L, 1), and cell (L, L). Each hospital is equipped with one ambulance.

The cautious Bitaro decided to run a simulation to prepare for actual emergency calls from patients. In the scenario he envisioned, emergency calls from N patients arrive at time 0, and he wants to determine whether all patients can be transported to one of the hospitals by time T. The k-th patient (1 \le k \le N) is located at cell (X_{k}, Y_{k}).

The ambulances transport patients according to the following rules:

  • Each ambulance can start moving at time 0 or later. It repeats the following (possibly 0 times): depart from its hospital, move to the patient’s location, pick up the patient, and then return to the hospital to drop off the patient.
  • Each ambulance can carry at most 1 patient at a time.
  • Each ambulance can only transport patients to the hospital where it was initially stationed. Patients cannot be dropped off at any location other than a hospital.
  • Each ambulance moves to an adjacent cell (up, down, left, or right) in 1 unit of time. The time taken to pick up and drop off a patient can be ignored.
  • Ambulances from different hospitals may occupy the same cell at the same time.

Unfortunately, Bitaro was unable to determine the outcome of his envisioned scenario, so he has asked you to investigate it on his behalf.

Given the size of the IOI Kingdom and the scenario envisioned by Bitaro, write a program to determine whether all patients can be transported to a hospital by time T.

Input

The input is given from Standard Input in the following format:

L N T
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print Yes if all patients can be transported to a hospital by time T in the scenario envisioned by Bitaro. Otherwise, print No. The output should consist of a single line.

Constraints

  • 3 \le L \le 10\,000.
  • 1 \le N \le 160.
  • 1 \le T \le 20\,000.
  • 1 \le X_{k} \le L (1 \le k \le N)
  • 1 \le Y_{k} \le L (1 \le k \le N)
  • (X_{k}, Y_{k}) is not equal to any of (1, 1), (1, L), (L, 1), or (L, L). (1 \le k \le N)
  • All input values are integers.

Subtasks

  1. (4 points) T \le 50.
  2. (8 points) T \le 160.
  3. (5 points) N \le 10.
  4. (18 points) N \le 20.
  5. (15 points) N \le 45. L is an odd number, and Y_k = \frac{L+1}{2} (1 \le k \le N).
  6. (31 points) N \le 45.
  7. (19 points) No additional constraints.

Sample Input 1

6 4 8
1 3
2 2
3 4
5 5

Sample Output 1

Yes

By transporting the 1st and 2nd patients to the hospital at (1, 1), the 3rd patient to the hospital at (1, 6), and the 4th patient to the hospital at (6, 6), all patients can be transported to a hospital by time 8, so the output is Yes.

For example, if the ambulance stationed at the hospital in (1, 1) moves in the following order, it can transport both the 1st and 2nd patients to the hospital by time 8.

Time Ambulance Status
0 Departs from cell (1, 1)
1 Arrives at cell (2, 1)
2 Arrives at cell (2, 2), picks up the 2nd patient, and departs
3 Arrives at cell (1, 2)
4 Arrives at cell (1, 1), drops off the 2nd patient, and departs
5 Arrives at cell (1, 2)
6 Arrives at cell (1, 3), picks up the 1st patient, and departs
7 Arrives at cell (1, 2)
8 Arrives at cell (1, 1), drops off the 1st patient

This sample input satisfies the constraints of subtasks 1, 2, 3, 4, 6 and 7.

Sample Input 2

9 5 19
5 5
5 5
7 5
2 5
9 5

Sample Output 2

No

Since it is not possible to transport all patients to a hospital by time 19, the output is No.

This sample input satisfies the constraints of all subtasks.

Sample Input 3

7 7 16
6 1
2 4
4 5
5 5
3 4
6 4
5 1

Sample Output 3

Yes

This sample input satisfies the constraints of subtasks 1, 2, 3, 4, 6 and 7.

Sample Input 4

200 15 800
126 45
196 40
43 58
96 13
28 33
44 55
60 22
58 156
135 183
44 29
92 182
157 138
30 132
175 87
166 57

Sample Output 4

No

This sample input satisfies the constraints of subtasks 4, 6 and 7.

配点 : 100 点

問題文

IOI 王国は縦 L 行,横 L 列のマス目で表される領土を持っている.以降,上から i 行目 (1 \leqq i \leqq L),左から j 列目 (1 \leqq j \leqq L) のマスをマス (i, j) と表すことにする.

最近の IOI 王国では感染症で倒れる患者が相次いでおり,国民から医療の充実を求める声が上がっている.そこで,IOI 王国の国王であるビ太郎は,マス (1, 1),マス (1, L),マス (L, 1),マス (L, L) の 4 箇所に病院を建設し,それぞれの病院に 1 台ずつ救急車を設置することにした.

用心深いビ太郎は,実際に患者から救助要請があったときのことを想定してシミュレーションを行うことにした.ビ太郎が想定するシナリオでは,時刻 0 において N 人の患者から救助要請が届くので,時刻 T までにすべての患者をいずれかの病院に搬送することができるかどうかを調べたい.k 番目 (1 \leqq k \leqq N) の患者はマス (X_k, Y_k) にいる.

救急車は以下の規則に従って患者を搬送する.

  • それぞれの救急車は,時刻 0 以降に動き出すことができ,病院を出発し患者の存在するマスまで移動して患者を乗せ,再び病院まで移動して患者を降ろすことを繰り返す.
  • それぞれの救急車は高々 1 人の患者を乗せることができる.
  • それぞれの救急車は,その救急車が設置されている病院にしか患者を搬送することができず,病院が存在しないマスで患者を降ろしてはならない.
  • それぞれの救急車は,1 単位時間かけて上下左右いずれかに隣接するマスに移動することができ,患者を乗せるのにかかる時間および降ろすのにかかる時間は無視できる.
  • 異なる病院に設置されている救急車が同時に同じマスに存在することは可能である.

残念ながら,ビ太郎は自分の想定したシナリオの結果を調べることはできなかったため,あなたに代わりに調べるよう依頼してきた.

IOI 王国の領土の大きさおよびビ太郎が想定したシナリオの情報が与えられたとき,時刻 T までにすべての患者をいずれかの病院に搬送することができるかどうかを求めるプログラムを作成せよ.


入力

入力は以下の形式で標準入力から与えられる.

L N T
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

標準出力に,ビ太郎が想定したシナリオにおいて時刻 T までにすべての患者をいずれかの病院に搬送することができるなら Yes を,そうでないなら No を 1 行に出力せよ.

制約

  • 3 \leqq L \leqq 10\, 000.
  • 1 \leqq N \leqq 160.
  • 1 \leqq T \leqq 20\, 000.
  • 1 \leqq X_k \leqq L (1 \leqq k \leqq N)
  • 1 \leqq Y_k \leqq L (1 \leqq k \leqq N)
  • (X_k, Y_k) は (1, 1), (1, L), (L, 1), (L, L) のいずれでもない (1 \leqq k \leqq N).
  • 入力される値はすべて整数である.

小課題

  1. (4 点) T \leqq 50.
  2. (8 点) T \leqq 160.
  3. (5 点) N \leqq 10.
  4. (18 点) N \leqq 20.
  5. (15 点) N \leqq 45.L は奇数であり,Y_k = \frac{L+1}{2} (1 \leqq k \leqq N).
  6. (31 点) N \leqq 45.
  7. (19 点) 追加の制約はない.

入力例 1

6 4 8
1 3
2 2
3 4
5 5

出力例 1

Yes

1 番目と 2 番目の患者をマス (1, 1) にある病院へ,3 番目の患者をマス (1, 6) にある病院へ,4 番目の患者をマス (6, 6) にある病院へそれぞれ搬送することで,時刻 8 までにすべての患者をいずれかの病院に搬送することができるので,Yes を出力する.

例えば,マス (1, 1) にある病院に設置された救急車が次の順に動くと,この救急車は時刻 8 までに 1 番目と 2 番目の患者を病院へ搬送することができる.

時刻 救急車の状態
0 マス (1, 1) を出発する
1 マス (2, 1) に到着する
2 マス (2, 2) に到着し,2 番目の患者を乗せ,出発する
3 マス (1, 2) に到着する
4 マス (1, 1) に到着し,2 番目の患者を降ろし,出発する
5 マス (1, 2) に到着する
6 マス (1, 3) に到着し,1 番目の患者を乗せ,出発する
7 マス (1, 2) に到着する
8 マス (1, 1) に到着し,1 番目の患者を降ろす

この入力例は小課題 1,2,3,4,6,7 の制約を満たす.


入力例 2

9 5 19
5 5
5 5
7 5
2 5
9 5

出力例 2

No

時刻 19 までにすべての患者をいずれかの病院に搬送することはできないので,No を出力する.

この入力例はすべての小課題の制約を満たす.


入力例 3

7 7 16
6 1
2 4
4 5
5 5
3 4
6 4
5 1

出力例 3

Yes

この入力例は小課題 1,2,3,4,6,7 の制約を満たす.


入力例 4

200 15 800
126 45
196 40
43 58
96 13
28 33
44 55
60 22
58 156
135 183
44 29
92 182
157 138
30 132
175 87
166 57

出力例 4

No

この入力例は小課題 4,6,7 の制約を満たす.


Source Name

JOI 2024/2025 春季トレーニング Contest Day2