#P2447. [SDOI2010] 外星千足虫

    ID: 1455 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2010各省省选山东概率论统计高斯消元位运算按位

[SDOI2010] 外星千足虫

题目描述

公元 233323332233 日,在经历了 1717 年零 33 个月的漫长旅行后,“格纳格鲁一号”载人火箭返回舱终于安全着陆。此枚火箭由美国国家航空航天局(NASA)研制发射,行经火星、金星、土卫六、木卫二、谷神星、“张衡星”等 2323 颗太阳系星球,并最终在小行星“杰森星”探寻到了地外生命。宇航员在“杰森星”地表岩层下 45.7045.70 米位置发现一批珍贵的活体生命样本,并将其带回检测。

在带回的活体样本中,最吸引人的当属这些来自外星的千足虫了。这些虫子身躯纤长,身体分为若干节。受到触碰时,会将身体卷曲成圆环形,间隔一段时间后才会复原活动。

有趣的还不止如此。研究人员发现,这些虫子的足并不像地球千足虫成对出现、总共偶数条——它们每节身体下方都有着不定数量的足,但足的总数一定是奇数条!

虽然从外观难以区分二者,但通过统计足的数目,科学家们就能根据奇偶性判断出千足虫所属的星球。

作为 J 国派去 NASA 的秘密间谍,你希望参加这次研究活动以掌握进一步的情报,而 NASA 选拔的研究人员都是最优秀的科学家。于是 NASA 局长 Charles Bolden 出了一道难题来检测你的实力:

现在你面前摆有 1N1\ldots N 编号的 NN 只千足虫,你的任务是鉴定每只虫子所属的星球,但不允许亲自去数它们的足。

Charles 每次会在这 NN 只千足虫中选定若干只放入“昆虫点足机”(the Insect Feet Counter, IFC)中,“点足机”会自动统计出其内所有昆虫足数之和。Charles 会将这个和数 mod\bmod 22 的结果反馈给你,同时告诉你一开始放入机器中的是哪几只虫子。

他的这种统计操作总共进行 MM 次,而你应当尽早得出鉴定结果。

假如在第 KK 次统计结束后,现有数据就足以确定每只虫子的身份,你就还应将这个 KK 反馈给 Charles,此时若 K<MK<M,则表明那后 MKM-K 次统计并非必须的。

如果根据所有 MM 次统计数据还是无法确定每只虫子身份,你也要跟 Charles 讲明:就目前数据会存在多个解。

输入格式

第一行是两个正整数 N,MN,M

接下来 MM 行,按顺序给出 Charles 这 MM 次使用“点足机”的统计结果。每行包含一个 0101 串和一个数字,用一个空格隔开。0101 串按位依次表示每只虫子是否被放入机器:如果第 ii 个字符是 00 则代表编号为 ii 的虫子未被放入,11 则代表已被放入。后面跟的数字是统计的昆虫足数 mod\bmod 22 的结果。

由于 NASA 的实验机器精确无误,保证前后数据不会自相矛盾。即给定数据一定有解。

输出格式

在给定数据存在唯一解时有 N+1N+1 行,第一行输出一个不超过 MM 的正整数 KK,表明在第 KK 次统计结束后就可以确定唯一解;接下来N行依次回答每只千足虫的身份,若是奇数条足则输出 ?y7M#(火星文),偶数条足输出 Earth

如果输入数据存在多解,输出 Cannot Determine

3 5
011 1
110 1
101 0
111 1
010 1
4
Earth
?y7M#
Earth
5 7
01100 1
11000 1
10100 0
11100 1
00011 1
00000 0
11111 0
Cannot Determine

提示

评分标准

对于每一个测试点,如果你的输出文件与答案文件完全相同,该测试点得满分。

否则,对于存在唯一解的测试点,如果你正确回答所有千足虫的身份,将得到 50%50\% 的分数;

其他情况,该测试点得零分。

数据规模和约定

对于 20%20\% 的数据,满足 N=M20N=M\leq 20

对于 40%40\% 的数据,满足 N=M500N=M\leq 500

对于 70%70\% 的数据,满足 N500N\leq500M103M\leq 10^3

对于 100%100\% 的数据,满足 1N1031\leq N\leq 10^31M2×1031\leq M\leq 2\times 10^3