시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
0.6 초 | 1024 MB | 12 | 0 | 0 | 0.000% |
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.
Given N and K, what is the expected number of interesting games to be watched tonight, from Charlie's perspective?
The input contains a single line with two numbers N and K.
The output must contain the answer as an irreducible fraction. Write the numerator on the first line and the denominator on the second line.
번호 | 배점 | 제한 |
---|---|---|
1 | 20 | N < 50 |
2 | 40 | N < 300 |
3 | 20 | N < 1,600 |
4 | 20 | none |
7 4
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.
5 4
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: