NOI '06 P6 - The Magical Bag

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.6s
Memory limit: 256M

Problem type
National Olympiad in Informatics, China, 2006

Pòlya received a magical bag with symbols written on it that are difficult for humans to understand. Pòlya is in awe of the symbols. As he is painstakingly trying to contemplate their meaning, he discovered a magical model (known to later generations as the Pòlya model). To make the teaching of his model more vivid and interesting, he created a game for his students to play.

At the start of the game, the bag contains a_1 balls of color 1, a_2 balls of color 2, …, a_t balls of color t, where a_i \in \mathbb Z^+ (1 \le i \le t).

After the game has started, the following actions are strictly followed at each step: Randomly draw a ball from the bag (there is equal probability for drawing any ball). After Pòlya individually looks at the color of the ball, he places the ball back into the bag, and then places d balls of this color into the bag.

Let c_i represent the color of the ball drawn during the i-th step (1 \le c_i \le t), then the process of the game will yield a color sequence (c_1, c_2, \dots, c_n, \dots).

Regarding the t types of colored balls at the start of the game, Pòlya has told all of the students the amount a_1, a_2, \dots, a_t of each type. Then he asks his students: What is the probability of the color sequence from a single game satisfying the following conditions?

\displaystyle c_{x_1} = y_1, c_{x_2} = y_2, \dots, c_{x_i} = y_i, \dots, c_{x_n} = y_n

where 0 < x_1 < x_2 < \dots < x_n and 1 \le y_i \le t. In other words, given (t, n, d, a_1, a_2, \dots, a_t, x_1, y_1, x_2, y_2, \dots, x_n, y_n), you must determine the probability of the following event: "for all k, 1 \le k \le n, the ball drawn in the x_k-th draw has color y_k."

Input Specification

The first line contains three positive integer t, n (1 \le t, n \le 1\,000), and d (1 \le d \le 10).
The second line contains t integers a_1, a_2, \dots, a_t (1 \le a_k \le 10) representing the amount of each type of the t types of colored balls at the start of the game.
For the next n lines, each line contains a pair of positive integers x_i, y_i (1 \le x_1 < x_2 < \dots < x_n \le 10\,000; 1 \le y_k \le t), indicating that in step x_i, a ball of color y_i is drawn.

Output Specification

Determine the answer in fraction form (it is clear that this probability is a rational number). Output a single line in the format: numerator/denominator. At the same time, output a reduced fraction (where the numerator and denominator are relatively prime). For the probability of 0, output 0/1. For the probability of 1, output 1/1.

Sample Input 1

2 3 1
1 1
1 1
2 2
3 1

Sample Output 1

1/12

Explanation of Sample 1

Initially, the amount of each of the two types of balls are (1, 1). The probability of drawing a ball with color 1 is \frac 1 2.
Before the second draw, the amounts of the two types of balls are (2, 1). The probability of drawing a ball with color 2 is \frac 1 3.
Before the third draw, the amounts of the two types of balls are (2, 2). The probability of drawing a ball with color 1 is \frac 1 2.
Therefore, the total probability for all three draws is \frac 1 {12}.

Sample Input 2

3 1 2
1 1 1
5 1

Sample Output 2

1/3

Problem translated to English by Alex.


Comments

There are no comments at the moment.