FiveHundredEleven
SRM 511 · 2011-05-25 · by rng_58
SRM 511 · 2011-05-25 · by rng_58 · Dynamic Programming
Problem Statement
Problem Statement
Fox Ciel and Toastman are playing a game.
The game uses a memory and N cards. Initially the value of the memory is set to zero. You are given aint[] cards containing exactly N elements. cards[i] is the number written on the i-th card.
Ciel and Toastman take alternate turns, and Ciel plays first. In each turn, the player chooses a card and removes the card from the game (this card can't be used later). If the chosen card contains x and the value of the memory is y, the value of the memory is changed to (x | y). The '|' symbol stands for bitwise OR (see notes for clarification). If a player can't make a move (because there are no cards left), or if after a player's move the memory becomes 511, this player loses.
Determine the winner when both players play optimally. If Fox Ciel wins, return "Fox Ciel" (quotes for clarity). If Toastman wins, return "Toastman" (quotes for clarity).
The game uses a memory and N cards. Initially the value of the memory is set to zero. You are given a
Ciel and Toastman take alternate turns, and Ciel plays first. In each turn, the player chooses a card and removes the card from the game (this card can't be used later). If the chosen card contains x and the value of the memory is y, the value of the memory is changed to (x | y). The '|' symbol stands for bitwise OR (see notes for clarification). If a player can't make a move (because there are no cards left), or if after a player's move the memory becomes 511, this player loses.
Determine the winner when both players play optimally. If Fox Ciel wins, return "Fox Ciel" (quotes for clarity). If Toastman wins, return "Toastman" (quotes for clarity).
Notes
- If a and b are single bits then a | b is defined as max(a, b). For two integers, A and B, in order to calculate A | B, they need to be represented in binary: A = (an...a1)2, B = (bn...b1)2 (if the lengths of their representations are different, the shorter one is prepended with the necessary number of leading zeroes). Then A | B = C = (cn...c1)2, where ci = ai | bi. For example, 10 | 3 = (1010)2 | (0011)2 = (1011)2 = 11.
Constraints
- cards will contain between 1 and 50 elements, inclusive.
- Each element of cards will be between 0 and 511, inclusive.
Examples
0)
{3, 5, 7, 9, 510}
Returns: "Fox Ciel"
If Fox Ciel chooses 510 in her first turn, the value of the memory after Toastman's turn becomes 511 regardless of his choice.
1)
{0, 0, 0, 0}
Returns: "Toastman"
The value of the memory never becomes 511. After each player chooses 2 cards, there are no cards left and Fox Ciel loses.
2)
{511}
Returns: "Toastman"
After Fox Ciel chooses the only card in her first turn, the value of the memory becomes 511 and Fox Ciel loses.
3)
{0, 0, 0, 0, 0}
Returns: "Fox Ciel"
4)
{7, 56, 448}
Returns: "Toastman"
Submissions are judged against all 217 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FiveHundredEleven with a public method string theWinner(vector<int> cards) · 217 test cases · 2 s / 256 MB per case