IOI 2003 - Ngày 2

\(N\) con bò của nông dân John trông rất giống nhau và được đánh số từ \(1\) đến \(N\), với \(1\le N\le50\). Khi đưa một con bò vào chuồng ngủ, John phải xác định đó là con nào để đưa vào đúng ô chuồng.

Mỗi con bò có \(P\) thuộc tính, đánh số từ \(1\) đến \(P\), với \(1\le P\le8\). Mỗi thuộc tính có ba giá trị có thể có, được ký hiệu bằng các chữ X, Y, Z. Chẳng hạn, màu thẻ tai có thể là vàng, xanh lá hoặc đỏ. Hai con bò bất kỳ luôn khác nhau ở ít nhất một thuộc tính.

Đây là bài tương tác. Biết các thuộc tính của cả đàn, hãy giúp John xác định con bò đang được đưa đi ngủ. Chương trình được hỏi không quá 100 câu dạng: “Giá trị thuộc tính \(T\) của con bò có thuộc tập \(S\) không?”. Hãy dùng ít câu hỏi nhất có thể.

Dữ liệu vào

Trong đề gốc, danh sách đàn bò được đọc từ guess.in, còn phần hỏi đáp dùng đầu vào và đầu ra chuẩn. Trong bản luyện tập này, cả danh sách đàn bò lẫn câu trả lời đều được nhận từ đầu vào chuẩn. Đầu tiên, đọc danh sách đàn bò:

• Dòng đầu chứa hai số nguyên \(N,P\) cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo mô tả các con bò theo thứ tự từ 1 đến \(N\). Mỗi dòng chứa \(P\) chữ cái cách nhau bởi dấu cách, lần lượt là giá trị thuộc tính 1, 2, ..., \(P\).

Sau đó, các câu trả lời cho truy vấn cũng được nhận từ đầu vào chuẩn.

Tương tác

Để hỏi, ghi ra đầu ra chuẩn một dòng dạng Q T v1 v2 ..., gồm chữ Q, số thuộc tính \(T\) và một hoặc nhiều giá trị cách nhau bởi dấu cách. Phải có \(1\le T\le P\); mỗi giá trị là X, Y hoặc Z và không được lặp lại trong cùng một câu hỏi. Ví dụ, Q 1 Z Y hỏi thuộc tính 1 có bằng Z hoặc Y không.

Sau mỗi câu hỏi, đẩy hết dữ liệu trong bộ đệm đầu ra và đọc một dòng chứa một số nguyên. Số 1 nghĩa là giá trị thuộc tập đã hỏi; số 0 nghĩa là không thuộc.

Khi xác định được con bò, ghi dòng cuối dạng C i, với \(1\le i\le N\) là số thứ tự con bò, đẩy hết bộ đệm đầu ra rồi kết thúc chương trình. Đáp án chỉ đúng khi con bò được chỉ ra là con duy nhất còn phù hợp với mọi câu trả lời đã nhận.

Ràng buộc

Giới hạn thời gian: 1 giây CPU. Giới hạn bộ nhớ: 64 MiB.

Phân nhóm

Có 20 bộ dữ liệu, mỗi bộ tối đa 5 điểm.

• Tính đúng đắn, 30%: chỉ được phần điểm này khi chỉ ra đúng con bò duy nhất phù hợp với tất cả câu trả lời. Nếu hỏi quá 100 câu, bộ dữ liệu được 0 điểm.
• Số câu hỏi, 70%: phần còn lại phụ thuộc số câu hỏi đã dùng để xác định đúng con bò. Dữ liệu chấm được thiết kế để khuyến khích giảm số câu hỏi trong trường hợp xấu nhất; số câu hỏi gần tối ưu vẫn có điểm thành phần.

Gọi \(q\) là số câu hỏi đã dùng và \(q^*\) là số câu hỏi tối ưu trong trường hợp xấu nhất. Với đáp án đúng và \(q\le100\), tỷ lệ điểm theo bộ chấm gốc là:

Ví dụ

4 2
X Z
X Y
Y X
Y Y
0
1

Q 1 X Z
Q 2 Y
C 4

Nguồn

Đề gốc IOI 2003. Bảng tổng quan ngày 2.

Bạn tự hào sở hữu hai rô-bốt nằm trong hai mê cung hình chữ nhật riêng biệt, mỗi mê cung không lớn hơn \(20\times20\). Ô \((1,1)\) là ô trên cùng bên trái, tức góc tây bắc. Trong mê cung thứ \(i\) có \(G_i\) lính gác, với \(0\le G_i\le10\), đi qua lại trên các đường tuần tra thẳng để bắt rô-bốt.

Đầu mỗi phút, bạn gửi cùng một lệnh cho cả hai rô-bốt. Lệnh là một hướng: bắc, nam, đông hoặc tây. Mỗi rô-bốt đi một ô theo hướng đó; nếu gặp tường thì nó đứng yên trong phút ấy. Rô-bốt thoát khỏi mê cung bằng cách đi ra ngoài biên. Khi đã thoát, nó bỏ qua mọi lệnh tiếp theo.

Lính gác cũng đi một ô vào đầu mỗi phút, đồng thời với rô-bốt. Mỗi lính gác bắt đầu tại một ô và quay mặt về một hướng cho trước. Nếu đường tuần tra có \(L\) ô, lính đi \(L-1\) bước theo hướng ban đầu, quay đầu ngay lập tức và đi ngược về ô xuất phát; tại đó lại quay đầu và tiếp tục lặp lại. Đường tuần tra không đi qua tường và không ra ngoài mê cung.

Các đường tuần tra có thể giao nhau nhưng hai lính gác không bao giờ va chạm: chúng không cùng ở một ô cuối phút và không đổi chỗ cho nhau trong một phút. Ban đầu không có lính gác nào ở cùng ô với rô-bốt.

Một lính gác bắt được rô-bốt nếu chúng ở cùng một ô vào cuối phút, hoặc đổi chỗ cho nhau trong một phút.

Hãy tìm một dãy lệnh đưa cả hai rô-bốt thoát khỏi mê cung mà không bị bắt. Cần tối thiểu hóa thời điểm rô-bốt thoát sau cùng. Nếu hai rô-bốt thoát ở hai thời điểm khác nhau, thời điểm thoát của rô-bốt sớm hơn không ảnh hưởng đến mục tiêu.

Dữ liệu vào

Trong bản luyện tập, đọc dữ liệu từ đầu vào chuẩn; tệp đầu vào trong đề gốc có tên robots.in. Dữ liệu mô tả mê cung thứ nhất rồi đến mê cung thứ hai, cùng một định dạng nhưng các giá trị có thể khác nhau:

• Dòng đầu chứa hai số nguyên \(R_i,C_i\) là số hàng và số cột, mỗi số từ 1 đến 20.
• \(R_i\) dòng tiếp theo, mỗi dòng có \(C_i\) ký tự: X là ô xuất phát của rô-bốt, . là ô trống, # là tường. Mỗi mê cung có đúng một rô-bốt.
• Dòng tiếp theo chứa \(G_i\), số lính gác.
• Mỗi trong \(G_i\) dòng tiếp theo chứa ba số nguyên và một ký tự, cách nhau bởi dấu cách. Hai số đầu là hàng và cột xuất phát của lính gác. Số thứ ba là số ô trên đường tuần tra, từ 2 đến 4. Ký tự cuối là hướng ban đầu: N, S, E, W, lần lượt là bắc, nam, đông, tây.

Dữ liệu ra

Ghi kết quả ra đầu ra chuẩn. Tệp đầu ra trong đề gốc có tên robots.out.

Nếu không có dãy lệnh hợp lệ, ghi một dòng duy nhất chứa -1.

Nếu có, dòng đầu ghi số lệnh \(K\), với \(K\le10000\). \(K\) dòng tiếp theo, mỗi dòng chứa một ký tự N, S, E hoặc W. Dãy lệnh phải đưa cả hai rô-bốt ra ngoài mà không bị bắt; lệnh cuối phải làm ít nhất một rô-bốt thoát khỏi mê cung. Nếu có lời giải thì lời giải ngắn nhất không quá 10000 lệnh. Nếu có nhiều dãy ngắn nhất, có thể ghi bất kỳ dãy nào.

Ràng buộc

Giới hạn thời gian: 2 giây CPU. Giới hạn bộ nhớ: 64 MiB.

Phân nhóm

Có 20 bộ dữ liệu, mỗi bộ tối đa 5 điểm. Với bộ dữ liệu không có lời giải, chỉ có điểm nếu trả lời đúng -1.

Với bộ dữ liệu có lời giải:

• Tính đúng đắn, 20%: kết quả đúng định dạng, không quá 10000 lệnh, cả hai rô-bốt thoát an toàn và lệnh cuối làm ít nhất một rô-bốt thoát.
• Tính ngắn nhất, 80%: ngoài các điều kiện đúng đắn trên, không tồn tại dãy hợp lệ ngắn hơn. Dãy không ngắn nhất không được phần điểm này.

Ví dụ

5 4
####
#X.#
#..#
...#
##.#
1
4 3 2 W
4 4
####
#...
#X.#
####
0

8
E
N
E
S
S
S
E
S

Nguồn

Đề gốc IOI 2003. Bảng tổng quan ngày 2.

Nông dân Don quan sát hàng rào bao quanh cánh đồng phẳng hình vuông cạnh \(N\) mét, với \(2\le N\le500000\). Một góc của hàng rào ở \((0,0)\), góc đối diện ở \((N,N)\); các cạnh song song với hai trục tọa độ.

Có một cọc rào ở mỗi góc và tại mỗi vị trí cách nhau một mét trên mỗi cạnh, tổng cộng \(4N\) cọc. Các cọc thẳng đứng và được coi là không có bán kính. Don muốn biết mình nhìn thấy được bao nhiêu cọc từ vị trí đang đứng trong hàng rào.

Trong cánh đồng có \(R\) tảng đá lớn, với \(1\le R\le30000\), che khuất một số cọc rào vì Don không đủ cao để nhìn qua chúng. Đáy mỗi tảng đá là một đa giác lồi có diện tích khác không, các đỉnh có tọa độ nguyên. Các tảng đá có mặt bên thẳng đứng; chúng không chồng lên nhau, không chạm nhau, không chạm Don và không chạm hàng rào. Don không đứng trong hay trên tảng đá, cũng không chạm hàng rào.

Hãy tính số cọc rào Don nhìn thấy. Nếu từ vị trí của Don, một đỉnh của tảng đá nằm thẳng hàng và che đúng một cọc rào thì cọc đó không nhìn thấy được.

Dữ liệu vào

Trong bản luyện tập, đọc dữ liệu từ đầu vào chuẩn. Tệp đầu vào trong đề gốc có tên boundary.in.

• Dòng đầu chứa hai số nguyên \(N,R\) cách nhau bởi dấu cách.
• Dòng tiếp theo chứa hai số nguyên là tọa độ \(X,Y\) của Don.
• Tiếp theo là mô tả của \(R\) tảng đá. Mỗi mô tả bắt đầu bằng một dòng chứa số nguyên \(p_i\), với \(3\le p_i\le20\), là số đỉnh của đáy tảng đá.
• \(p_i\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X,Y\) là tọa độ một đỉnh. Các đỉnh đôi một khác nhau và được cho theo chiều ngược kim đồng hồ. Các đỉnh liên tiếp có thể thẳng hàng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên trên một dòng: số cọc rào Don nhìn thấy. Tệp đầu ra trong đề gốc có tên boundary.out.

Ràng buộc

Giới hạn thời gian: 1 giây CPU. Giới hạn bộ nhớ: 64 MiB.

Phân nhóm

Có 25 bộ dữ liệu, mỗi bộ tối đa 4 điểm. Mỗi bộ chỉ được điểm khi kết quả đúng; không có điểm thành phần trong một bộ dữ liệu.

Ví dụ

100 1
60 50
5
70 40
75 40
80 40
80 50
70 60

319

Nguồn

Đề gốc IOI 2003. Bảng tổng quan ngày 2.