QOJ.ac

QOJ

実行時間制限: 1.0 s メモリ制限: 256 MB 満点: 100 ハック可能 ✓

#6785. 你们是什么样的朋友?

統計

加帕里公园(Japari Park)是一个巨大的动物园,栖息着现存物种、濒危物种、已灭绝物种、神秘生物以及一些传说中的生物。由于一种被称为“砂之星”(Sandstar)的神秘物质,所有的动物都拟人化成了被称为“朋友”(Friends)的女孩。

小鞄(Kaban)是一个发现自己身处加帕里公园的年轻女孩,她不记得自己是谁,也不记得从哪里来。她虽然害羞但足智多谋,在薮猫(Serval)的陪伴下穿过加帕里公园寻找自己的身份,途中遇到了更多的“朋友”,最终发现自己是人类。

然而,小鞄很快发现识别其他的“朋友”也很重要。她的朋友薮猫启发小鞄,可以使用一些预期答案为“是”(yes)或“否”(no)的问题来识别一种“朋友”。

具体来说,有 $n$ 个“朋友”需要被识别。小鞄会问她们每个人 $q$ 个相同的问题并收集答案。对于每个问题,她还会得到一份会回答“是”的动物名单(不在名单上的动物对该问题会回答“否”),因此可以通过结合答案和名单来确定一个“朋友”的名字。

但这项工作对小鞄来说太繁重了。你能帮她完成吗?

输入格式

输入包含多组测试数据。第一行是一个整数 $T$ ($1 \le T \le 100$),表示测试数据的组数。接下来是 $T$ 组测试数据。

每组测试数据的第一行包含两个整数 $n$ ($1 \le n \le 100$) 和 $q$ ($1 \le q \le 21$),分别表示需要识别的“朋友”数量和问题的数量。

下一行包含一个整数 $c$ ($1 \le c \le 200$),随后是 $c$ 个字符串 $p_1, p_2, \dots, p_c$ ($1 \le |p_i| \le 20$),表示所有已知的“朋友”名字。

接下来的 $q$ 行中,第 $i$ 行包含一个整数 $m_i$ ($0 \le m_i \le c$),随后是 $m_i$ 个字符串 $s_{i,1}, s_{i,2}, \dots, s_{i,m_i}$ ($1 \le |s_{i,j}| \le 20$),表示对第 $i$ 个问题回答“是”的“朋友”数量及其名字。保证所有名字均出现在已知的“朋友”名字中。

接下来的 $n$ 行中,第 $i$ 行包含 $q$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,q}$ ($0 \le a_{i,j} \le 1$),表示需要识别的第 $i$ 个“朋友”对第 $j$ 个问题的回答(0 表示“否”,1 表示“是”)。

保证输入中所有的名字仅由大小写英文字母组成。

输出格式

对于每组测试数据,输出 $n$ 行。如果小鞄能确定需要识别的第 $i$ 个“朋友”的名字,则在第 $i$ 行打印该名字。否则,在第 $i$ 行打印 “Let’s go to the library!!” (不含引号)。

样例

样例输入 1

2
3 4
5 Serval Raccoon Fennec Alpaca Moose
4 Serval Raccoon Alpaca Moose
1 Serval
1 Fennec
1 Serval
1 1 0 1
0 0 0 0
1 0 0 0
5 5
11 A B C D E F G H I J K
3 A B K
4 A B D E
5 A B K D E
10 A B K D E F G H I J
4 B D E K
0 0 1 1 1
1 0 1 0 1
1 1 1 1 1
0 0 1 0 1
1 0 1 1 1

样例输出 1

Serval
Let’s go to the library!!
Let’s go to the library!!
Let’s go to the library!!
Let’s go to the library!!
B
Let’s go to the library!!
K

说明

第一组测试数据的解释如下:

由于薮猫(Serval)是唯一已知对第 1、2 和 4 个问题回答“是”,且对第 3 个问题回答“否”的动物,因此我们在第一行输出 “Serval”。

由于没有已知的动物对所有问题都回答“否”,我们在第二行输出 “Let’s go to the library!!”。

羊驼(Alpaca)和驼鹿(Moose)都对第 1 个问题回答“是”,且对第 2、3 和 4 个问题回答“否”。因此我们无法确定需要识别的第三个“朋友”的名字,在第三行输出 “Let’s go to the library!!”。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.