#P18658. LaLa and Divination Magic
LaLa and Divination Magic
LaLa and Divination Magic
题目描述
LaLa 擅长占卜魔法。
她希望预测 个事件 。每个事件只有两种结果:灾难或救赎。
每施展一次占卜魔法,LaLa 会得到下面四种形式之一的知识:
- : 的结果是灾难,或者 的结果是灾难,也可能两者都是灾难。
- : 的结果是救赎,或者 的结果是灾难,也可能两者都成立。
- : 的结果是灾难,或者 的结果是救赎,也可能两者都成立。
- : 的结果是救赎,或者 的结果是救赎,也可能两者都是救赎。
LaLa 施展了若干次魔法,也可能一次都没有施展。她写下了与得到的所有知识同时相容的全部事件结果,也就是所有满足这些知识的 元组。这个集合称为占卜结果。然后,LaLa 睡着了。
醒来后,LaLa 发现她的宠物 Leo 弄坏了魔法所给出的预测。她找回了占卜结果,但不确定这些数据是否也被 Leo 弄坏了。
给定她找回的占卜结果,请判断是否存在一组知识,使其允许的所有结果恰好是给定集合;如果存在,输出任意一组这样的知识。
用二进制表示结果: 表示灾难, 表示救赎。注意,只让给定的每个结果都满足输出知识还不够;输出知识不能允许任何额外结果。
输入格式
输入一组数据。
第一行包含两个整数 ,分别表示找回的结果数量、事件数量。
接下来 行,每行是一个长度为 的二进制字符串 。其中第 个字符为 1 当且仅当该结果中事件 得到救赎。
数据范围
- 是整数,。
- 每个 的长度为 ,仅包含
0和1。 - 所有字符串两两不同。
- 事件下标从 到 。
输出格式
如果不存在符合要求的知识集合,输出一个整数 。
否则,第一行输出一个整数 ,表示知识数量;接下来 行,每行输出三个整数 ,表示一条知识 。
要求 ,事件下标在 内,知识类型在 内。两个事件下标可以相同。可以证明,只要存在符合要求的知识集合,就存在一组满足上述数量限制的知识。
答案可能不唯一,输出任意一组即可。 表示没有任何知识约束。
样例输入 1
2 1
1
0
样例输出 1
0
样例输入 2
3 3
101
011
111
样例输出 2
6
0 2 3
0 1 4
0 2 4
1 2 3
1 2 4
2 2 4