問題一覧 > 通常問題

No.47 Tap the Pocket and the Biscuits Double

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 1517
作問者 : yuki2006
お気に入りにしたユーザー ProblemId : 89 / 自分の提出
問題文最終更新日: 2026-06-26 16:02:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 41 (順位表) の他の問題:

Problem Statement

Sara obtained a "Mysterious Pocket".

When some biscuits are put into the "Mysterious Pocket" and it is tapped, the number of biscuits put in doubles.
Sara initially has 1 biscuit, and she wants to use the "Mysterious Pocket" to end up with exactly \(N\) biscuits and eat them all.
(She cannot eat more than that, so the number of biscuits must not go over.)

Find the minimum number of times Sara needs to tap the pocket to end up with exactly N biscuits.

Input

N

The number of biscuits Sara wants to eat, \(N (1 \le N \le 10^{8})\), is given.

Output

Output the minimum number of times Sara taps the pocket.

Sample

Sample 1
Input
3
Output
2

First, put 1 biscuit into the pocket and tap it.
This gives 2 biscuits.
Put 1 of those 2 biscuits into the pocket and tap it once more, which gives 3 biscuits in total.
Thus, 2 taps give 3 biscuits.

Sample 2
Input
4
Output
2

First, put 1 biscuit into the pocket and tap it.
This gives 2 biscuits.
Tap again with both of the 2 biscuits as they are, which gives 4 biscuits in total.

Sample 3
Input
1000
Output
10

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。