Bộ tứ
Đề bài
Mô tả
Bạn đang xem một nhóm trẻ em chơi một ván bài Bộ tứ (Quartets) rất vui vẻ. Đến một lúc, bạn bắt đầu nghi ngờ rằng một vài đứa trẻ có thể đang gian lận. Có vẻ bọn trẻ chẳng hề bận tâm về chuyện đó. Ngược lại, điều này còn khiến chúng vui hơn, nhất là khi có ai đó bị bắt quả tang gian lận. Là một lập trình viên, bạn lập tức nghĩ cách phát hiện gian lận chỉ bằng việc quan sát ván bài.
Bộ tứ là trò chơi bài cho người, dùng một bộ lá bài chia thành bộ, mỗi bộ lá. Lá bài thật thường in hình ảnh mang tính giáo dục, giúp người chơi học không chỉ từng sự vật mà cả cách phân loại chúng. Ví dụ, các lá bài có thể in hình động vật, còn các bộ tương ứng với các nhóm động vật (thú, bò sát, v.v.).
Đầu ván, mỗi người chơi được chia lá và người chơi bắt đầu lượt của mình. Trong mỗi lượt, một người chơi hỏi một người chơi khác xem người đó có một lá bài cụ thể nào đó không. Nếu người bị hỏi có lá đó, họ phải đưa nó cho người hỏi, và người hỏi tiếp tục lượt của mình bằng cách hỏi bất kỳ người chơi nào về một lá khác. Nếu người bị hỏi không có lá được hỏi, người hỏi mất lượt và người bị hỏi bắt đầu lượt của mình. Một luật quan trọng: người hỏi phải đang có sẵn ít nhất một lá thuộc cùng bộ với lá mà họ hỏi.
Nếu trong lượt của mình, một người chơi có trong tay đủ một bộ (một "bộ tứ"), người đó có thể trình bộ tứ cho những người khác xem, đặt nó sang một bên và được điểm. Bốn lá của bộ tứ bị loại vĩnh viễn khỏi ván đang chơi. Nếu tại bất kỳ thời điểm nào một người chơi không còn lá nào, người đó rời khỏi ván. Nếu khi đó đang là lượt của người này, lượt được chuyển cho người chơi kế tiếp theo vòng (, , , , , ...) còn có bài. Nếu không ai còn bài, ván kết thúc và người có nhiều điểm nhất thắng.
Người chơi không được hỏi những lá đã bị loại khỏi ván, và không được hỏi bài người đã rời khỏi ván.
Gian lận trong trò Bộ tứ có thể xảy ra trong hai tình huống, khi một người chơi nói sai về việc mình có (hoặc không có) một lá bài nào đó. Cụ thể, gian lận xảy ra nếu:
- một người chơi hỏi một lá bài trong khi họ không có lá nào thuộc bộ tương ứng, hoặc
- một người bị hỏi nói rằng mình không có lá được hỏi trong khi thực ra họ có.
Đương nhiên, gian lận thường bị phát hiện về sau. Về lý thuyết, một đối thủ tinh ý cuối cùng có thể phát hiện mọi gian lận, vì tất cả các lá bài rốt cuộc đều được lộ ra vào lúc nào đó trước khi ván kết thúc. Lưu ý rằng việc hỏi một lá mà người bị hỏi không thể nào có (ví dụ vì chính người hỏi đang cầm lá đó) không phải nước đi khôn ngoan, nhưng bản thân nó không bị coi là gian lận.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số hành động liên tiếp trong một ván Bộ tứ, tính từ đầu ván. Mỗi dòng trong dòng tiếp theo mô tả một hành động, có một trong các dạng sau:
x A y sk yes: người chơi hỏi người chơi lá , và người chơi đưa lá đó cho người chơi ;x A y sk no: người chơi hỏi người chơi lá , người chơi nói mình không có lá đó và bắt đầu lượt của mình;x Q s: người chơi đặt bộ tứ sang một bên.
Trong mọi hành động, và (, ) là các số nguyên chỉ người chơi, () là một số nguyên một chữ số ứng với một trong các bộ, còn là ký tự xác định một trong bốn lá của bộ. Như vậy các lá được ký hiệu 1A, 1B, 1C, 1D, 2A, 2B, ..., 8C, 8D. Bốn lá có cùng chữ số đầu tạo thành một bộ.
Dãy hành động đã cho mô tả một ván bài hợp lệ giữa người chơi. Nghĩa là, ngoại trừ hai cách gian lận nêu trên, mọi hành động đều tuân theo mọi luật chơi.
Dữ liệu ra
Nếu tồn tại một cách chia bài ban đầu sao cho dãy hành động tương ứng với một ván bài (có thể chưa kết thúc) trong đó mọi người chơi đều tuân theo luật, in ra yes. Ngược lại, in ra no, tiếp theo là một dòng chứa số thứ tự của hành động đầu tiên mà sau hành động đó chắc chắn đã có người gian lận. Các hành động được đánh số liên tiếp bắt đầu từ , hành động đặt bộ tứ sang một bên cũng được đếm.
Ràng buộc
- .
- , , , .
- Dãy hành động là một ván bài hợp lệ, ngoại trừ hai cách gian lận nêu trên.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 A 2 3C no 2 A 3 3A yes 2 A 4 3D yes 2 A 1 3C no |
no 4 |
Người chơi và đều nói không có lá 3C, và không ai trong hai người có 3A hay 3D lúc đầu. Vậy một trong hai người hoặc đã nói dối về việc không có 3C, hoặc đã hỏi 3C mà không có 3B (lá duy nhất còn lại của bộ ). |
| 6 1 A 2 3C no 2 A 3 3A yes 2 A 4 3D yes 2 A 1 3B no 1 A 4 5B yes 1 Q 5 |
yes | Chẳng hạn lúc đầu người chơi có 3C, 5A, 5C, 5D, người chơi có 3B, người chơi có 3A, người chơi có 3D và 5B; khi đó mọi hành động đều đúng luật. |
Bình luận