Overview

This problem asks us to find the probability that Takahashi is paired with a member of a different rank, expressed as an irreducible fraction.

Analysis

Let \(S_1\) be the rank of Takahashi (member \(1\)). A pair is formed only when a member with a different rank from Takahashi is selected.

In other words, we count the number of members among members \(2\) through \(N\) who have a rank different from \(S_1\), and divide that by the total number of candidates \(N - 1\) to get the desired probability.

For example, consider the case where \(N = 5\) and the ranks are A B A B A. Takahashi’s (member 1) rank is A. The ranks of members 2 through 5 are B, A, B, A, of which 2 are B. Therefore, the probability of forming a valid pair is \(\frac{2}{4} = \frac{1}{2}\).

In this way, simply counting the “number of people with a different rank” gives us the numerator of the probability. The denominator is always \(N - 1\).

Finally, this fraction needs to be reduced to an irreducible fraction. This can be achieved by dividing both the numerator and denominator by their greatest common divisor (GCD).

Note that in this problem \(N\) can be up to \(10^6\), so even a straightforward simulation will run in time, and the computational complexity is sufficiently fast.

Algorithm

1. Read \(N\) and the rank sequence \(S\) for each member from the input.
2. Get Takahashi’s rank \(S_1\).
3. Count the number of members among members \(2\) through \(N\) whose rank differs from \(S_1\).
4. This count becomes the numerator of the probability, and \(N - 1\) becomes the denominator.
5. Find the greatest common divisor of the numerator and denominator, and divide both by it to obtain the irreducible fraction.
6. Output the result in the format P/Q.

Complexity

• Time complexity: \(O(N + \log N)\) (GCD computation takes \(\log\))
• Space complexity: \(O(1)\) (constant memory excluding the input)

Implementation Notes

• The input is a space-separated string, so it can be easily converted to a list using input().split().

• To compute the greatest common divisor, math.gcd() is convenient.

• Even when the fraction equals 0 or 1, it will be output as 0/1 or 1/1 as specified by the problem statement, so no special handling is needed.

  Source Code

import math

def main():
    N = int(input())
    S = input().split()
    
    s1 = S[0]
    others = S[1:]
    
    count_diff = 0
    for s in others:
        if s != s1:
            count_diff += 1
    
    total = N - 1
    gcd = math.gcd(count_diff, total)
    p = count_diff // gcd
    q = total // gcd
    print(f"{p}/{q}")

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.