题目解释

题目要求我们将一个用十六进制数表示的二进制序列（长度为 $n$ 的 $01$ 字符串）通过左右平移一个相同的字符串，用其中的 $1$ 覆盖掉原字符串中的 $0$，从而使原字符串变成全 $1$。输入包含一个整数 $n$（表示二进制字符串的长度）和多个十六进制数（用空格分隔，表示这个 $01$ 字符串的内容）。要求输出能使字符串变为全 $1$ 的所有平移方案，方案应优先输出右移，且每个方向只需输出移动次数最少的方案。如果无法完成覆盖，输出 $0$。

思路:

先将十六进制转成二进制，然后要么往左移动若干位，要么往右移动若干位。枚举这两种情况即可。注意二进制可能很大，无法直接使用内置int或者long类型。C++需要使用bitset,python直接使用内置的大整数。Java需要手写bitset.

题解

题目内容

小明突然收到一封信，里面有一个一个十六进制数，信里提到，这个十六进制数表示一个长度为 $n$ 的 $01$ 字符串。

信中写道，你能否通过左右移动一个和该$01$字符串相同的字符串，来用$1$覆盖掉原字符串中的$0$（$0$ 并不会覆盖 $1$），使得原字符串变成一个长度为 $n$ 的全 $1$ 字符串。如果可以请将方案写出，如果同时存在多个方案，请写下移动次数最少的方案。

小明一直在思考这个问题该如何解决，你能帮助小明解决这个问题吗？

输入描述

输入第一行为 $01$ 字符串的长度 $n$ 。（ $10\le n\le 1024$ ）

输入第二行为 $n$ 个bit的序列，用双字节十六进制数表示，如果 $n$ 超过 $16$ ，则用多个双字节十六进制表示，它们之间用空格分割。

有效bit从第一个十六进制的最高位开始计算，序列尾部如果有无效bit则用 $1$ 填充。

输出描述

输出第一行为可以变化为全 $1$ 字符串的方案个数，同一个方向只需要给出移位最少的方案。如果无法变为全 $1$ 字符串，则输出 $0$ 。

输出从第二行开始，每两行为一组。

第一行为平移方向和平移的次数，用 +X 表示向右为 + ，向左为 - ;

第二行为一个长度为 $n$ 的 $01$ 字符串，表示移动后字符串中哪些位置的 $1$ 将覆盖原始位置的 $0$ ；

如果存在多个方案，先输出向右移动的方案

样例

样例一

输入

13
0xEEEE

输出

2
+1
0010001000100
-1
0000100010001

样例解释

输入的十六进制数为:0xEEEE , 二进制为1110111011101110 , 截取$n=13$ 得到1110111011101

肉眼观察可以发现有两种方案，分别是右移 $1$ 个位置和左移 $1$ 个位置。对应的 $01$ 连续字符序列表示移动后字符串中哪些位置的 $1$ 将覆盖原始位置的 $0$ 。

样例二

输入

20
0xEEEF 0x3FFF

输出

2
+2
01000100010000110000
-2
00000100010001000011

样例解释

输入的十六进制数 0xEEEF 0x3FFF，截取前$n=20$位，转换为二进制序列为 11101110111011110011 ；

肉眼观察可以发现有两种方案，左移 $2$ 个位置 和 右移两个位置 。 对应的 $01$ 连续字符序列表示移动后字符串中哪些位置的 $1$ 将覆盖原始位置的 $0$ 。