IOI 2002 - Ngày 1

Ở Hàn Quốc, sự nghịch ngợm của loài ếch nhỏ cheonggaeguri đã trở thành huyền thoại. Chúng quả thật xứng với tiếng tăm ấy: ban đêm, chúng nhảy qua ruộng lúa của bạn và làm đè bẹp các cây lúa. Sáng hôm sau, sau khi ghi lại những cây bị đè bẹp, bạn muốn xác định đường đi của con ếch gây thiệt hại nhiều nhất.

Mỗi con ếch luôn nhảy theo một đường thẳng, với khoảng cách giữa hai lần đáp liên tiếp không đổi. Các con ếch khác nhau có thể có độ dài bước nhảy và hướng nhảy khác nhau.

Các cây lúa nằm tại những giao điểm của một lưới hình chữ nhật gồm \(R\) hàng và \(C\) cột, như hình bên trái dưới đây. Mỗi con ếch nhảy xuyên qua ruộng, bắt đầu ở bên ngoài một phía và kết thúc ở bên ngoài phía bên kia, như hình bên phải.

Nhiều con ếch có thể nhảy qua ruộng. Mỗi lần đáp trong ruộng đều rơi vào một cây lúa và làm cây đó bị đè bẹp; nhiều con ếch có thể đáp xuống cùng một cây. Bạn chỉ quan sát được những cây bị đè bẹp, không nhìn thấy đường đi của các con ếch hay các lần đáp ở ngoài ruộng.

Chúng ta chỉ quan tâm đến đường đi của những con ếch đã đáp xuống ít nhất ba cây lúa trong ruộng; gọi đó là một đường đi hợp lệ. Mọi điểm đáp trong ruộng trên một đường đi như vậy đều phải là cây đã bị đè bẹp. Tuy nhiên, một cây bị đè bẹp nằm trên đường thẳng đó không nhất thiết phải là điểm đáp của con ếch đang xét. Cũng có thể có những cây bị đè bẹp không thuộc đường đi hợp lệ nào.

Hãy xác định số cây lúa lớn nhất có thể bị một con ếch đè bẹp trên một đường đi hợp lệ. Nếu không có đường đi nào thỏa mãn, kết quả là \(0\).

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(R,C\), với \(1\le R,C\le 5000\).
• Dòng thứ hai chứa số cây bị đè bẹp \(N\), với \(3\le N\le 5000\).
• Mỗi dòng trong \(N\) dòng tiếp theo chứa chỉ số hàng và cột của một cây bị đè bẹp. Các hàng được đánh số từ \(1\) đến \(R\), các cột từ \(1\) đến \(C\). Các vị trí này đôi một khác nhau.

Dữ liệu ra

In một số nguyên: số cây lớn nhất trên một đường đi hợp lệ, hoặc \(0\) nếu không có đường đi như vậy.

Chấm điểm

Có 25 bộ kiểm tra, mỗi bộ tương ứng 4 điểm trong thang điểm gốc 100. Một bộ kiểm tra chỉ được điểm khi kết quả đúng và chương trình chạy trong giới hạn thời gian; ngược lại được 0 điểm.

Ví dụ

6 7
14
2 1
6 6
4 2
2 5
2 6
2 7
3 4
6 1
6 2
2 3
6 3
6 4
6 5
6 7

7

6 7
18
1 1
6 2
3 5
1 5
4 7
1 2
1 4
1 6
1 7
2 1
2 3
2 6
4 2
4 4
4 5
5 4
5 5
6 6

4

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.

Vùng đất Utopia xinh đẹp từng bị chiến tranh tàn phá. Khi chiến sự lắng xuống, đất nước được chia thành bốn vùng bởi một đường kinh tuyến chạy theo hướng bắc–nam và một đường vĩ tuyến chạy theo hướng đông–tây. Giao điểm của chúng được gọi là điểm \((0,0)\). Cả bốn vùng đều nhận tên Utopia, nhưng dần dần được gọi là Utopia 1 ở phía đông bắc, Utopia 2 ở phía tây bắc, Utopia 3 ở phía tây nam và Utopia 4 ở phía đông nam.

Vị trí của một điểm được xác định bằng khoảng cách có dấu về phía đông và về phía bắc so với \((0,0)\): chiều dương của trục hoành hướng đông, chiều dương của trục tung hướng bắc. Các khoảng cách này có thể âm.

Các vùng được đánh số như sau: vùng 1 có \(x>0,y>0\); vùng 2 có \(x<0,y>0\); vùng 3 có \(x<0,y<0\); vùng 4 có \(x>0,y<0\). Các điểm trên hai trục tọa độ không thuộc vùng nào.

Một trở ngại lớn là người dân không được phép vượt qua biên giới giữa các vùng. May mắn thay, một số thí sinh IOI tài giỏi của Utopia đã phát minh ra một phương thức dịch chuyển tức thời an toàn. Máy dịch chuyển cần các mã số, mỗi mã chỉ được dùng một lần.

Thử thách dành cho nhóm thí sinh ấy và cho bạn là điều khiển máy từ vị trí ban đầu \((0,0)\) lần lượt đến \(N\) vùng theo một danh sách cho trước. Bạn có thể đáp xuống bất kỳ điểm nào bên trong vùng được yêu cầu. Hai hay nhiều vùng liên tiếp trong danh sách có thể giống nhau. Sau khi rời vị trí ban đầu, bạn không bao giờ được đáp xuống đường biên.

Bạn có \(2N\) mã số nguyên dương, đôi một khác nhau. Trong mỗi lần dịch chuyển, chọn hai mã chưa dùng, gắn cho mỗi mã một dấu + hoặc -, rồi dùng chúng làm độ dịch chuyển theo trục hoành và trục tung. Nếu vị trí hiện tại là \((x,y)\) và cặp số có dấu là \((u,v)\), vị trí mới sẽ là \((x+u,y+v)\). Chẳng hạn, cặp \((+u,-v)\) đưa bạn đến \((x+u,y-v)\). Bạn có thể sử dụng các mã theo bất kỳ thứ tự nào, nhưng mỗi mã phải được dùng đúng một lần trong toàn bộ hành trình.

Hãy tìm một hành trình thỏa mãn danh sách vùng đã cho.

Dữ liệu vào

• Dòng đầu chứa \(N\), với \(1\le N\le 10000\).
• Dòng thứ hai chứa \(2N\) mã số nguyên dương đôi một khác nhau, mỗi mã không vượt quá \(100000\).
• Dòng cuối chứa \(N\) số nguyên từ \(1\) đến \(4\), là các vùng cần đến theo thứ tự.

Dữ liệu ra

Nếu có lời giải, in \(N\) dòng theo thứ tự dịch chuyển. Mỗi dòng chứa hai mã đã gắn dấu, lần lượt cho trục hoành và trục tung. Phải in dấu + hoặc - trước mỗi mã, không có khoảng trắng giữa dấu và số; hai số có dấu được ngăn cách bằng một dấu cách. Có thể in bất kỳ lời giải hợp lệ nào.

Nếu không có lời giải, chỉ in số \(0\).

Chấm điểm

Có 25 bộ kiểm tra, mỗi bộ tương ứng 4 điểm trong thang điểm gốc 100. Một bộ kiểm tra chỉ được điểm khi hành trình đúng và chương trình chạy trong giới hạn thời gian; ngược lại được 0 điểm.

Ví dụ

4
7 5 6 1 3 2 4 8
4 1 2 1

+7 -1
-5 +2
-4 +3
+8 +6

4
2 5 4 1 7 8 6 3
4 2 2 1

+3 -2
-4 +5
-6 +1
+8 +7

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.

Bạn đang xây dựng một ứng dụng cho điện thoại di động có màn hình đen trắng. Ứng dụng cần nhiều hình ảnh với các kích thước khác nhau. Thay vì lưu trữ các ảnh, bạn muốn tạo ra chúng bằng thư viện đồ họa của điện thoại.

Mỗi ảnh có dạng hình vuông gồm \(N\times N\) điểm ảnh, mỗi điểm có màu trắng hoặc đen. Khi bắt đầu vẽ một ảnh, có thể giả sử mọi điểm ảnh trên màn hình đều màu trắng. Tọa độ \(x\) tăng từ trái sang phải, tọa độ \(y\) tăng từ trên xuống dưới; các cột và hàng được đánh số bắt đầu từ \(1\).

Thư viện chỉ cung cấp thao tác XOR(L,R,T,B), đảo màu tất cả điểm ảnh thuộc hình chữ nhật có góc trên trái \((L,T)\) và góc dưới phải \((R,B)\), kể cả các biên: trắng thành đen và đen thành trắng. Các tham số \(L,R,T,B\) lần lượt là tọa độ biên trái, phải, trên và dưới. Chú ý thứ tự tham số này có thể khác với các thư viện đồ họa khác.

Cho trước một ảnh đích, hãy tạo ra ảnh đó từ màn hình trắng bằng ít thao tác XOR nhất có thể. Bạn được cung cấp các tệp đầu vào và cần nộp các tệp kết quả, không cần nộp mã nguồn chương trình tìm lời giải.

Dữ liệu vào

Có 10 ảnh trong các tệp xor1.in đến xor10.in, được cung cấp trong tệp đính kèm xor-inputs.zip. Trong mỗi tệp:

• Dòng đầu chứa \(N\), với \(5\le N\le 2000\).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên, mô tả ảnh đích theo thứ tự hàng. Giá trị \(0\) biểu thị màu trắng, \(1\) biểu thị màu đen.

Dữ liệu ra

Trong kỳ thi gốc, mỗi tệp xorI.in có một tệp kết quả tương ứng. Trên bản luyện tập này, chọn ngôn ngữ OUTPUT và nộp một tệp ZIP chứa 10 tệp kết quả ngay tại thư mục gốc của ZIP, không đặt trong thư mục con, theo ánh xạ sau:

Nội dung mỗi tệp giữ nguyên định dạng của kỳ thi gốc:

• Dòng đầu có dạng #FILE xor I, trong đó I là số thứ tự của tệp đầu vào.
• Dòng thứ hai chứa số thao tác \(K\).
• \(K\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(L,R,T,B\) của một thao tác, theo đúng thứ tự thực hiện.

Mỗi thao tác phải thỏa mãn \(1\le L\le R\le N\) và \(1\le T\le B\le N\).

Chẳng hạn, 01.out phải bắt đầu bằng #FILE xor 1, còn 10.out bắt đầu bằng #FILE xor 10. Số trong dòng #FILE là số bộ dữ liệu gốc từ 1 đến 10, không thêm số 0 ở đầu như trong tên tệp ZIP.

Chấm điểm

Bản luyện tập này sử dụng các mốc cố định lấy từ kết quả tốt nhất của IOI 2002. Với ảnh từ 1 đến 10, số thao tác mốc \(B\) lần lượt là 3, 34, 28, 122, 74, 481, 566, 200, 500, 810. Mỗi bộ kiểm tra có trọng số 1. Một lời giải hợp lệ dùng \(K>0\) thao tác nhận tỉ lệ điểm \(\min(1,(1+9B/K)/10)\); lời giải tốt hơn mốc vẫn chỉ nhận tối đa toàn bộ điểm của bộ đó. Tổng điểm được chuẩn hóa về thang 100 từ các tỉ lệ này, không áp dụng bước làm tròn từng ảnh đến một chữ số thập phân hay làm tròn tổng đến số nguyên của kỳ thi gốc. Nếu ảnh toàn trắng được tạo bằng 0 thao tác thì nhận toàn bộ điểm.

Mỗi ảnh được 0 điểm nếu ảnh tạo ra không đúng, số thao tác thực tế khác \(K\), \(K>40000\), hoặc có thao tác chứa tọa độ không hợp lệ. Cụ thể, các trường hợp \(L>R\), \(T>B\), tọa độ không dương hay lớn hơn \(N\) đều không hợp lệ.

Trong cách chấm tương đối của kỳ thi gốc, một kết quả hợp lệ được \(1+9\times B/K\) điểm, trong đó \(B\) là số thao tác ít nhất trong các lời giải hợp lệ của tất cả thí sinh cho cùng ảnh. Khi đó, điểm mỗi ảnh được làm tròn đến một chữ số sau dấu phẩy; tổng điểm của 10 ảnh được làm tròn đến số nguyên gần nhất. Đây là quy tắc lịch sử, được thay bằng cách chấm mốc cố định nêu trên trong bản luyện tập này.

Ví dụ, nếu bạn dùng 121 thao tác và đó là kết quả tốt nhất của các thí sinh, bạn được 10 điểm. Nếu kết quả tốt nhất dùng 98 thao tác, bạn được \(1+9\times98/121\), làm tròn thành \(8{,}3\) điểm.

Ví dụ

7
0 0 0 0 0 0 0
0 1 1 1 0 0 0
1 0 0 1 0 0 0
1 0 1 0 1 1 0
1 0 1 0 1 1 0
0 1 0 0 1 1 0
0 0 1 1 1 1 0

#FILE xor 0
3
2 4 2 6
3 6 4 7
1 3 3 5

Nguồn

Đề gốc IOI 2002. Tài liệu kỳ thi.