1380BUnreviewed1400

Universal Solution

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

greedy
Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

Think about what happens at a single position ii of your string across all nn possible cyclic shifts of the opponent's string. What characters does position ii end up facing?

As the shift kk ranges from 00 to n−1n-1, position ii of your string faces s[(i+k) mod n]s[(i+k) \bmod n] — which cycles through every character of ss exactly once. So every position faces the exact same multiset of opponent moves.

Since each position faces the same distribution of opponent moves (each character of ss appears exactly once across all shifts), the optimal choice at every position is the same: pick the move that beats the most characters in ss.

Count the occurrences of R, P, and S in the input. Playing R beats all the S's, playing P beats all the R's, and playing S beats all the P's. Pick whichever gives max⁡(countR,countP,countS)\max(\text{count}_R, \text{count}_P, \text{count}_S) wins.

The answer string is just the same character repeated nn times (the one that beats the most frequent character), and the expected wins equal max⁡(countR,countP,countS)\max(\text{count}_R, \text{count}_P, \text{count}_S), which is always an integer — so the fraction is always m/1m/1.

Key Insight

Consider what a single position ii in your chosen string tt faces across all nn equally-likely cyclic shifts. When the shift is kk, position ii faces s[(i+k) mod n]s[(i+k) \bmod n]. As kk ranges over 0,1,…,n−10, 1, \ldots, n-1, the index (i+k) mod n(i+k) \bmod n takes every value in {0,…,n−1}\{0, \ldots, n-1\} exactly once. So every position in your string faces the entire multiset of the opponent's characters, each exactly once.

Consequence

Since each position faces the same distribution, the optimal move at every position is the same: pick the RPS character that beats the largest group. Specifically:

  • If ss has rr R's, pp P's, and cc S's, then:
    • Playing P at a position beats all rr rocks across shifts
    • Playing S at a position beats all pp papers across shifts
    • Playing R at a position beats all cc scissors across shifts

The best choice beats m=max⁡(r,p,c)m = \max(r, p, c) opponents per position.

Expected Value

The expected number of wins is:

E=1n∑i=0n−1m=n⋅mn=mE = \frac{1}{n} \sum_{i=0}^{n-1} m = \frac{n \cdot m}{n} = m

This is always an integer, so the output fraction is simply m/1m/1. The optimal string is just the winning character repeated nn times.

Complexity

O(n)O(n) per test case to count characters — about as chill as it gets.

Trap Alert

The problem asks for a fraction p/qp/q in lowest terms. Since mm is always a non-negative integer, the answer is always m/1m/1. Don't overthink the fraction part.

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

using ll = long long;

void setIO(const string& name = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

#ifdef ZK_LOCAL_RUN
    freopen("f.in", "r", stdin);
    freopen("f.out", "w", stdout);
#else
    if (!name.empty()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
#endif
}

int main() {
    setIO();
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size();
        int r = 0, p = 0, sc = 0;
        for (char c : s) {
            if (c == 'R') r++;
            else if (c == 'P') p++;
            else sc++;
        }
        // P beats R, S beats P, R beats S
        int mx = max({r, p, sc});
        char best;
        if (mx == r) best = 'P';
        else if (mx == p) best = 'S';
        else best = 'R';

        cout << string(n, best) << "\n";
        cout << mx << "/1\n";
    }
    return 0;
}
View on CodeforcesBack to the list