RoseDressGame
SRM 781 · 2020-03-19 · by misof
Problem Statement
Coco and Yves are playing a two-player game. As usual, in the game they take alternating turns. Coco plays first. The player unable to make a valid move wins the game. (I.e., the player whose move creates such a situation loses the game.)
The game is played using a collection of models. Each model is wearing the same dress, but their dresses are decorated using different numbers of roses.
In each turn, the current player may choose any one model that still has some roses on their dress and remove some positive number of roses (maybe all of them) from that dress.
After each turn, if the dresses of two models contain the same number of roses, the move has created a socially awkward situation in which two of the models are dressed the same. Whenever that happens, both models retreat to their dressing rooms immediately, and they will be unavailable for the rest of the game.
You are given the initial numbers of roses on the individual dresses in the
Constraints
- roses will contain between 1 and 50 elements, inclusive.
- Each element of roses will be between 1 and 10^9, inclusive.
- Elements of roses will be distinct.
{1, 47, 7}
Returns: "Coco"
One possible winning move for Coco is to remove 40 of the 47 roses from the middle dress. This will send two of the models away from the game. Yves will be forced to take the last remaining rose from the last remaining dress and he will lose the game immediately.
{2, 3}
Returns: "Yves"
Coco loses this game. Let's examine her options: If she creates a dress with no roses, Yves will take all but one roses off the other dress and Coco is forced to lose. If she creates a dress with one rose, Yves will take all roses from the other dress and Coco is forced to lose. If she takes one rose from the dress that has three, both models leave and she loses the game immediately.
{12, 20, 24}
Returns: "Yves"
{2, 4, 6, 8, 9}
Returns: "Coco"
{1, 2, 4, 6, 8, 9}
Returns: "Yves"
Submissions are judged against all 234 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RoseDressGame with a public method string getWinner(vector<int> roses) · 234 test cases · 2 s / 256 MB per case