RPSChamps
SRM 329 · 2006-12-09 · by dmytro
Problem Statement
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.
Notes
- The returned value must have absolute or relative error less than 1E-9.
- If a round is replayed one or more times, every replay is counted towards the total number of rounds for that tournament.
Constraints
- N will be between 1 and 500, inclusive.
1 Returns: 0.0
Since there is only one participant, no rounds are needed to determine placement.
2 Returns: 1.5
There is a 1/3 probability of each round being replayed. When a round is not replayed, all places are immediately determined.
3 Returns: 3.0
10 Returns: 35.59012622220019
20 Returns: 1201.2046591553308
Submissions are judged against all 24 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RPSChamps with a public method double numberOfMoves(int N) · 24 test cases · 2 s / 256 MB per case