National Olympiad in Informatics, China, 2006
Day 2, Problem 3 - The Magical Bag
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 a1 balls of color 1, a2 balls of color 2, …, at balls of color t, where ai ∈ ℤ+ (1 ≤ i ≤ 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 ci represent the color of the ball drawn during the i-th step (1 ≤ ci ≤ t), then the process of the game will yield a color sequence (c1, c2, …, cn, …).
Regarding the t types of colored balls at the start of the game, Pòlya has told all of the students the amount a1, a2, …, at of each type. Then he asks his students: What is the probability of the color sequence from a single game satisfying the following conditions?
cx1 = y1, cx2 = y2, …, cxi = yi, …, cxn = yn
where 0 < x1 < x2 < … < xn and 1 ≤ yi ≤ t. In other words, given (t, n, d, a1, a2, …, at, x1, y1, x2, y2, …, xn, yn), you must determine the probability of the following event: "for all k, 1 ≤ k ≤ n, the ball drawn in the xk-th draw has color yk."
The first line contains three positive integer t, n (1 ≤ t, n ≤ 1000), and d (1 ≤ d ≤ 10).
The second line contains t integers a1, a2, …, at (1 ≤ ak ≤ 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 xi, yi (1 ≤ x1 < x2 < … < xn ≤ 10000; 1 ≤ yk ≤ t), indicating that in step xi, a ball of color yi is drawn.
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
Sample Input 1
2 3 1 1 1 1 1 2 2 3 1
Sample Output 1
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 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 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 1/2.
Therefore, the total probability for all three draws is 1/12.
Sample Input 2
3 1 2 1 1 1 5 1
Sample Output 2
Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 256M
Added: Jul 24, 2014
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3