Mnogomet
레이팅 미적용의견: 0
\(5^{th}\) round, February \(16^{th}\), 2013
2N people are playing football (soccer), divided into two teams. Each player wears a dress with the
team logo and a unique (in the team) positive integer between 1 and N, inclusive. For each player, we
know his precision, the set of teammates whom he can pass the ball to (F) and the set of opponents
who can take the ball from him (E). When a player comes into possession of the ball, after exactly one
second one of the following events will happen:
o the player passes the ball to a random teammate from the set F,
o a random opponent from the set E takes the ball from him,
o the player attempts a shot at the goal.
If the player attempts a shot, the probability of scoring a goal is equal to his precision. After the
shot, whether it was successful or not, the ball is awarded to the player number 1 from the opposing
team.
The probabilities of different events are in the proportion |F| : |E| : 1, in order, and depend only on
the player currently in possession of the ball (|S| determines the size of the set S corresponding to the
current player), not on any previous events in the game. The word “random” means that all players
from the set F (or E) have the same probability of being passed (or taking) the ball by (from) the
player that is currently in the ball's possession. The time that a ball spends outside of a player's
possession is negligible.
The match begins with player 1 from the first team in possession of the ball and ends either when one
team has scored R goals or when T seconds have elapsed, whichever happens first. For each
possible final score, determine the probability that the match will end with it.
The following image illustrates the player arrangement for the second test example:
The first line of input contains three positive integers: N (\(1 \le N \le 100\)), the number of players in each
team, R (\(1 \le R \le 10\)), the number of goals needed for victory, and T (\(1 \le T \le 500\)), the maximum
duration of the match.
The following N lines contain descriptions of the first team's players, one per line, while the next N
lines after that contain descriptions of the second team's players. A description of a single player
consists of a real number p (\(0 \le p \le 1\)), the player's precision, followed by two positive integers, nF (0
≤ \(nF \le N - 1\)) and nE (\(0 \le nE \le N\)), the sizes of the sets F and E, respectively, followed by \(nF + nE\)
player labels representing the sets F and E themselves (in that order), all spa\(ce-se\)parated. Note that the
labels from F represent players from one team, and labels from E the other team. The set F will not
contain the label of the player currently being described.
\(5^{th}\) round, February \(16^{th}\), 2013
The match can theoretically end with one of R * (\(R + 2\)) different final results. For each result, output
the probability of its realization as a real number, one per line. Order the results first by the number of
goals scored by the first team, then by the number of goas scored by the second team, in ascending
order. The permitted difference from the exact value for each probability is 0.000001.
1 1 2
0.5 0 1 1
0.5 0 1 10.56250
0.18750
0.250002 2 5
0.0 1 2 2 1 2
1.0 0 0
0.5 1 0 2
0.5 1 0 10.2578125
0.2812500
0.0703125
0.1718750
0.1640625
0.0234375
0.0156250
0.0156250Clarification of the first example:
The star denotes the player in possession of the ball in the beginning. The match lasts for only T = 2
moves or until someone scores R = 1 goal. Since N = 1, there are only two players in the match,
playing one against the other. Both players have the precision of 0.5, which means that each has a 50%
chance of scoring a goal when trying to shoot, after which the ball is awarded to the opponent.
Let us label the grey player as A, and the white player as B. Under these assumptions, there are only 6
possible matches. Each of them is described in the table below, with the corresponding probability,
description and outcome:
0.25
A decides to shoot and scores!
1:0
0.25 * 0.25
A decides to shoot, but misses.
B decides to shoot and scores!
0:1
0.25 * 0.25
A decides to shoot, but misses.
B decides to shoot, but also misses.
0:0
0.50 * 0.25
A loses the ball to B.
B decides to shoot and scores!
0:1
0.50 * 0.50
A loses the ball to B.
B loses the ball to A.
0:0
0.50 * 0.25
A loses the ball to B.
B decides to shoot, but misses.
0:0
By summing probabilities for particular final results, we obtain the following solution:
0:0
0.25 * 0.25 + 0.5 * 0.5 + 0.5 * 0.25
0.5625
0:1
0.25 * 0.25 + 0.5 * 0.25
0.1875
1:0
0.25
0.25
평가 및 의견
Mnogomet
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Mnogomet