N people take part in a Rock-Paper-Scissors tournament. The purpose of the tournament is to assign every participant a distinct place from 1 to N.
The places are assigned by running a number of rounds of Rock-Paper-Scissors.
In each round, each participant casts one of three figures - Rock, Paper, or Scissors - with equal probability. Rock beats Scissors, Paper beats Rock, and Scissors beats Paper. After all the participants have cast their figures, the round is replayed if one of the following occurred:
- All participants cast the same figure.
- Each of the three figures was cast at least once.
If the round is not replayed, then for every pair of participants who cast different figures, the one whose figure beat the other player's figure will take a higher place. Within each group of players who cast equal figures, an independent subtournament will be run using the same rules. Of course, if a group contains only one player, no rounds are needed to determine that player's placement within that group.
For example, consider a tournament between 5 players where the results of the first round are as follows:
- Player 1 casts Rock
- Player 2 casts Scissors
- Player 3 casts Scissors
- Player 4 casts Rock
- Player 5 casts Scissors
The players will be divided into 2 groups: {P1, P4} and {P2, P3, P5}. An independent subtournament will be run for each group. Since Rock beats Scissors, the players from the first group will take overall places in the range 1-2 depending on the results of their subtournament, and players assigned to the second group will take places in the range 3-5 depending on the results of their subtournament.
Given N, the number of participants in the tournament, return the expected number of rounds.
|