[传智杯 #2 初赛] 特殊的翻转

题目描述

k 老师在研究一段病毒程序的代码。这段代码是由一段长度不超过 $10^6$ 的十六进制字符(也就是 `0` 到 `9` 和 `A` 到 `F`)组成的信息。现在 k 老师要将其转换为二进制的 0/1 串(这个时候需要确保最高位是 1)。然后对这个 0/1 串进行“翻转”操作。 对于每次“翻转”操作,k 老师可以选择这个 0/1 串中的其中一位,将这一位和这一位相邻的两位,一共三位,分别进行“翻转”(也就是 0 变 1,1 变 0)。如果指定的这一位是序列的开头或者结尾,那么翻转这一位和存在的相邻位即可。 k 老师想知道,如何用最少的“翻转”步骤,将这个 0/1 串变为全 0 的串。

输入输出格式

输入格式


一个十六进制的字符串,由 `0` 到 `9` 和 `A` 到 `F` 构成。

输出格式


最少能将其变为全 0 串需要的“翻转”步骤次数。如果无论如何都不能将其变为全 0 串,则输出 `No`。

输入输出样例

输入样例 #1

15

输出样例 #1

3

输入样例 #2

FF

输出样例 #2

3

输入样例 #3

10

输出样例 #3

No

说明

样例解释: 十六进制的 15 对应二进制的 10101,翻转第 1/3/5 位,就可以全部变为 0。 十六进制的 FF 对应二进制的 11111111,翻转第 2/5/8 位,就可以全部变为 0。 十六进制的 10 对应二进制的 10000,无法全变为 0。