kmjp's blog

競技プログラミング参加記です

Saiko~ No Contesuto #02 : 倍々オークション

焼肉チャレンジはHRのSubmit仕様に苛立ち途中で撤退してしまいました。
https://www.hackerrank.com/contests/camypapercon02/challenges/doubling-auction

問題

あるX円の商品のオークションを行う。
初期価格wに対し、2*w<Xの場合、現在の価格の倍額を提示する。
これ以上倍額が提示されなくなったらオークション終了で、落札となる。

落札価格が最小となる初期金額のうち、倍額提示回数が最大となるものを求めよ。

解法

落札額をvとすると、2*v<Xである最少なvはv=X/2+1で求まる。
あとはvが2の累乗で割れる限り割っていけばよい。

int N;
ll A;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	while(N--) {
		cin>>A;
		A=A/2+1;
		while(A%2==0) A/=2;
		cout<<A<<endl;
	}
}

まとめ


あまり問題文をちゃんと読まずにサンプル見て解いてしまった。