Codechef-CIELRCPT : Ciel and Receipt

問題概要

P(<100000)円を支払いたい。1円、2円、4円、…2048円玉が存在するとき最小何枚で支払えるか求める問題。

解法

貪欲に選べばよい。

acceptされたコード

#include <cstdio>
using namespace std;

inline int countPopulation(unsigned int x) {
	x -= ((x >> 1) & 0x55555555);
	x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
	x = ((x >> 4) + x) & 0x0f0f0f0f;
	x += (x >> 8);
	x += (x >> 16);
	return (x & 0x0000003f);
}

int P;

void init() {
	scanf("%d", &P);
}

int solve() {
	return P / 2048 + countPopulation(P % 2048);
}

int main() {
	int T;
	scanf("%d", &T);
	for (int _ = 0; _ < T; ++_) {
		init();
		printf("%d\n", solve());
	}
	return 0;
}