PairingPawns
SRM 529 · 2011-11-22 · by misof
Problem Statement
"Pairing pawns" is a game played on a strip of paper, divided into N cells. The cells are labeled 0 through N-1. Each cell may contain an arbitrary number of pawns.
You are given a
The goal of the game is to bring as many pawns as possible to cell 0.
The only valid move looks as follows:
- Find a pair of pawns that share the same cell X (other than cell 0).
- Remove the pair of pawns from cell X.
- Add a single new pawn into the cell X-1.
You may make as many moves as you wish, in any order.
Return the maximum number of pawns that can be in cell 0 at the end of the game.
Notes
- You may assume that the answer will always fit into an int.
- Note that you are only given the int[] start. The number of cells N can be determined as the length of start.
Constraints
- start will contain between 1 and 20 elements, inclusive.
- Each element of start will be between 0 and 1,000,000, inclusive.
{0,2}
Returns: 1
There are two pawns on cell 1. You can remove them both and place a pawn onto cell 0.
{10,3}
Returns: 11
There are 10 pawns already on cell 0. You can add another one by removing two pawns from cell 1. Note that at the end of the game cell 1 will still contain one pawn that cannot be used anymore.
{0,0,0,8}
Returns: 1
After 7 moves you can get a single pawn to cell 0. The rest of the board will be empty.
{0,1,1,2}
Returns: 1
Again, a single pawn can reach the leftmost cell.
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,123456}
Returns: 0
That's a lot of pawns! But they are too far away. In this case it is impossible for a pawn to reach cell 0.
Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PairingPawns with a public method int savedPawnCount(vector<int> start) · 128 test cases · 2 s / 256 MB per case