Scribd
Upload
61 views2 pages

Expected Interesting Games in Starcraft

John and Charlie are watching a Starcraft match replay, but John knows the match lasted K games, which spoils his enjoyment of the games. The task is to calculate the expected number of interesting games from Charlie's perspective, given the total number of games N and the known games K. The output should be presented as an irreducible fraction representing the expected interesting games.

Uploaded by

Ahmed Gamberli
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
61 views2 pages

Expected Interesting Games in Starcraft

John and Charlie are watching a Starcraft match replay, but John knows the match lasted K games, which spoils his enjoyment of the games. The task is to calculate the expected number of interesting games from Charlie's perspective, given the total number of games N and the known games K. The output should be presented as an irreducible fraction representing the expected interesting games.

Uploaded by

Ahmed Gamberli
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Spoiler

John and Charlie are avid Starcraft fans and they love watching match replays. Tonight they are
watching a replay of a match between two top players, HerO and Maru. The match is a best-of-N,
meaning that the players play game after game until one wins the majority of N games (N is an odd
number). If one player reaches a majority before N games, he wins the match immediately
(remaining games are not played). For example, a best-of-7 match ends when a player reaches 4
wins, so it may last between 4 games (ending in a 4-0) and 7 games (ending in a 4-3). There are no
draws in Starcraft and HerO and Maru have equal chances of winning any given game.

John accidentally peeked at the game list and saw that the match lasted K games. Charlie does not
know K. This spoils John's fun, because he only enjoys watching interesting games, games whose
winner he does not know in advance. Furthermore, as soon as John can predict the outcome of an
upcoming game, he blurts out "I know who wins the next game" and tells Charlie the value of K.

Task

Given N and K, what is the expected number of interesting games to be watched tonight, from
Charlie's perspective?

Input data

The input file [Link] contains a single line with two numbers N and K.

Output data

The output file [Link] must contain the answer as an irreducible fraction. Write the numerator on
the first line and the denominator on the second line.

Limits and constraints

• 1 ≤ N < 2,000;
• N is odd;
• (N + 1) / 2 ≤ K ≤ N;
• Time limit: 0.6 seconds.
• Memory limit: 8 MB
Subtasks

Subtask Percent of points Additional input constraints


1 20 N < 50
2 40 50 < N < 300
3 20 300 < N < 1,600
4 20 none

Example

[Link] [Link]
74 1
1

Here, only the first game is interesting. Since the match lasts for 4 games, it must end in a 4-0.
Therefore, whoever wins the first games must have won every game, so games 2, 3 and 4 are not
interesting.

[Link] [Link]
54 5
2

We know that the match ends 3-1 (or 1-3). The first two games are interesting (winners cannot be
predicted). After two games, the score can be:

• 2-0 with a 25% chance. Then the last two games will not be interesting, as the match can only
go 2-1, then 3-1 from here.
• 0-2 with a 25% chance. Again, the last two games will not be interesting.
• 1-1 with a 50% chance. In this case the third game will also be interesting. Whoever gets to
2-1 must go on to win 3-1, so the fourth game will not be interesting.

You might also like