2544. 牛来打字
1000ms
256MB
简单
动态规划
Dynamic Programming
题目描述
牛来要在电脑前打字。一共需要打 $n$ 个字，但现在文档里只有一个字。
牛来有两种操作可以做。假设现在已经有 $x$ 个字，牛来可以选择：
- 往文档最后加一个字。字数变成 $x+1$。
- 把文档复制粘贴一遍。字数变成 $2x$。
问牛来至少需要多少次操作，才能得到恰好 $n$ 个字。
输入格式
仅一行，一个正整数 $n$。
输出格式
仅一行，一个正整数，表示最少操作次数。
样例 1
输入 (Input)
输出 (Output)
样例 2
输入 (Input)
输出 (Output)
样例说明
样例数据 1，$1\to 2\to 4\to8\to 16$，共 4 步。
样例数据 2，$1\to 2\to 4\to 5$，共 3 步。
对于 $100\%$ 的数据，$n\leq 10^6$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功