torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder, Single Round Match 648, Division 2, Level 1 : KitayutaMart2

問題概要

 ある店ではりんごを売っている.このりんごの値段は,買う個数を増やす毎に,1 つ目は K ,2 つ目は 2K ,3 つ目は 4K というように値段が上がっていく.一般的に書くと,i 個目 (0-based) のりんごの値段は 2^iK である.
 正整数 T が与えられる.合計金額が T となるようにりんごを買ったとすると,買ったりんごの数はいくつか? なお,解が必ず存在し,しかも一意に定まることは保証される.
 T \leq 163,680

解法

 りんごの値段は,1 つ買う毎に倍々になっていくので,買えるりんごの数は O( \log T ) 個になります.T の制約から,さほど多くのりんごを買うことはできないので,りんごの購入と値段の更新を愚直にシミュレーションしても Time Limit に間に合わせることができます.
 りんごを一つ買ったときの変化を,TK 減った後に K が倍になるという具合に実装すると,0 < T である間この処理を繰り返せば,繰り返された回数が答えです.

コード

class KitayutaMart2
{
public:
	int numBought( int K, int T )
	{
		int res = 0;
		while ( T )
		{
			++res;
			T -= K;
			K *= 2;
		}
		return res;
	}
};