A. 吃苹果

    远端评测题 1000ms 256MiB

吃苹果

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制:1 Sec 内存限制:256 MB 输入文件:apple.in 输出文件:apple.out

你的面前有一个盘子,盘子里有 $N$ 个苹果。

重复执行下面两种操作之一,把盘子变为空,求最少操作次数。操作可以以任意顺序执行。

- 选择一个非负整数 $k$,吃掉盘子里 $2^k$ 个苹果。当盘子中苹果不足 $2^k$ 个时,不能执行该操作。

- 选择一个非负整数 $k$,向盘子中加入 $2^k$ 个苹果。

输入格式

输入一行,给出 $N$。

输出格式

输出最小操作次数。

样例

样例 1

101

2

样例说明:

一共有 55 个苹果,可以按如下操作:

- 吃掉 $2^2=4$ 个苹果

- 吃掉 $2^0=1$ 个苹果

样例 2

111

2

样例说明:

77 个苹果,先加 11 个苹果,再一次性吃掉 88 个。

样例 3

11110101101110110001100

8

数据范围

对于 30% 的数据,$N \le 2^{10}$。

对于 100% 的数据,$1 \le N \lt 2^{200000}$,$N$ 以不带前导零的二进制字符串形式给出。

2026年9月月赛-Div1

未参加
状态
已结束
规则
OI
题目
4
开始于
2026-9-22 17:59
结束于
2026-9-30 23:59
持续时间
2.5 小时
主持人
参赛人数
21