ARC088 C : Multiple Gift(300)

作成日:2017.12.31
最終更新日:2017.12.31

問題概要

問題本文

 $X$以上$Y$以下の整数からなる数列$\{A\}$で、$A_{i+1}$は$A_i$より大きい$A_i$の倍数であるものの要素数の最大値を求めよ。
制約
$1 \leq X \leq Y \leq 10^{18}$

考え方

 条件より数列の初項は$X$以上であり、$A_{i+1} \geq 2A_i$が成り立つ。 各要素が$Y$以下であるという条件も踏まえると、$A_i$は取り得る最小のものを取るのが良い。 すなわち$A_i$$= 2^i X$$(i \geq 0)$とするのが最善である。 答えは$2^i X$$> Y$となる最小の$i$である。

ソースコード

マクロ等はこちら

LL X,Y;

int main(){
	cin >> X >> Y;
	int ans = 0;
	while(X<=Y){
		X <<= 1;
		++ans;
	}
	cout << ans << endl;
	return 0;
}

解法まとめ

 $2^i X$$> Y$となる最小の$i$が答えである。(5-10行)

ARC088の他の問題 D E F

自己紹介

プログラミングとか合成音声とか
詳しくはこちら
twitter

プライバシーポリシー

個人情報利用についてはこちら

最終更新日:2023.03.05

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

その他

全体MENU

寄付モドキ

0冂から10000冂まで
詳しくはこちら