QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 2048 MB Total points: 100

#8062. 猜猜我是谁

Statistics

Guess Who 是一款双人棋盘游戏,其中多个角色通过一组属性(例如是否戴眼镜)进行唯一标识,每位玩家通过询问一系列“是/否”问题(例如“此人是否戴眼镜?”)来尝试猜出对方隐藏的角色。

在本游戏的变体中,共有 $N$ 个角色,每个角色由 $M$ 个属性唯一标识。每个属性的值要么是 YES,要么是 NO。你将获得一份角色及其属性的列表,以及一系列 $Q$ 个问题及其对应的回答。你的任务是尽可能确定隐藏的角色。

输入格式

输入的第一行包含三个空格分隔的整数 $N$、$M$ 和 $Q$,满足 $1 \le N \le 1000$,$1 \le M \le 15$ 以及 $1 \le Q \le M$。接下来的 $N$ 行,每行包含一个长度为 $M$ 的字符串,由字符 Y 或 N 组成。第 $i$ 行表示第 $i$ 个角色的 $M$ 个属性值。接下来的 $Q$ 行,每行包含一个整数 $1 \le A \le M$,后跟一个空格,再后跟一个字符 Y 或 N。这表示该问题是关于属性 $A$ 的,回答表示隐藏角色的该属性为 YES 或 NO。每个属性最多被询问一次。至少有一个列出的角色符合所有查询的回答。

输出格式

第一行输出 uniqueambiguous,表示隐藏角色是唯一可确定的,还是存在多个可能的隐藏角色。

如果隐藏角色是唯一可确定的,则在第二行输出该隐藏角色的索引(在 $1$ 到 $N$ 之间)。如果存在多个可能的隐藏角色,则在第二行输出可能隐藏角色的数量。

样例

样例输入 1

5 5 3
YYYYY
NNNNN
YNYNY
YYYNN
NNYYY
1 N
2 N
3 Y

样例输出 1

unique
5

样例输入 2

5 5 3
YYYYY
NNNNN
YNYNY
YYNNN
NNNYY
1 Y
5 Y
3 Y

样例输出 2

ambiguous
2

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.