trang chủ / đề bài / icpc23_nat_f

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 n 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ả n 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ố k>1, và cứ mỗi k lượt liên tiếp, Lộc chỉ chọn một hình duy nhất. Cụ thể:

  • Ở các lượt 1,2,…,k, Lộc chọn cùng một hình.
  • Ở các lượt k+1,k+2,…,2·k, Lộc chọn cùng một hình.
  • ...
  • Ở (nmodk) 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ố k>1 sao cho tổng số lượt Lộc thắng là lớn nhất. Nếu có nhiều giá trị k thỏa mãn, hãy tìm giá trị k 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 t (1≤t≤10000), 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 s (2≤|s|≤200000, si∈{R, P, S}), các hình mà máy tính sẽ chọn trong n lượt:

  • Nếu si là R, máy tính chọn búa ở lượt i;
  • Nếu si là P, máy tính chọn bao ở lượt i;
  • Nếu si là S, máy tính chọn kéo ở lượt i.

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á 200000.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là giá trị k>1 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

  • 1≤t≤10000
  • 2≤|s|≤200000, s chỉ gồm các ký tự R, P, S
  • Tổng độ dài các xâu không vượt quá 200000.

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 5 lượt. Bộ thứ hai: với k=8, Lộc chọn PPPPPPPPR và thắng 7 lượt; với k=2 Lộc chọn PPRRSSPPR và cũng thắng 7 lượt, nhưng k=2 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à k=5, Lộc chọn PPPPPS và thắng cả 6 lượ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