Hướng dẫn giải

Mỗi cái bắt tay là một cặp RL đứng cạnh nhau đổi chỗ thành LR. Các cặp RL trong cùng một lượt không chồng nhau, nên mọi lượt là các phép đổi chỗ song song. Trò chơi dừng khi xâu có dạng L...LR...R.

Sub 1: Mô phỏng — ~O(n \cdot T)~, dùng khi xâu dài ~\le 3000~

Lặp từng lượt: duyệt xâu, gặp RL thì đổi thành LR và nhảy qua cặp đó. Nếu lượt không có cái bắt tay nào thì dừng; ngược lại tăng thời gian thêm 1 và cộng số cặp vào tổng. Số lượt có thể lên tới cỡ ~n~ nên với ~n = 10^5~ sẽ quá chậm. Nếu chỉ nộp sub này: đúng 10/20 test.

Sub 2: Công thức theo từng chữ L — ~O(n)~

Số cái bắt tay bằng số cặp (R đứng trước, L đứng sau), vì mỗi cặp đổi chỗ đúng một lần. Với mỗi chữ L có ~k~ chữ R đứng trước, nó cần ít nhất ~k~ giây, và không thể di chuyển cùng lúc sớm hơn chữ L ngay trước nó một giây. Do đó gọi ~t~ là thời điểm chữ L đó xong: ~t = \max(t_{\text{trước}} + 1, k)~ (chỉ áp dụng cho chữ L có ~k > 0~). Đáp số thời gian là ~t~ của chữ L cuối cùng, tổng số bắt tay là tổng các ~k~ (dùng long long, có thể tới khoảng ~2{,}5 \cdot 10^9~). Chương trình đúng 20/20 test.

Chương trình hoàn chỉnh

main đọc xâu; xâu ngắn thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

#include <bits/stdc++.h>
using namespace std;

string s;

// Sub 1: mô phỏng từng lượt — ~O(n * số lượt)~, dùng khi xâu ngắn
void sub1() {
    int n = s.size();
    long long time = 0, cnt = 0;
    while (true) {
        int c = 0;
        // các cặp "RL" không chồng nhau nên đổi chỗ tại chỗ được
        for (int i = 0; i + 1 < n; i++)
            if (s[i] == 'R' && s[i + 1] == 'L') {
                s[i] = 'L'; s[i + 1] = 'R';
                c++; i++;
            }
        if (c == 0) break;
        time++; cnt += c;
    }
    cout << time << " " << cnt;
}

// Sub 2: mỗi cái bắt tay là một cặp (R trước L) bị đổi chỗ => số bắt tay = số cặp R...L.
// Với mỗi L (từ trái sang phải) có k chữ R đứng trước, nó cần xong sau
// t = max(t_trước + 1, k) giây (không thể đi cùng lúc với L ngay trước nó).
void sub2() {
    long long r = 0, t = 0, cnt = 0;
    for (char ch : s) {
        if (ch == 'R') r++;
        else if (r > 0) {
            cnt += r;
            t = max(t + 1, r);
        }
    }
    cout << t << " " << cnt;
}

int main() {
    freopen("HANDS.INP", "r", stdin);
    freopen("HANDS.OUT", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> s;
    if (s.size() <= 3000) sub1();
    else sub2();
}