Byes
TCO19 Round 2A · 2019-04-15 · by misof
Problem Statement
Recently there was a single-elimination tournament. The tournament consisted of multiple rounds. In each round the players were divided into pairs, each pair played a game, and the loser of each game was eliminated from the tournament. Once there was only a single player left, the tournament terminated and that player was declared its winner.
If the number of players in a round is odd, it is impossible to divide all of them into pairs. Whenever such a situation arised, one of the players was awarded a bye and advanced into the next round without playing a game.
You are given the
Notes
- For the constraints given below the answer always exists and fits into a long.
Constraints
- lowerBound will be between 1 and 2^60, inclusive.
- numberOfByes will be between 0 and 60, inclusive.
3 1 Returns: 3
A tournament with three people looks as follows: In the first round one person gets a bye and the remaining two people play a game. Two people advance from this round. In the second round the two remaining people face off. The loser is out, the winner wins the tournament. As the tournament with three people had exactly one bye, this is what we are looking for.
4 1 Returns: 6
In a tournament with four players there are no byes. In a tournament with five players there are two byes (one in the first round and one in the second). In a tournament with six players there is a single bye (in the second round), hence six is the correct answer for this test case.
1234567890123 0 Returns: 2199023255552
Watch out for integer overflow.
200 4 Returns: 202
127377 60 Returns: 1152921504606846977
Submissions are judged against all 136 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class Byes with a public method long long getNumberOfPlayers(long long lowerBound, int numberOfByes) · 136 test cases · 2 s / 256 MB per case