#1021. [CERC2018C] Clockwork 兔子搬迁

[CERC2018C] Clockwork 兔子搬迁

题目描述

据百度百科,兔是哺乳类兔形目兔科下属所有的属的总称。农场的兔子生活在有保护的畜栏里,畜栏的边界装饰有精美的花卉装饰品。畜栏里生长着数十个可爱的橙色胡萝卜。兔子繁殖很快(这很正常,每年都有成千上万的兔子出生),农场主希望不费力地把它们安置在畜栏里。

畜栏规则地形成一排。在第一个繁殖季开始时,一些畜栏里可能没有兔子。每个繁殖季结束时,都会进行一次精心策划过的兔子搬迁。每次搬迁遵循一条简单的公式,这个公式取决于一个正整数 K。更重要的是,每次搬迁的K值由农场主根据当时的繁殖季来确定,不同的繁殖季 K 值不一定相同。对于所有畜栏,每次的搬迁工作是同时进行的。每一次搬迁,有兔子的每个畜栏中大约有一半的兔子被移到这个畜栏右边第 K 个畜栏里。目标畜栏里原来有没有兔子都没有关系。

如果某个畜栏离这一排最后一个畜栏太近(即离最后一个畜栏的距离小于 K),那么这个畜栏中的所有兔子都留在原畜栏,不会进行搬迁。

每个畜栏都可以容纳无限只兔子,并且非空的畜栏中总有足够多能够成功繁殖的兔子。

给定第一个繁殖季开始时畜栏被占用的情况。请求出使得所有畜栏中都有兔子的最少搬迁次数。

输入格式

输入仅有一行,包含一个长度为 b 的字符串,每个字符表示一个畜栏。字符只有 0(空畜栏)和 1(有兔子的畜栏)两种。第一个字符表示这一排的第一个畜栏。

输出格式

输出使得所有畜栏中都有兔子的最少搬迁次数。如果没有任何一种搬迁方案使得每个畜栏中都有兔子,输出 -1。

样例 1

输入

1010

输出

1

样例 2

输入

100110000

输出

3

数据范围与提示

1 <= b <= 40