Sziasztok!
Egy újabb topcoderes feladat, nem olyan túl bonyolúlt, de nem is
sablon, ha jól emlékszem. :)
You are organizing a local Rock-Paper-Scissors Tournament, where the
best N players in your town will compete for fame and prizes. You have
already ranked the participants according to their performance in the
qualifying round, so each one of them will have a seed for winning the
tournament in the range from 1 to N.
The tournament will be in a knockout format and will consist of
multiple rounds. During each round the competitors still left in the
competition are randomly paired up with each other. The winners from
each game advance to the next round. The great champion is the winner
of the final game between the last two remaining players.
The tournament starts soon, and you are preoccupied with some
pre-statistics. You estimate that a player with any seed S can win
against players with greater seeds, and against ones with lower seeds,
if the difference between their seeds is not greater than sqrt(C * S),
where C is a constant. Assuming that the outcome of all the played
games during the tournament agrees with your estimation, a player can
win the tournament if there exists an assignment of games in each of
the rounds such that the player can win each round.
You will be given two ints, rounds, denoting the number of rounds, and
the constant C. Return the greatest seed of a player that could win
the tournament. Note that N, the number of competitors will be N =
2rounds.
Definition
Class:
RPSTournament
Method:
greatestSeed
Parameters:
int, int
Returns:
int
Method signature:
int greatestSeed(int rounds, int C)
(be sure your method is public)
Constraints
-
rounds will be between 1 and 16, inclusive.
-
C will be between 0 and 1500, inclusive.
Examples
0)
2
0
Returns: 1
There is no room for surprises here. Since nobody can win against a
higher-rated opponent, the lowest seed will win the tournament.
1)
3
1
Returns: 6
Player 2 can win against player 1, so both of them can win the final
if they are to meet in that phase of the competition. Since players 3
and 4 can beat player 2, they can win the tournament as long as player
2 wins against player 1 somewhere before the final. Finally, players 5
and 6 can beat player 4 in the final, as long as player 4 wins against
player 2 in the semifinals and player 2 eliminates player 1 in the
first round. It is impossible for players 7 and 8 to win the
tournament. We return the greatest seed of those who can win, namely
6.
2)
4
1
Returns: 9
3)
7
3
Returns: 50
4)
15
180
Returns: 9755
Watch out for timeout!