JOI 2017 Final Camp - Ngày 1 - Bộ đề bài - LQDOJ: Le Quy Don Online Judge

#	Bài tập	Điểm	Thời gian:	Giới hạn bộ nhớ
1	JOI 2017 - Cultivation	100 (p)	2.0s	256M
2	JOI 2017 - Port Facility	100 (p)	5.0s	1G
3	JOI 2017 - Sparklers	100 (p)	2.0s	256M

1. JOI 2017 - Cultivation

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Trong năm 21XX, cư dân hành tinh IOI dự định di cư đến một hành tinh mới được phát hiện. Trên hành tinh mới có một cánh đồng hình chữ nhật gồm \(R\) hàng và \(C\) cột. Các cột chạy theo hướng nam-bắc, còn các hàng chạy theo hướng đông-tây. Ô ở hàng thứ \(i\) tính từ phía bắc và cột thứ \(j\) tính từ phía tây được gọi là ô \((i,j)\). Góc tây bắc là ô \((1,1)\) và góc đông nam là ô \((R,C)\).

Mỗi năm, cư dân hành tinh IOI chọn một hướng gió thổi qua cánh đồng: đông, tây, nam hoặc bắc.

Để canh tác trên hành tinh mới, họ sẽ trồng "cỏ JOI" trên toàn bộ cánh đồng. Vào mùa xuân năm đầu tiên sau khi di cư, cỏ JOI đã mọc ở \(N\) ô.

Phạm vi của cỏ JOI được mở rộng nhờ gió. Mỗi mùa hè, hạt của cỏ JOI bị gió thổi theo hướng đã chọn, di chuyển đúng một ô rồi rơi xuống. Nếu hạt rơi vào một ô thuộc cánh đồng chưa có cỏ JOI, ô đó sẽ có cỏ JOI vào mùa xuân năm sau. Một khi đã có cỏ JOI, ô đó sẽ luôn có cỏ JOI trong những năm tiếp theo.

Hãy chọn hướng gió thích hợp qua từng năm để toàn bộ cánh đồng có cỏ JOI sớm nhất có thể.

Yêu cầu

Tính số năm nhỏ nhất cần thiết để tất cả các ô trên cánh đồng đều có cỏ JOI.

Dữ liệu vào

Dòng đầu gồm hai số nguyên \(R,C\), lần lượt là số hàng và số cột của cánh đồng.
Dòng thứ hai chứa số nguyên \(N\), là số ô đã có cỏ JOI vào mùa xuân năm đầu tiên.
Trong \(N\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(S_i,E_i\), cho biết ô \((S_i,E_i)\) đã có cỏ JOI vào mùa xuân năm đầu tiên.

Dữ liệu ra

In ra một số nguyên duy nhất: số năm nhỏ nhất cần thiết để toàn bộ cánh đồng có cỏ JOI.

Ràng buộc

\(1 \le N \le 300\).
\(1 \le R,C \le 1\,000\,000\,000\).
\(1 \le S_i \le R\) với mọi \(1 \le i \le N\).
\(1 \le E_i \le C\) với mọi \(1 \le i \le N\).
Vào mùa xuân năm đầu tiên, vẫn có ít nhất một ô trên cánh đồng chưa có cỏ JOI.
\((S_i,E_i) \ne (S_j,E_j)\) với mọi \(1 \le i<j \le N\).

Phân nhóm

Subtask 1 (5 điểm): \(R \le 4\), \(C \le 4\).
Subtask 2 (10 điểm): \(R \le 40\), \(C \le 40\).
Subtask 3 (15 điểm): \(R \le 40\).
Subtask 4 (30 điểm): \(N \le 25\).
Subtask 5 (20 điểm): \(N \le 100\).
Subtask 6 (20 điểm): Không có ràng buộc bổ sung.

Giới hạn

Thời gian: 2 giây.
Bộ nhớ: 256 MB.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Ban đầu, ba ô \((1,2)\), \((1,4)\) và \((2,3)\) có cỏ JOI. Nếu hướng gió trong ba năm đầu lần lượt là tây, nam, nam thì sau ba năm mọi ô đều có cỏ. Số năm mà từng ô bắt đầu có cỏ là:

1 0 1 0
2 1 0 2
3 2 2 3

Không thể phủ kín cánh đồng trong ít hơn ba năm.

Ví dụ 2

Input

Output

2. JOI 2017 - Port Facility

Điểm: 100 (p) Thời gian: 5.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Mỗi ngày có nhiều container được tàu thủy đưa đến cảng JOI, rồi được xe tải vận chuyển đi khắp cả nước.

Cảng JOI rất hẹp và chỉ có hai khu vực để đặt container. Tại mỗi khu vực, có thể xếp chồng một số lượng bất kỳ container theo phương thẳng đứng.

Vì lý do an toàn, khi một container đến bằng tàu thủy, nó phải được đặt vào một trong hai khu vực; nếu khu vực đó đã có container thì container mới phải được đặt lên trên cùng. Khi một container rời cảng bằng xe tải, nó phải được lấy từ trên cùng của một trong hai chồng.

Hôm nay có \(N\) container đến cảng JOI và sau đó tất cả đều sẽ rời cảng bằng xe tải. Với mỗi container, bạn biết thời điểm nó đến và thời điểm nó rời cảng.

Yêu cầu

Tính số cách đặt và lấy các container hợp lệ, lấy phần dư theo \(1\,000\,000\,007\).

Hai cách được xem là khác nhau nếu có ít nhất một container được đặt vào hai khu vực khác nhau trong hai cách đó.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), là số container.
Trong \(N\) dòng tiếp theo, dòng thứ \(i\) gồm hai số nguyên \(A_i,B_i\): container thứ \(i\) đến cảng tại thời điểm \(A_i\) và rời cảng tại thời điểm \(B_i\).

Dữ liệu ra

In ra số cách đặt và lấy container hợp lệ, lấy phần dư theo \(1\,000\,000\,007\).

Ràng buộc

\(1 \le N \le 1\,000\,000\).
\(1 \le A_i,B_i \le 2N\) với mọi \(1 \le i \le N\).
\(A_i<B_i\) với mọi \(1 \le i \le N\).
\(2N\) số \(A_1,\ldots,A_N,B_1,\ldots,B_N\) đôi một khác nhau.

Phân nhóm

Subtask 1 (10 điểm): \(N \le 20\).
Subtask 2 (12 điểm): \(N \le 2\,000\).
Subtask 3 (56 điểm): \(N \le 100\,000\).
Subtask 4 (22 điểm): Không có ràng buộc bổ sung.

Giới hạn

Thời gian: 3.5 giây.
Bộ nhớ: 1024 MB.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Gọi hai khu vực là A và B. Bốn cách hợp lệ ứng với việc lần lượt đặt các container \(1,2,3,4\) vào:

A, B, A, A;
A, B, A, B;
B, A, B, A;
B, A, B, B.

Ví dụ 2

Input

Output

Ví dụ 3

Input

Output

Ví dụ 4

Input

Output

3. JOI 2017 - Sparklers

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

JOI-kun và các bạn sẽ chơi pháo que. Có tổng cộng \(N\) người. Sau khi được châm, một que pháo cháy đúng \(T\) giây.

Ban đầu, mọi người đứng dọc theo một con đường thẳng chạy theo hướng đông-tây. Họ được đánh số từ \(1\) đến \(N\). Với mọi \(i<j\), người thứ \(i\) đứng về phía tây của người thứ \(j\), hoặc hai người đứng cùng một vị trí. Khoảng cách từ người thứ \(i\) đến người ở xa nhất về phía tây, tức người thứ nhất, là \(X_i\) mét. JOI-kun là người thứ \(K\).

Chiếc bật lửa chỉ còn đủ nhiên liệu để châm một que pháo, nên trước tiên họ châm que pháo của JOI-kun. Sau đó, các que khác chỉ có thể được châm bằng cách chạm vào một que đang cháy. Mỗi lần truyền lửa phải thỏa mãn:

Việc chạm phải diễn ra không quá \(T\) giây kể từ khi que đang cháy được châm; thời điểm đúng \(T\) giây vẫn được phép.
Que sắp được châm chưa từng cháy trước đó.
Hai người liên quan phải ở cùng một vị trí.

Thời gian cần để truyền lửa được xem là bằng \(0\).

Mọi người có thể chạy về phía đông hoặc phía tây với tốc độ tùy ý, nhưng để bảo đảm an toàn, tốc độ của mỗi người không được vượt quá \(s\) mét mỗi giây, trong đó \(s\) là một số nguyên không âm.

Yêu cầu

Tính số nguyên nhỏ nhất \(s\) sao cho có thể châm được tất cả các que pháo.

Dữ liệu vào

Dòng đầu gồm ba số nguyên \(N,K,T\): số người, chỉ số của JOI-kun và thời gian một que pháo duy trì ngọn lửa.
Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa số nguyên \(X_i\), là khoảng cách ban đầu từ người thứ \(i\) đến người thứ nhất.

Dữ liệu ra

In ra số nguyên nhỏ nhất \(s\) sao cho có thể châm tất cả các que pháo nếu giới hạn tốc độ là \(s\) mét mỗi giây.

Ràng buộc

\(1 \le K \le N \le 100\,000\).
\(1 \le T \le 1\,000\,000\,000\).
\(0 \le X_i \le 1\,000\,000\,000\) với mọi \(1 \le i \le N\).
\(X_1=0\).
\(X_i \le X_j\) với mọi \(1 \le i \le j \le N\).

Phân nhóm

Subtask 1 (30 điểm): \(N \le 20\).
Subtask 2 (20 điểm): \(N \le 1\,000\).
Subtask 3 (50 điểm): Không có ràng buộc bổ sung.

Giới hạn

Thời gian: 2 giây.
Bộ nhớ: 256 MB.

Ví dụ

Ví dụ 1

Input

Output

Giải thích

Với giới hạn \(2\) m/s, người thứ nhất chạy về đông, còn người thứ hai và thứ ba chạy về tây. Sau \(50\) giây, người thứ hai truyền lửa cho người thứ nhất. Tiếp đó, người thứ nhất chạy về đông và người thứ ba chạy về tây, đều với tốc độ \(2\) m/s. Sau \(25\) giây, người thứ nhất truyền lửa cho người thứ ba. Giới hạn \(1\) m/s là không đủ.

Ví dụ 2

Input

Output

Giải thích

Với giới hạn \(8\) m/s, ban đầu người thứ nhất và thứ hai chạy về đông, người thứ ba chạy về tây. Sau \(3\) giây, người thứ hai dừng lại; hai người còn lại tiếp tục chạy. Sau thêm \(6.5\) giây, người thứ hai và thứ ba gặp nhau nhưng chưa truyền lửa; cả hai dừng lại, còn người thứ nhất tiếp tục chạy. Sau thêm \(0.5\) giây, người thứ hai truyền lửa cho người thứ ba. Người thứ nhất tiếp tục chạy, còn người thứ ba chạy về tây với tốc độ \(8\) m/s. Sau thêm \(9\) giây, người thứ nhất và thứ ba gặp nhau, và người thứ ba truyền lửa cho người thứ nhất. Giới hạn \(7\) m/s là không đủ.

Ví dụ 3

Input

Output