P16129 [ICPC 2018 NAIPC] Flashing Fluorescents

有一排 $n$ 盏灯，每盏灯都有自己的按钮。按下一盏灯的按钮会切换该灯的状态：如果灯是亮的，则会熄灭；如果灯是灭的，则会点亮。灯的状态变化以 1 秒为时间步长。你可以在任何时间按下按钮，但按钮的效果要到下一个时间步才会生效。在每个时间步开始之前，你可以选择最多按下一个按钮（也可以选择不按任何按钮）。 按下按钮不仅会影响所按的那盏灯，还会影响其后方的所有灯。具体来说，如果你在第 $k$ 个时间步开始前按下第 $i$ 个按钮，那么第 $(i + m)$ 盏灯将在第 $(k + m)$ 个时间步发生状态切换（其中 $i + m \leq n$）。例如，如果你在时间 19 开始前按下按钮 5，那么灯 5 将在时间 19 切换状态，灯 6 将在时间 20 切换状态，灯 7 将在时间 21 切换状态，依此类推。如果你按下的按钮导致某盏灯在某个时间步需要切换状态，而该灯在同一时间步由于之前按下的按钮也需要切换状态，那么这两次切换会相互抵消，并且后续的传播也会因此停止。 假设有三盏灯，初始全部熄灭。如果你在第一个时间步开始前按下第一个按钮，那么接下来三个时间步的变化如下： :::align{center}  ::: 现在，假设你在第一个时间步开始前按下第一个按钮，然后在第一个和第二个时间步之间按下第二个按钮。这次按钮按下会抵消传播，效果如下（注意传播不会继续延伸）： :::align{center}  ::: 再假设你在第一个时间步开始前按下第一个按钮，然后在第一个和第二个时间步之间按下第三个按钮。三盏灯在第二个时间步都会点亮（但第三个时间步不会）： :::align{center}  ::: 你希望让所有灯都亮起来。请问你最早能在什么时刻看到所有灯都亮着？注意，如果所有灯在时间 $t$ 是亮的，但由于传播在时间 $t+1$ 又不亮了，那么 $t$ 仍然是正确的答案。

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。每个测试用例包含一个字符串 $S$（$1 \leq |S| \leq 16$）。字符串 $S$ 仅包含字符 1 和 0，其中 1 表示该灯初始为亮，0 表示该灯初始为灭。第一个字符对应灯 1，第二个字符对应灯 2，依此类推。

输出一个整数，表示所有灯都亮起的最早时刻。

翻译由 DeepSeek V3.2 完成