Kỳ thi Học sinh giỏi Quốc gia 2018 - Ngày 1

VOI 18 Bài 1 - Robot

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 7

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Đọc đề gốc tại đây.

Chủ đề của cuộc thi ROBCON năm nay là "Tìm đường thoát mê cung". Tuấn vừa chế tạo được một robot để tham dự cuộc thi này. Tuấn rất thành thạo trong kỹ thuật chế tạo máy nhưng trong lập trình lại không được tốt như vậy. Do đó, Tuấn mới chỉ lập được một chương trình còn khá đơn giản để điều khiển robot của mình.

Robot di chuyển về phía trước với tốc độ 1 mét/giây cho đến khi gặp vật cản. Khi gặp vật cản robot sẽ liên tiếp thực hiện quay trái 90 độ cho đến khi trước mặt nó không có vật cản và lại tiếp tục di chuyển về phía trước. Thời gian để robot thực hiện đổi hướng chuyển động là cực nhanh, vì thế được coi là bằng 0. Robot không bao giờ tự dừng chuyển động.

Để thử nghiệm robot, Tuấn đã xây dựng một mê cung trên một mặt sàn thi đấu rất rộng lớn. Mặt sàn có dạng một lưới ô vuông kích thước ~1 \times 1~ mét. Các cột của lưới được đánh số bởi các số nguyên từ ~-10^{10}~ đến ~10^{10}~, từ trái qua phải. Các dòng của lưới được đánh số bởi các số nguyên từ ~-10^{10}~ đến ~10^{10}~, từ trên xuống dưới. Ô nằm trên giao của cột ~x~ và dòng ~y~ được gán với toạ độ ~(x, y)~. Mê cung mà Tuấn xây dựng là một lưới con kích thước ~N \times N~ với ô ở góc trái trên có toạ độ ~(1, 1)~. Trong một số ô của mê cung có đặt vật cản, các ô còn lại là ô rỗng (ô không có vật cản).

Tuấn đặt robot của mình vào ô có toạ độ ~(x, y)~, mặt robot quay về phía trên của lưới và cho robot chuyển động. Biết rằng vị trí mà Tuấn đặt robot không có vật cản và có ít nhất một ô chung cạnh với ô đặt robot là ô rỗng. Tuấn muốn xác định vị trí của robot sau ~S~ giây.

Yêu cầu: Hãy giúp Tuấn giải quyết vấn đề đặt ra.

Input

Dòng đầu tiên chứa bốn số nguyên ~N~, ~x~, ~y~, ~S~ được ghi cách nhau bởi dấu cách, ~1 \le N \le 1\,000, -10^5 \le x, y \le 10^5~;
~N~ dòng tiếp theo mô tả mê cung, mỗi dòng gồm ~N~ ký hiệu được ghi liên tiếp nhau, mỗi ký hiệu được lấy từ tập {#, .}, trong đó ký hiệu # cho biết ô tương ứng trong mê cung có vật cản, còn ký hiệu . cho biết ô tương ứng trong mê cung là ô rỗng.

Output

Ghi ra hai số nguyên cách nhau bởi một dấu cách là toạ độ của ô mà robot đạt đến sau ~S~ giây.

Chú ý: Ô xuất phát và ô mà robot đạt đến sau ~S~ giây không nhất thiết phải nằm trong mê cung.

Giới hạn

Có ~50\%~ số lượng test ứng với ~50\%~ số điểm của bài thoả mãn điều kiện: ~1 \le S \le 10^5~.
~50\%~ số lượng test còn lại ứng với ~50\%~ số điểm của bài thoả mãn điều kiện: ~1 \le S \le 10^9~.

Sample Input 1

4 3 5 9
###.
#...
#..#
##.#

Sample Output 1

2 3

Sample Input 2

3 2 5 7
###
#..
#..

Sample Output 2

2 6

Note

Giải thích: Hình 1a) dưới đây minh hoạ cho ví dụ thứ nhất. Lưới con gồm các ô được tô nền xanh là mê cung. Đường di chuyển của robot xuất phát từ ô ~(3, 5)~ (ô có chữ R) qua các ô của sàn thi đấu được chỉ ra bởi các mũi tên. Trong ví dụ này ô xuất phát không thuộc mê cung. Sau ~9~ giây, robot đạt đến ô ~(2, 3)~.

Tương tự, hình 1b) minh hoạ đường di chuyển của robot trong ví dụ thứ hai: Robot xuất phát từ ô ~(2, 5)~, đạt đến ô ~(2, 6)~ sau ~7~ giây.

VOI 18 Bài 2 - Dòng xe vào bến

Nộp bài

Giới hạn thời gian: 1.0s / Giới hạn bộ nhớ: 256M

Điểm: 7

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Đọc đề gốc tại đây.

Bến xe khách liên tỉnh XYZ có ~M~ điểm đỗ đón xe khách cập bến để hành khách xuống xe. Các điểm đỗ được đánh số từ ~1~ đến ~M~. Ban điều hành bến xe nhận được yêu cầu cập bến của một dòng xe gồm ~N~ xe khách chờ được phục vụ cập bến, lần lượt xe này sau xe kia. Các xe khách được đánh số từ ~1~ đến ~N~ theo thứ tự chờ được phục vụ. Xe khách thứ ~i~ chỉ chấp nhận cập bến, nếu như nó được xếp phục vụ tại một trong số các điểm đỗ có chỉ số trong khoảng từ ~a_i~ đến ~b_i~ ~(1 \le a_i \le b_i \le M)~ và đồng thời tại điểm đỗ được bố trí để phục vụ nó chưa có xe nào trong số các xe (trong dòng xe đang xét) đến trước đã cập bến tại đó. Nếu có một xe khách đến lượt được phục vụ mà Ban điều hành không tìm được điểm đỗ theo đúng yêu cầu để phục vụ nó, thì xe này và tất cả các xe đến sau nó sẽ đồng loạt di chuyển sang bến xe khác và việc phục vụ dòng xe chấm dứt tại đây.

Yêu cầu: Hãy giúp Ban điều hành bến xe xác định số lượng lớn nhất các xe khách trong dòng xe mà bến xe khách XYZ có thể phục vụ đáp ứng các điều kiện đã nêu.

Input

Dòng đầu tiên chứa số nguyên dương ~T~ ~(T \le 5)~ là số lượng test. Tiếp đến là ~T~ nhóm dòng, mỗi nhóm là thông tin về một test theo khuôn dạng sau đây:

Dòng đầu tiên chứa hai số nguyên ~M~ và ~N~ tương ứng là số lượng điểm đỗ trong bến xe và số lượng xe trong dòng xe yêu cầu được phục vụ;
Dòng thứ ~i~ trong số ~N~ dòng tiếp theo mô tả yêu cầu của xe khách thứ ~i~ gồm hai số nguyên ~a_i~ và ~b_i~ ~(1 \le a_i \le b_i \le M)~ mô tả khoảng chỉ số của các điểm đỗ trong bến xe mà xe khách thứ ~i~ chấp nhận được phục vụ tại đó. Hai số trên cùng dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra ~T~ dòng, mỗi dòng ghi số lượng xe khách lớn nhất trong dòng xe mà bến xe khách XYZ có thể phục vụ là câu trả lời cho test tương ứng trong dữ liệu vào.

Giới hạn

Có ~25\%~ số test ứng với ~25\%~ số điểm của bài có: ~1 \le N, M \le 10~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có: ~1 \le N, M \le 300~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có: ~1 \le N, M \le 50\,000; \; a_i = 1, \; i = 1, 2, \ldots, N~;
~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài có: ~1 \le N, M \le 50\,000~.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Note

Giải thích: Trong ví dụ thứ nhất, xe khách thứ nhất yêu cầu được cập bến ở một trong các điểm đỗ ~1, 2, 3, 4~, ta có thể xếp nó vào điểm đỗ số ~4~. Cả hai xe khách ~2~ và ~3~ đều yêu cầu được cập bến ở điểm đỗ số ~1~, do đó, không thể phục vụ được xe khách số ~3~ (đến sau).

Trong ví dụ thứ hai, hai xe khách đầu tiên có thể xếp với điểm đỗ số ~1~ và ~2~ (xe ~1~ vào điểm đỗ số ~1~ và xe ~2~ vào điểm đỗ số ~2~, hoặc xe ~1~ vào điểm đỗ số ~2~ và xe ~2~ vào điểm đỗ số ~1)~. Xe khách thứ ba phải xếp cập bến tại điểm đỗ số ~3~. Đến lượt xe khách thứ tư, ta không tìm được điểm đỗ nào đáp ứng yêu cầu của nó, vì thế bến xe XYZ chấm dứt phục vụ dòng xe tại đây, mặc dù nếu bỏ qua xe khách thứ tư, ta có thể xếp điểm đỗ cho xe khách số ~5~ (nhưng xe này và cả xe khách số ~6~ đã theo xe khách số ~4~ đi tìm bến xe khác).

VOI 18 Bài 3 - Trò chơi khối hộp

Nộp bài

Giới hạn thời gian: 3.0s / Giới hạn bộ nhớ: 256M

Điểm: 6

Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài

Đọc đề gốc tại đây.

Trò chơi khối hộp là một trò chơi với một khối hộp chữ nhật kích thước ~a \times b \times c~ đơn vị trên lưới hình chữ nhật ~H~ được chia thành ~m \times n~ ô vuông đơn vị. Các hàng của lưới được đánh số từ ~1~ tới ~m~ từ trên xuống dưới và các cột của lưới được đánh số từ ~1~ tới ~n~ từ trái qua phải. Ô nằm trên giao của hàng ~i~ và cột ~j~ được gọi là ô ~(i, j)~. Ban đầu, khối hộp được đặt ở góc trái trên của lưới ~H~, cụ thể mặt đáy khối hộp chiếm đúng ~a \times b~ ô của lưới, là các ô nằm trong hình chữ nhật con của lưới ~H~ với ô ở góc trái trên là ~(1, 1)~ và ô ở góc phải dưới là ~(a, b)~. Mỗi bước, người chơi có thể thực hiện một trong các loại thao tác sau:

Đẩy khối hộp tịnh tiến lên trên, xuống dưới, sang trái hoặc sang phải một ô;
Lật khối hộp lên trên, xuống dưới, sang trái hoặc sang phải một ô.

Ví dụ, các hình vẽ trong Hình ~2~ dưới đây mô tả vị trí của khối hộp kích thước ~1 \times 2 \times 1~ sau khi thực hiện từng loại thao tác.

Khi bắt đầu chơi, tất cả các ô mà khối hộp đè lên được bật sáng màu xanh và có ~k~ ô khác trên lưới được bật sáng màu đỏ, các ô còn lại ở trạng thái tắt. Một thao tác được gọi là hợp lệ, nếu sau khi thực hiện thao tác này, khối hộp vẫn nằm gọn trên lưới ~H~ và không đè lên ô sáng màu đỏ nào. Sau khi một thao tác được thực hiện, những ô bị khối hộp đè lên đang ở trạng thái tắt sẽ được bật sáng màu xanh, những ô đang sáng xanh vẫn giữ nguyên trạng thái bật sáng màu xanh. Nhiệm vụ của người chơi là tìm cách thực hiện dãy các thao tác hợp lệ để bật được nhiều ô sáng màu xanh nhất.

Yêu cầu: Cho kích thước khối hộp, kích thước của lưới ~H~ và vị trí của các ô sáng màu đỏ, hãy xác định số lượng nhiều nhất các ô được bật sáng màu xanh mà người chơi có thể đạt được.

Input

Dòng thứ nhất chứa sáu số nguyên dương ~a~, ~b~, ~c~, ~m~, ~n~, ~k~, các số được ghi cách nhau bởi dấu cách;
Dòng thứ ~s~ trong số ~k~ dòng tiếp theo chứa hai số nguyên dương được ghi cách nhau bởi dấu cách ~x_s, y_s~ là tọa độ của một ô đã bật sáng màu đỏ ~(s = 1, 2, \dots, k)~.

Output

Ghi ra một số nguyên duy nhất là số lượng nhiều nhất các ô được bật sáng màu xanh mà người chơi có thể đạt được.

Giới hạn

Có ~25\%~ số test ứng với ~25\%~ số điểm của bài có ~a = b = c = 1~; ~m, n \le 100~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~a = b = c~; ~m, n \le 100~;
Có ~25\%~ số test khác ứng với ~25\%~ số điểm của bài có ~m, n \le 100~;
~25\%~ số test còn lại ứng với ~25\%~ số điểm của bài có ~m, n \le 1\,000~.

Sample Input

1 2 1 3 3 2
2 2
3 3

Sample Output

Note

Giải thích:

Hình vẽ dưới mô tả trạng thái bắt đầu trò chơi, trong đó hai ô tô đen là các ô sáng màu đỏ. Người chơi có thể thực hiện dãy thao tác: Lật sang phải, đẩy xuống dưới, đẩy lên trên, đẩy sang trái, đẩy sang trái, đẩy xuống dưới, đẩy xuống dưới, cuối cùng đẩy sang phải để bật được ~7~ ô của lưới sáng màu xanh.