\(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.