SRM529 easy(250) - avrmicom @ ウィキ

2012/1/25
212.33 points
約12分

問題概要

N個のセルにそれぞれpawnsが複数入っていて、右端から順に１セルずつ左に移していく。移すとき２つが１つに合わさってカウントされる。
最終的に左端には何個のpawnsが入っているか。問題の入力はN個のセルのそれぞれのpawnsの個数配列。

pawnsって何だったんだ？
pawn:人質、チェスのポーン、将棋の歩

例

{0,2}
Returns: 1
There are two pawns on cell 1. You can remove them both and place a pawn onto cell 0.

解法

そのまんま。右セルの値を半分ずつ左に移していく。

解答

#include <vector>
#include <iostream>
using namespace std;

class PairingPawns{
public:
	int savedPawnCount(vector <int> start){
		if(start.size()>1){
			for(int i=start.size()-1; i>0; i--){
				start[i-1] += start[i]/2;
			}
		}
		return start[0];
	}
};