#6211. 「美团 CodeM 决赛」elimination

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: samzhang

题目描述

有一个长为 N 的 01 串 A ,有两个老哥老 G 和老 T,他们会按照某种方式不断修改这个 01 串。

每一步的流程如下(假设这个串当前的长度为 L ):

  • 老 G 会去掉当前 01 串的第一个字符,得到一个长为 L-1 的 01 串。
  • 老 T 会去掉当前 01 串的最后一个字符,也得到一个长为 L-1 的 01 串。
  • 把这个串变成老 G 和老 T 得到的串的 xor。

比如当前的串是 \texttt{00110} ,老 G 会得到 \texttt{0110} ,老 T 会得到 \texttt{0011} ,xor 得到 \texttt{0101}

问经过多少步,这个 01 串不包含字符 \texttt{1}
如果这个 01 串一直有 \texttt{1} 直到变成空串,输出 -1
01 串初始至少有一个 \texttt{1}

输入格式

多组数据,请一直读到文件结束为止。
每组数据一行,一个 01 串。

输出格式

每组数据一行,输出一个答案。

样例

样例输入

00110

样例输出

3

样例解释

  • 第一步:
    • 开始时的串是 \texttt{00110}
    • 老 G 得到的串是 \texttt{0110}
    • 老 T 得到的串是 \texttt{0011}
    • xor 后得到的串是 \texttt{0101}
  • 第二步:
    • 开始时的串是 \texttt{0101}
    • 老 G 得到的串是 \texttt{010}
    • 老 T 得到的串是 \texttt{101}
    • xor 后得到的串是 \texttt{111}
  • 第三步:
    • 开始时的串是 \texttt{111}
    • 老 G 得到的串是 \texttt{11}
    • 老 T 得到的串是 \texttt{11}
    • xor 后得到的串是 \texttt{00}

三步之后这个串全部变成 \texttt{0} ,所以答案是 3

数据范围与提示

对于所有每个测试点的任何一组数据,数据组数不多于 7 组, N\leq 8\times 10^6
一个测试点的串总长可能很长(不超过 5.6\times 10^7 ),请大家注意读入的方式