IOI 2008 - Linear Garden

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 2000 (p) Thời gian: 1.5s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Ramesses II vừa trở về sau một trận chiến thắng lợi. Để kỷ niệm chiến thắng, ông quyết định xây dựng một khu vườn tráng lệ. Khu vườn sẽ gồm một hàng cây dài, kéo từ cung điện của ông ở Luxor đến đền Karnak. Hàng cây chỉ gồm cây sen và cây cói giấy, vì hai loài cây này lần lượt tượng trưng cho Thượng Ai Cập và Hạ Ai Cập.

Khu vườn phải có đúng \(N\) cây. Ngoài ra, khu vườn phải cân bằng: trong bất kỳ đoạn liên tiếp nào của hàng cây, số cây sen và số cây cói giấy không được chênh lệch quá \(2\).

Có thể biểu diễn một khu vườn bằng một xâu gồm các chữ cái L (cây sen) và P (cây cói giấy). Chẳng hạn, với \(N=5\), có \(14\) khu vườn cân bằng. Theo thứ tự từ điển, đó là: LLPLP, LLPPL, LPLLP, LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP và PPLPL.

Ta sắp xếp tất cả các khu vườn cân bằng có cùng độ dài theo thứ tự từ điển, với L đứng trước P, rồi đánh số bắt đầu từ \(1\). Ví dụ, với \(N=5\), khu vườn số \(12\) là PLPPL.

Cho số cây \(N\) và một xâu biểu diễn một khu vườn cân bằng, hãy viết chương trình tính số thứ tự được gán cho khu vườn đó, lấy modulo số nguyên \(M\) cho trước. Giá trị \(M\) chỉ nhằm đơn giản hóa việc tính toán, không có ý nghĩa nào khác đối với việc giải bài toán.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

  • Dòng thứ nhất chứa số nguyên \(N\), là số cây trong khu vườn.
  • Dòng thứ hai chứa số nguyên \(M\).
  • Dòng thứ ba chứa một xâu gồm \(N\) ký tự L (cây sen) hoặc P (cây cói giấy), biểu diễn một khu vườn cân bằng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên từ \(0\) đến \(M-1\), kể cả hai đầu: số thứ tự của khu vườn được mô tả trong dữ liệu vào, lấy modulo \(M\).

Ràng buộc

  • \(1 \le N \le 1\,000\,000\).
  • \(7 \le M \le 10\,000\,000\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Nhãn nhóm Điểm Tệp dữ liệu vào gốc
1 3 lin/lin1.in
2 3 lin/lin2.in
3 3 lin/lin3.in
4 3 lin/lin4.in
5 4 lin/lin5.in
6 4 lin/lin6.in
7 4 lin/lin7.in
8 4 lin/lin8.in
9 4 lin/lin9.in
10 4 lin/lin10.in
11 4 lin/lin11.in
12 5 lin/lin12a.in, lin/lin12b.in
13 5 lin/lin13a.in, lin/lin13b.in
14 5 lin/lin14a.in, lin/lin14b.in, lin/lin14c.in
15 5 lin/lin15.in
16 5 lin/lin16.in
17 5 lin/lin17.in
18 5 lin/lin18.in
19 5 lin/lin19.in
20 5 lin/lin20.in
21 5 lin/lin21.in
22 5 lin/lin22.in
23 5 lin/lin23a.in, lin/lin23b.in, lin/lin23c.in

Các ví dụ trong đề không tính điểm. Các tệp ví dụ gốc có nhãn 0 được giữ lại riêng và có trọng số 0.

Tệp ví dụ gốc: lin/lin0a.in, lin/lin0b.in.

Ví dụ

Ví dụ 1

Input 
5
7
PLPPL
Output 
5
Note

Số thứ tự thực sự được gán cho PLPPL là \(12\). Vì vậy, kết quả là \(12 \bmod 7 = 5\).

Ví dụ 2

Input 
12
10000
LPLLPLPPLPLL
Output 
39

Nguồn

IOI 2008, ngày thi thứ hai: Linear Garden, bản tiếng Anh 1.1. Tác giả đề bài: Aleksandar Ilić (Serbia). Tập đề bài và lời giải IOI 2008.

Tệp

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: