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; }