題目 2316:
[傳智杯]特殊的翻轉(zhuǎn)
時間限制: 2s
內(nèi)存限制: 192MB 提交: 217 解決: 35
題目描述
k 老師在研究一段病毒程序的代碼。這段代碼是由一段長度不超過 10^6106 的十六進制字符（也就是 0 到 9 和 A 到 F）組成的信息?，F(xiàn)在 k 老師要將其轉(zhuǎn)換為二進制的 0/1 串（這個時候需要確保最高位是 1）。然后對這個 0/1 串進行“翻轉(zhuǎn)”操作。
對于每次“翻轉(zhuǎn)”操作，k 老師可以選擇這個 0/1 串中的其中一位，將這一位和這一位相鄰的兩位，一共三位，分別進行“翻轉(zhuǎn)”（也就是 0 變 1，1 變 0）。如果指定的這一位是序列的開頭或者結(jié)尾，那么翻轉(zhuǎn)這一位和存在的相鄰位即可。
k 老師想知道，如何用最少的“翻轉(zhuǎn)”步驟，將這個 0/1 串變?yōu)槿?0 的串。
輸入格式
一個十六進制的字符串，由 0 到 9 和 A 到 F 構(gòu)成。
輸出格式
最少能將其變?yōu)槿?0 串需要的“翻轉(zhuǎn)”步驟次數(shù)。如果無論如何都不能將其變?yōu)槿?0 串，則輸出 No。
提示
十六進制的 15 對應(yīng)二進制的 10101，翻轉(zhuǎn)第 1/3/5 位，就可以全部變?yōu)?0。
十六進制的 FF 對應(yīng)二進制的 11111111，翻轉(zhuǎn)第 2/5/8 位，就可以全部變?yōu)?0。
十六進制的 10 對應(yīng)二進制的 10000，無法全變?yōu)?0。