Overview

This problem asks us to find, as an irreducible fraction, the probability that the member selected by lottery has a different rank from Takahashi (Member \(1\)).

Analysis

One person is selected uniformly at random from the \(N-1\) people excluding Takahashi. A valid pair is formed when the selected person’s rank is different from Takahashi’s.

For example, consider the case where \(N = 5\) and the ranks are A A B B A.

• Takahashi’s rank is A
• The ranks of members \(2 \sim 5\) are A B B A
• Among these, the members with a different rank (i.e., B) number \(2\)

Therefore, the probability of forming a valid pair is \(\frac{2}{4} = \frac{1}{2}\).

In general, if \(D\) denotes the number of people among members \(2, 3, \ldots, N\) whose rank differs from Takahashi’s, the desired probability is:

\[\frac{D}{N-1}\]

To reduce this to an irreducible fraction, we simply divide the numerator and denominator by their greatest common divisor (\(\gcd\)).

This problem can be solved by simply scanning through all members once, so no special techniques are needed. Although \(N\) can be up to \(10^6\), an \(O(N)\) scan is more than sufficient.

Algorithm

1. Record Takahashi’s rank \(S_1\).
2. Scan from member \(2\) to member \(N\), counting the number \(D\) of members whose rank differs from \(S_1\).
3. Set numerator \(P = D\) and denominator \(Q = N - 1\).
4. Compute \(g = \gcd(P, Q)\), and divide both \(P\) and \(Q\) by \(g\) to obtain the irreducible fraction.
5. Output in the format P/Q.

Note: When \(D = 0\) (all members have the same rank), \(\gcd(0, Q) = Q\), so \(0 / Q = 0 / 1\) is correctly output. Similarly, when \(D = N-1\) (all other members have a different rank), \(\frac{N-1}{N-1} = \frac{1}{1}\).

Complexity

• Time complexity: \(O(N)\) (just a single scan through all members)
• Space complexity: \(O(N)\) (needed to store the input; if we only count ranks, \(O(1)\) is also possible)

Implementation Notes

• Using math.gcd makes computing the greatest common divisor easy. Python’s math.gcd works correctly even when one of the arguments is \(0\) (\(\gcd(0, k) = k\)).

• Note that the output format for the irreducible fraction is P/Q. Using an f-string, this can be concisely written as f"{P}/{Q}".

• Since member indices are managed in \(0\)-indexed fashion, S[0] corresponds to Takahashi’s rank, and S[1] through S[N-1] correspond to the ranks of members \(2\) through \(N\).

  Source Code

import math

N = int(input())
S = input().split()

takahashi_rank = S[0]

# Count members 2..N with different rank
different = sum(1 for i in range(1, N) if S[i] != takahashi_rank)

P = different
Q = N - 1

g = math.gcd(P, Q)
P //= g
Q //= g

print(f"{P}/{Q}")

---

This editorial was generated by claude4.6opus-thinking.