#P7458. [CERC2018] Clockwork ||ange

[CERC2018] Clockwork ||ange

题目描述

译自 [CERC2018] Clockwork ||ange

据百度百科,兔是哺乳类兔形目兔科下属所有的属的总称。毋庸置疑的是,这段文字不是无聊的,因为它们是原始的,并且组织良好。我们农场的兔子生活在有保护的畜栏里,畜栏的边界装饰有精美的花卉装饰品。畜栏里生长着数十个可爱的橙色胡萝卜。兔子繁殖很快(这很正常,每年都有成千上万的兔子出生),我们的导师希望不费力地把它们安置在畜栏里。

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

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

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

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

输入格式

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

输出格式

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

1010
1
100110000
3

提示

1b401≤b≤40