← 返回题目列表

Codeforces · 1510/B

B. 按钮锁

中文机器翻译题面 查看原题

你正站在拥有巨大宝藏的房间前面。唯一阻止你的是带有按钮密码锁的门。该锁有 $$$d$$$ 按钮,数字从 $$$0$$$ 到 $$$d - 1$$$。每当您按下按钮时,它都会保持按下状态。您不能只弹出一个按钮,但有一个“重置”按钮 - 按下它会弹出所有其他按钮。最初,没有按钮被按下。

当按下某些特定的数字组时,门会立即打开。遗憾的是,您不知道它的密码。阅读此特定锁的文档后,您发现此特定锁有 $$$n$$$ 可能的密码。

找到最短的按钮按下顺序,使得所有可能的密码在执行过程中至少出现一次。任何最短的正确按钮按下顺序都将被接受。

输入

第一行包含两个整数 $$$d$$$ 和 $$$n$$$ ($$$1 \le d \le 10$$$; $$$1 \le n \le 2^d - 1$$$)。接下来的 $$$n$$$ 行描述可能的密码。每行包含一个由 $$$d$$$ 个零和一个组成的字符串 $$$s_i$$$:对于从 $$$1$$$ 到 $$$d$$$ 的所有 $$$j$$$,第 $$$j$$$ 个字符是 1 iff 必须按下带有数字 $$$j - 1$$$ 的按钮。

所有字符串$$$s_i$$$都不同,并且每个字符串至少包含一个 1.

输出

在第一行,打印数字 $$$k$$$ — 按下按钮的最少次数。在第二行,打印 $$$k$$$ 标记,描述序列。每当您按下带有数字的按钮时,都会打印该数字。每当您按“RESET”时,都会打印“R".

示例

输入
复制

2 2
10
11

输出
复制

2
0 1 

输入
复制

3 4
001
111
101
011

输出
复制

6
2 0 R 1 2 0 

注意

在第二个示例中,序列 1 2 R 2 0 1 也是可能的。