Overview

This problem asks you to find the probability that a member with a different rank from Takahashi is selected from the \(N-1\) members other than Takahashi, and output it as an irreducible fraction.

Analysis

The condition for a pair to be formed is that “the selected partner has a different rank from Takahashi.” Since Takahashi’s rank is \(S_1\), a pair is formed when the partner’s rank is B if \(S_1\) is A, or A if \(S_1\) is B.

The lottery is drawn from the \(N-1\) people excluding Takahashi. Since one person is randomly selected from them, every person has an equal probability of \(\frac{1}{N-1}\) of being chosen. Therefore, the probability of forming a pair can be expressed as:

\[ \frac{\text{Number of people with a different rank from Takahashi (excluding Takahashi)}}{N - 1} \]

If we let \(C\) be the number of people satisfying the condition, the desired probability is \(\frac{C}{N-1}\). Finally, this fraction needs to be reduced to an irreducible fraction (a fraction that cannot be simplified further). This can be achieved by finding the greatest common divisor (GCD) of the numerator \(C\) and the denominator \(N-1\), and dividing both by that GCD.

For example, if \(N=5\) and there are 2 people among the 4 people excluding Takahashi who satisfy the condition, the probability is \(\frac{2}{4}\). The GCD of 2 and 4 is 2, so dividing both the numerator and denominator by 2 gives \(\frac{1}{2}\).

Algorithm

1. Read the input: \(N\) and each member’s rank \(S_1, S_2, \ldots, S_N\).
2. Check Takahashi’s rank \(S_1\) and determine the rank to search for (target).
   • If \(S_1\) is A, then target is B
   • If \(S_1\) is B, then target is A
3. Count the number \(C\) of members from member \(2\) to \(N\) whose rank matches target.
4. Set the denominator as \(den = N - 1\).
5. Compute the GCD \(g\) of the numerator \(C\) and the denominator \(den\).
6. Divide both the numerator and denominator by \(g\), and output in the format numerator/denominator.

Complexity

• Time complexity: \(O(N)\)
  • Reading input and counting the members satisfying the condition takes \(O(N)\) time.
  • Computing the GCD takes \(O(\log N)\), which is very fast.
  • Overall, it is \(O(N)\), which runs sufficiently fast for the constraint \(N \le 10^6\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the \(N\) rank values in an array (list).

Implementation Notes

• GCD computation: In Python, you can easily compute the GCD using the standard library function math.gcd(a, b).

• Cases where the probability is 0 or 1: When the probability is \(0\) (numerator is \(0\)), the GCD equals the denominator, so reducing automatically gives 0/1. Similarly, when the probability is \(1\), it becomes 1/1, so there is no need to write special conditional branches (if statements).

• Fast I/O: Since \(N\) can be as large as \(10^6\), in Python, reading all input at once using sys.stdin.read().split() can reduce execution time and prevent Time Limit Exceeded (TLE).

  Source Code

import sys
import math

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    S1 = input_data[1]
    
    target = 'B' if S1 == 'A' else 'A'
    C = input_data[2:].count(target)
    
    den = N - 1
    g = math.gcd(C, den)
    
    print(f"{C // g}/{den // g}")

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.