Dotcpp  >  编程题库  >  [传智杯]特殊的翻转
题目 2316:

[传智杯]特殊的翻转

时间限制: 1s 内存限制: 128MB 提交: 212 解决: 34

题目描述

k 老师在研究一段病毒程序的代码。这段代码是由一段长度不超过 10^6106 的十六进制字符(也就是 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

样例输入

FF

样例输出

3

提示

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

标签