trang chủ / đề bài / icpcwf22_x

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 4 người, dùng một bộ 32 lá bài chia thành 8 bộ, mỗi bộ 4 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 8 lá và người chơi 1 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 1 đ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 (1, 2, 3, 4, 1, ...) 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 n (1≤n≤1000), 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 n 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 x hỏi người chơi y lá sk, và người chơi y đưa lá đó cho người chơi x;
  • x A y sk no: người chơi x hỏi người chơi y lá sk, người chơi y 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 x đặt bộ tứ s sang một bên.

Trong mọi hành động, x và y (1≤x,y≤4, x≠y) là các số nguyên chỉ người chơi, s (1≤s≤8) là một số nguyên một chữ số ứng với một trong các bộ, còn k∈{A,B,C,D} là ký tự xác định một trong bốn lá của bộ. Như vậy các lá sk đượ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 4 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ừ 1, hành động đặt bộ tứ sang một bên cũng được đếm.

Ràng buộc

  • 1≤n≤1000.
  • 1≤x,y≤4, x≠y, 1≤s≤8, k∈{A,B,C,D}.
  • 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 1 và 2 đề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ộ 3).
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 1 có 3C, 5A, 5C, 5D, người chơi 2 có 3B, người chơi 3 có 3A, người chơi 4 có 3D và 5B; khi đó mọi hành động đều đúng luật.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0