YetAnotherCardGame
2015 TCO Parallel 2C · 2015-04-08 · by rng_58
2015 TCO Parallel 2C · 2015-04-08 · by rng_58 · Dynamic Programming
Problem Statement
Problem Statement
Petr and Snuke are playing a cooperative card game.
The game is played with special cards: each card is labeled with some positive integer.
The integers on cards are not necessarily distinct.
At the beginning of the game Petr is holding some cards in his hand and Snuke is holding all the other cards in his hand. You are givenint[] s petr and snuke that describe the state at the beginning of the game:
the elements of petr are the numbers on Petr's cards and the elements of snuke are the numbers on Snuke's cards.
During the game the players will place some of their cards onto a pile. Initially, the pile is empty. The players take alternating turns, Petr goes first. In each turn, if the current player has no cards in his hand, the game ends. Otherwise, the player must make exactly one valid move. There are three types of valid moves:
Petr and Snuke have a common goal: they want to create a pile with as many cards as possible. Return the size of the pile at the end of the game, assuming that they cooperate and play the game optimally.
At the beginning of the game Petr is holding some cards in his hand and Snuke is holding all the other cards in his hand. You are given
During the game the players will place some of their cards onto a pile. Initially, the pile is empty. The players take alternating turns, Petr goes first. In each turn, if the current player has no cards in his hand, the game ends. Otherwise, the player must make exactly one valid move. There are three types of valid moves:
- If the pile is empty, the player may choose any card and place it onto the pile.
- If the pile is not empty, the player may choose any card and place it on top of the pile. However, this move is only valid if the number on the new card is strictly greater than the number on the card that was previously on the top of the pile.
- The player may always choose one of his cards and eat it.
Petr and Snuke have a common goal: they want to create a pile with as many cards as possible. Return the size of the pile at the end of the game, assuming that they cooperate and play the game optimally.
Constraints
- petr and snuke will contain between 1 and 50 elements, inclusive.
- petr and snuke will contain the same number of elements.
- Each element in petr and snuke will be between 1 and 100, inclusive.
Examples
0)
{2, 5}
{3, 1}
Returns: 3
One optimal way is as follows. Petr puts 2 onto the pile. Snuke puts 3 onto the pile. Petr puts 5 onto the pile. Snuke eats 1. The game ends because Petr has no cards in his hand.
1)
{1, 1, 1, 1, 1}
{1, 1, 1, 1, 1}
Returns: 1
The integers on cards are not necessarily distinct.
2)
{1, 4, 6, 7, 3}
{1, 7, 1, 5, 7}
Returns: 6
3)
{19, 99, 86, 30, 98, 68, 73, 92, 37, 69, 93, 28, 58, 36, 86, 32, 46, 34, 71, 29}
{28, 29, 22, 75, 78, 75, 39, 41, 5, 14, 100, 28, 51, 42, 9, 25, 12, 59, 98, 83}
Returns: 28
4)
{95, 40, 1, 31, 27, 80, 10, 33, 31, 55, 41, 5, 51, 40, 5, 53, 52, 76, 15, 95, 8, 27, 57, 59, 24, 59, 89, 38, 24, 81, 55, 59, 82, 5, 72, 37, 39, 84, 28, 85, 35, 60, 72, 13, 6, 2, 92, 78, 75, 98}
{41, 43, 23, 18, 36, 48, 85, 85, 35, 60, 46, 40, 89, 25, 39, 34, 32, 24, 23, 9, 84, 70, 50, 59, 95, 74, 70, 21, 21, 87, 87, 59, 29, 85, 89, 42, 41, 78, 57, 16, 89, 73, 39, 86, 89, 67, 37, 14, 10, 74}
Returns: 61
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class YetAnotherCardGame with a public method int maxCards(vector<int> petr, vector<int> snuke) · 57 test cases · 2 s / 256 MB per case