trang chủ / đề bài / icpcwf17_k

Lời tiên tri Tarot

Đề bài

Mô tả

Đáng ghét thật! Năm nào ở giải đấu Oẳn tù tì (Rock Paper Scissors) thường niên, bạn cũng lọt vào trận chung kết. (Kỹ thuật Búa của bạn là vô đối, còn Bao của bạn sắc như dao! Riêng Kéo thì vẫn cần luyện thêm một chút.) Nhưng năm nào đối thủ của bạn cũng đánh bại bạn, dù các nước đi của hắn trông hoàn toàn ngẫu nhiên! Hắn còn tuyên bố với báo chí rằng hắn đơn giản là không thể bị đánh bại. Bí mật của hắn là gì?

May thay, bạn nghĩ mình đã tìm ra. Năm nay, ngay trước giải đấu, bạn bắt gặp hắn đi thăm nhiều thầy pháp trong thị trấn. A ha! Hắn đang dùng sức mạnh siêu nhiên để chống lại bạn! Bạn nghĩ rằng trò này thì hai người cùng chơi được. Vậy là bạn đi gặp một nhóm thầy bói, mỗi người dùng một bộ bài Tarot để tiên đoán một dãy nước đi mà đối thủ của bạn sẽ dùng vào một lúc nào đó trong trận đấu.

Tuy nhiên, sự phấn khích ban đầu đã qua, và giờ bạn thấy mình hơi ngớ ngẩn. Chuyện này không thể nào có tác dụng, đúng không? Rốt cuộc bạn có cảm giác mình đã trả nhiều tiền cho một bộ tiên đoán ngẫu nhiên, lừa đảo. Thôi thì đành vậy, bạn vẫn có thể để ý xem vài tiên đoán trong số đó có xuất hiện trong trận đấu hay không. Nhưng bạn sẽ dùng những tiên đoán nào?

Trong trận chung kết, bạn và đối thủ sẽ chơi n ván Oẳn tù tì. Ở mỗi ván, cả hai người đều chọn một trong ba lựa chọn (Búa, Bao hoặc Kéo). Dựa trên lựa chọn của hai người, người thắng ván đó được xác định (cụ thể như thế nào không liên quan đến bài toán này).

Cho độ dài trận chung kết và các tiên đoán, hãy sắp xếp các tiên đoán theo khả năng chúng xuất hiện vào một lúc nào đó trong trận đấu, dưới dạng một dãy liên tiếp các lựa chọn của đối thủ, giả sử ở mỗi ván đối thủ chọn nước đi một cách độc lập và ngẫu nhiên đều trong ba lựa chọn.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n (1≤n≤106) là số ván của trận chung kết, và s (1≤s≤10) là số dãy tiên đoán.

Mỗi dòng trong s dòng tiếp theo mô tả một tiên đoán, là một xâu gồm các ký tự R, P và S. Mọi tiên đoán có cùng độ dài, độ dài này nằm trong khoảng từ 1 đến n ký tự (tính cả hai đầu) và không quá 105.

Dữ liệu ra

In ra tất cả các tiên đoán, mỗi tiên đoán trên một dòng, theo thứ tự xác suất xuất hiện vào một lúc nào đó trong trận chung kết giảm dần. Với các tiên đoán có xác suất bằng nhau, in chúng theo đúng thứ tự trong dữ liệu vào.

Ràng buộc

  • 1≤n≤106, 1≤s≤10.
  • Mọi tiên đoán có cùng độ dài ℓ với 1≤ℓ≤min(n,105), chỉ gồm các ký tự R, P, S.

Ví dụ

Input Output Giải thích
3 4
PP
RR
PS
SS
PS
PP
RR
SS
Trong 27 dãy dài 3 có 6 dãy chứa PS và 5 dãy chứa mỗi xâu PP, RR, SS. Ba xâu cuối có xác suất bằng nhau nên giữ thứ tự trong dữ liệu vào.
20 3
PRSPS
SSSSS
PPSPP
PRSPS
PPSPP
SSSSS
Ba xâu có xác suất xuất hiện khác nhau, PRSPS dễ xuất hiện nhất, SSSSS khó xuất hiện nhấ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