NOI Singapore 2026 - Monkeys
Xem PDFMonkeyland là một trục số vô hạn có \(n\) con khỉ, đánh số từ \(1\) đến \(n\). Ban đầu con thứ \(i\) ở vị trí \(p_i\); nhiều con có thể cùng vị trí.
Chuyển động của các con khỉ được xác định bởi chuỗi \(d\) dài \(n\):
- nếu \(d_i=\)
L, con thứ \(i\) dịch sang trái một đơn vị; - nếu \(d_i=\)
R, con thứ \(i\) dịch sang phải một đơn vị.
Mỗi ngày Pan niệm phép đúng một lần. Hai con khỉ trở thành bạn nếu chúng từng ở cùng vị trí vào bất kỳ ngày nào, kể cả lúc ban đầu. Nếu Pan niệm phép trong \(k\) ngày, hãy đếm số cặp khỉ trở thành bạn.
Dữ liệu vào
- Dòng đầu chứa \(n,k\).
- Dòng thứ hai chứa \(p_1,p_2,\ldots,p_n\).
- Dòng thứ ba chứa chuỗi \(d\) gồm \(n\) ký tự.
Dữ liệu ra
In một số nguyên: số cặp khỉ trở thành bạn.
Giới hạn
Mỗi \(d_i\) là L hoặc R.
Chấm điểm
| Phần | Điểm | Giới hạn thêm |
|---|---|---|
| 1 | 6 | \(n=2\) |
| 2 | 13 | \(d_1=d_2=\cdots=d_n\) |
| 3 | 10 | \(n,k\le200\) |
| 4 | 22 | \(n,k\le3000\) |
| 5 | 18 | \(n\le3000\) |
| 6 | 31 | Không có giới hạn thêm |
Ví dụ
Ví dụ 1
Input
2 1
1 3
RLOutput
1Note
Sau ngày đầu, cả hai con đều ở vị trí \(2\) nên trở thành bạn.
Ví dụ 2
Input
5 67
1 2 3 4 5
RRRRROutput
0Note
Mọi con cùng đi sang phải và ban đầu ở các vị trí khác nhau, nên không cặp nào gặp nhau.
Ví dụ 3
Input
6 7
1 1 8 16 18 22
RRLRLLOutput
3Ví dụ 4
Input
10 30
9 46 27 8 12 100 56 96 6 7
LRLRRLRRLROutput
5Ví dụ 5
Input
4 2
3 4 4 6
LLRLOutput
2Note
Ban đầu khỉ \(2\) và \(3\) cùng ở vị trí \(4\). Sau ngày đầu, khỉ \(3\) và \(4\) cùng ở vị trí \(5\). Do đó có hai cặp bạn.
Hình 1: Trạng thái ban đầu của ví dụ 5, ở ngày \(0\).
Hình 2: Trạng thái của ví dụ 5 sau ngày \(1\).
Hình 3: Trạng thái của ví dụ 5 sau ngày \(2\).
Kỳ thi:
- NOI Singapore 2026 - Vòng chung kết (14 Tháng ba, 2026)
Bình luận