trang chủ / đề bài / icpcwf09_g

Nhà bằng bài

Đề bài

Mô tả

Axel và Birgit thích chơi một trò chơi bài, trong đó họ xây một ngôi nhà bằng các lá bài và được (hoặc mất) điểm khi thêm bài vào ngôi nhà. Vì cả hai đều có đôi tay rất vững nên ngôi nhà bài không bao giờ đổ. Họ dùng nửa bộ bài tiêu chuẩn. Một bộ bài tiêu chuẩn có bốn chất, hai chất đỏ và hai chất đen. Axel và Birgit chỉ dùng hai chất, một đỏ và một đen. Mỗi chất có 13 bậc. Ta dùng ký hiệu 1R, 2R, ..., 13R, 1B, 2B, ..., 13B để chỉ bậc và màu (R là đỏ, B là đen).

Đầu tiên hai người chọn một tập con các lá bài, thường là mọi lá có bậc không quá một giá trị lớn nhất M. Sau khi xáo bộ bài đã chọn, họ lấy tám lá trên cùng và đặt liên tiếp từ trái sang phải để tạo thành bốn "đỉnh". Ví dụ, nếu M=13 và mười lá đầu tiên (trong 26 lá) là:

6B 3R 5B 2B 1B 5R 13R 7B 11R 1R ...

thì trò chơi bắt đầu với bốn đỉnh và ba thung lũng như Hình 1.

Hình 1: Các đỉnh và thung lũng tạo bởi 8 lá trên cùng của bộ bài.

Các lá còn lại được đặt ngửa thành một hàng duy nhất.

Mỗi người chơi ứng với một màu, đỏ hoặc đen. Birgit luôn là màu đen và Axel luôn là màu đỏ. Màu của lá đầu tiên dùng để dựng các đỉnh và thung lũng quyết định ai đi trước. Trong ví dụ ở Hình 1, Birgit đi trước vì lá đầu tiên là 6B.

Hai người chơi lần lượt thay phiên nhau. Mỗi lượt gồm việc lấy lá bài ở đầu hàng rồi làm một trong các việc sau:

  1. Giữ lá bài đó đến lượt sau (đây là "lá đang giữ").
  2. Phủ thung lũng giữa hai đỉnh bằng lá vừa lấy hoặc lá đang giữ, tạo thành một "sàn". Lá còn lại (nếu có) được giữ.
  3. Đặt hai lá lên trên một sàn, tạo thành một đỉnh (một trong hai lá phải là lá đang giữ).

Không phải lúc nào cũng làm được mọi việc. Mỗi người chỉ được giữ nhiều nhất một lá tại mọi thời điểm, nên việc 1 chỉ làm được khi người chơi chưa giữ lá nào.

Vì các lá trong hàng đều ngửa, cả hai người chơi đều biết trước thứ tự các lá sẽ được lấy.

Nếu người chơi tạo ra một tam giác chúc xuống khi thêm một sàn, hoặc một tam giác hướng lên khi thêm một đỉnh, thì điểm được cập nhật như sau: tổng bậc của ba lá trong tam giác được cộng vào điểm của người chơi có màu trùng với màu chiếm đa số trong ba lá đó. Nếu lượt chơi không tạo ra tam giác nào, điểm của cả hai không đổi.

Trong ví dụ ở Hình 1, nếu Birgit đặt lá của mình (11R) lên thung lũng giữa, cô được 14 điểm. Nếu cô đặt lên thung lũng bên trái, Axel được 19 điểm. Nếu cô đặt lên thung lũng bên phải, Axel được 29 điểm.

Nếu không còn lá nào để lấy khi kết thúc một lượt, trò chơi kết thúc. Nếu lúc đó người chơi nào đang giữ một lá, bậc của lá đó được cộng vào (trừ khỏi) điểm của người đó nếu màu của lá trùng với (khác với) màu của người đó.

Khi trò chơi kết thúc, người có điểm thấp hơn trả cho người kia số Krona Thụy Điển bằng hiệu điểm của hai người. Nếu hòa thì không ai trả.

Hãy viết chương trình nhận mô tả của một bộ bài đã xáo và tên một người chơi, rồi tìm số tiền lớn nhất mà người đó có thể thắng (hoặc số tiền thua nhỏ nhất của người đó), giả sử người kia luôn đi những nước tốt nhất.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test, mỗi bộ test là một ván chơi. Mỗi bộ test gồm một tên (Axel hoặc Birgit) trên một dòng, tiếp theo là bậc lớn nhất M trên một dòng, rồi đến bậc và màu của 2M lá bài theo thứ tự đã xáo trên một dòng. Mỗi tổ hợp bậc (từ 1 đến M) và màu xuất hiện đúng một lần trong danh sách này. Tám lá đầu tiên tạo thành hàng đỉnh ban đầu từ trái sang phải theo thứ tự được lấy, các lá còn lại cho biết thứ tự của phần còn lại của bộ bài.

Sau bộ test cuối cùng là một dòng chứa từ End.

Dữ liệu ra

Với mỗi bộ test, in ra số thứ tự của bộ test (bắt đầu từ 1), tên người chơi của bộ test đó và số tiền người đó thắng hoặc thua. Nếu hòa, in thông báo hòa thay cho số tiền. Làm theo đúng định dạng trong ví dụ.

Ràng buộc

  • 5≤M≤13.
  • Mỗi file có không quá 10 bộ test.

Ví dụ

Input Output Giải thích
Axel
5
1R 2R 3R 4R 5R 5B 4B 3B 2B 1B
Birgit
5
1R 2R 3R 4R 5R 5B 4B 3B 2B 1B
Birgit
5
1R 1B 3R 4R 5R 5B 4B 3B 2R 2B
End
Case 1: Axel wins 1
Case 2: Birgit loses 1
Case 3: Axel and Birgit tie
Ván 1: Axel đi trước (lá đầu là 1R), đặt 2B lên thung lũng 4R 5R (Axel được 11), Birgit đặt 1B lên thung lũng 5B 4B (Birgit được 10). Ván 2 giống ván 1 nhưng tính cho Birgit. Ván 3: Axel đặt 2R lên thung lũng 4R 5R (11), Birgit đặt 2B lên thung lũng 5B 4B (11).
Birgit
5
3B 3R 4B 2R 5R 1R 1B 5B 4R 2B
Axel
6
5R 6B 1B 2R 1R 4B 5B 3B 3R 4R 6R 2B
End
Case 1: Birgit loses 9
Case 2: Axel loses 9
Ván 1: Birgit đi trước; đặt 4R vào thung lũng nào cũng cho Axel điểm, giữ 4R thì cuối ván bị trừ 4. Tốt nhất là đặt 4R lên thung lũng giữa (Axel được 11), sau đó Axel giữ 2B (bị trừ 2). Ván 2: Axel giữ 3R, Birgit đặt 4R lên thung lũng trái (6B 1B 4R, Birgit được 11), Axel dựng đỉnh 3R 6R trên sàn đó (Axel được 13), Birgit đặt 2B lên thung lũng phải (Birgit được 11).

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