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 vector <int> start with N elements. For each i, element i of start is the initial number of pawns on cell i.
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.
N层空间存放着马前卒，第N-1层的2个马前卒可以配对走向第N-2层，使第N-2层的马前卒数量加1，给出各层马前卒数量，求他们按照规则行进，第0层的马前卒数量
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
class PairingPawns
{
public:
int savedPawnCount(vector <int> start)
{
for(int i=start.size()-1; i>0; i--)
{
start.at(i-1)+=start.at(i)/2;
}
return start.at(0);
}
};
posted on 2012-01-15 04:02
玉香 阅读(225)
评论(0) 编辑 收藏 引用 所属分类:
TopCoder