Tìm chiến thuật oẳn tù tì
Đề bài
Mô tả
Oẳn tù tì là trò chơi ai cũng biết. Một ván chơi có ít nhất hai người. Mỗi người đồng thời chọn một trong ba hình: búa, bao hoặc kéo. Búa thắng kéo, kéo thắng bao, và bao thắng búa. Nếu hai người chọn cùng một hình thì hòa, không ai thắng cũng không ai thua.
Lộc vừa viết xong một trò chơi oẳn tù tì trên máy tính và giờ muốn thử nghiệm nó. Lộc và máy tính sẽ chơi lượt oẳn tù tì. Vì biết thuật toán mà máy tính sử dụng, Lộc có thể đoán trước hình mà máy tính sẽ chọn ở cả lượt. Tuy nhiên, sau cả ngày làm trò chơi, Lộc rất mệt. Lộc không muốn phải ra quá nhiều quyết định trong lúc thử nghiệm, nên sẽ chọn một số , và cứ mỗi lượt liên tiếp, Lộc chỉ chọn một hình duy nhất. Cụ thể:
- Ở các lượt , Lộc chọn cùng một hình.
- Ở các lượt , Lộc chọn cùng một hình.
- ...
- Ở lượt cuối cùng, Lộc chọn cùng một hình.
Cho danh sách tất cả các hình mà máy tính sẽ chọn, hãy giúp Lộc chọn số sao cho tổng số lượt Lộc thắng là lớn nhất. Nếu có nhiều giá trị thỏa mãn, hãy tìm giá trị lớn nhất có thể để Lộc không phải ra nhiều quyết định.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên (), số bộ dữ liệu. Mô tả các bộ dữ liệu như sau.
Mỗi bộ dữ liệu gồm một dòng duy nhất chứa xâu (, R, P, S), các hình mà máy tính sẽ chọn trong lượt:
- Nếu là R, máy tính chọn búa ở lượt ;
- Nếu là P, máy tính chọn bao ở lượt ;
- Nếu là S, máy tính chọn kéo ở lượt .
Dữ liệu bảo đảm tổng độ dài các xâu trong tất cả các bộ dữ liệu không vượt quá .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra một số nguyên là giá trị giúp Lộc thắng nhiều lượt nhất. Nếu có nhiều đáp án, in ra đáp án lớn nhất.
Ràng buộc
- , chỉ gồm các ký tự R, P, S
- Tổng độ dài các xâu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 RRRPPS RRSRRPRRS RPSRPSRPS |
3 8 4 |
Bộ thứ nhất: máy tính chọn RRRPPS, Lộc chọn PPPSSS và thắng lượt. Bộ thứ hai: với , Lộc chọn PPPPPPPPR và thắng lượt; với Lộc chọn PPRRSSPPR và cũng thắng lượt, nhưng không phải đáp án lớn nhất. |
| 4 RP SS RRRRRP PRSPRS |
2 2 5 5 |
Ví dụ bổ sung. Với RRRRRP và , Lộc chọn PPPPPS và thắng cả lượt. |
Bình luận