#P4796. [CERC2016]Key Knocking
[CERC2016]Key Knocking
[CERC2016] 敲击密钥 Key Knocking
题目描述
Goran 在做膝盖手术后的康复期间,研究了一种储存加密密钥的智能卡。密钥是一个长度为 的二进制串,位的编号从左到右为 至 。密钥的权值等于相邻且不同的二进制位对数加 。例如,000 的权值为 ,011010100 的权值为 。
Goran 发现通过给智能卡电路施加短脉冲,可以同时翻转任意两个相邻的位。翻转把 0 改为 1,把 1 改为 0。例如,可以把 000 在一步内变成 110。
给定初始密钥,找出任意一种至多使用 步的方案,使密钥的权值达到至少 。保证有解。
输入格式
一行一个长度为 的二进制串,表示初始密钥。
输出格式
第一行一个整数 ,表示操作次数,。
第二行按执行顺序给出 个整数 。第 步翻转第 位和第 位,因此 。
若初始密钥的权值已至少为 ,可以只输出 0。
数据范围
。
样例 #1
样例输入 #1
000000000
样例输出 #1
3
2 5 6
样例 #2
样例输入 #2
111001000111
样例输出 #2
2
3 9
样例 #3
样例输入 #3
010101
样例输出 #3
0