← 返回题目列表

Codeforces · 1863/A

A. 通道

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

Petya 是其中一位即时通讯工具的频道管理员。共有 $$$n$$$ 人订阅了他的频道,Petya 不被视为订阅者。

Petya 在频道上发布了一篇新帖子。截至本文发布时,在线订户数量为 $$$a$$$。我们假设每个订阅者在线时都会阅读频道中的所有帖子。

此后,Petya 开始监控在线订阅者数量。他连续收到“订户离线”或“订户上线”形式的$$$q$$$通知。 Petya 不知道具体哪个订阅者上线或离线。保证确实可以接收到这样的通知序列。

Petya 想知道他的所有订阅者是否都阅读了这篇新帖子。通过确定以下其中一项来帮助他:

- 不可能所有 $$$n$$$ 订阅者都阅读了该帖子;
- 可能所有 $$$n$$$ 订阅者都已阅读该帖子;
- 保证所有 $$$n$$$ 订阅者都已阅读该帖子。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 500$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$a$$$ 和 $$$q$$$ ($$$1 \le n \le 100$$$, $$$0 \le a \le n$$$, $$$1 \le q \le 100$$$) — 频道的订阅者数量、初始在线订阅者数量和数量的通知。

每个测试用例的第二行包含一个长度为 $$$q$$$ 的字符串,由字符“+”和“-”组成。如果第 $$$i$$$ 通知告知订阅者上线,则这些字符中的第 $$$i$$$ 为“+”,否则为“-”。

输出

对于每个测试用例,输出一行:如果保证所有 $$$n$$$ 订阅者都已阅读该帖子,则输出“YES”;如果不可能所有 $$$n$$$ 订阅者都已阅读该帖子,则输出“NO”;否则输出“MAYBE”。

示例

输入 #1

4
5 5 3
--+
5 2 3
++-
5 4 2
-+
5 0 7
++++-++

输出 #1

YES
NO
MAYBE
YES

注意

在第一个测试用例中,一开始就有 $$$5$$$ 订阅者在线,所以 $$$5$$$ 订阅者无论如何都会阅读该帖子。答案是“是”。

在第二个测试用例中,在前两次通知后,在线订阅者数量变为 $$$4$$$,接下来有人离线,因此第五个订阅者没有机会阅读该帖子。所有订阅者都不可能阅读该帖子,因此答案是否定的。

在第三个测试用例中,一方面,同一个人可能同时离线和上线(在这种情况下,$$$5$$$ 订阅者中只有 $$$4$$$ 阅读了该帖子),另一方面,最后的通知可能告诉第五个订阅者已上线(在这种情况下,所有订阅者都已阅读该帖子)。我们无法推断出这两个中哪一个成立,所以答案是“也许”。

在第四个测试用例中,所有通知后必须有五个订阅者在线。他们都会阅读这篇文章,所以答案是“是”。