QOJ.ac

QOJ

时间限制: 1.0 s 内存限制: 512 MB 总分: 100

#9274. 饥饿的食人族

统计

有一群人,包括 $a$ 个食人族和 $b$ 个传教士,正准备一起旅行。他们面前有一条河,河边停着一艘小船。船很小,一次最多只能容纳两个人。此外,船上没有任何动力装置。移动船的唯一方法是使用船桨,这需要一定的技巧和体力。

已知在 $a$ 个食人族中只有 $x$ 个人会划船,在 $b$ 个传教士中只有 $y$ 个人会划船。为了将船从河的一岸划到另一岸,船上的乘客中至少要有一个人会划船。

如果食人族不寻求人肉,他们就不是食人族了。具体来说,如果河的同一岸(可能包括停靠的船)上有 $p$ 个食人族和 $q$ 个传教士,且满足 $p > q$ 且 $q > 0$,那么传教士就会成为食人族的晚餐,这在他们的旅程中是不可接受的。在其他情况下(即 $p \le q$ 或 $q = 0$),食人族会表现得像文明人一样,并遵循既定的转移计划。

考虑到所有这些限制,请判断是否存在一种方法将所有人安全地转移到河的另一岸。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 1000$),表示测试用例的数量。 接下来的每一行包含四个整数 $a, x, b, y$ ($0 \le a \le b \le 1000, 0 \le x \le a, 0 \le y \le b, a + b > 0$)。

输出格式

对于每个测试用例,如果能够将所有人安全地转移到河的另一岸,则输出 Yes,否则输出 No

样例

输入 1

4
2 0 2 1
1 1 4 0
2 1 2 0
3 1 3 1

输出 1

Yes
Yes
No
Yes

说明

在第一个测试用例中,将所有人转移到河对岸的一种可能方式如下:

  • 会划船的传教士占据船上的一个位置。
  • 他首先将一名食人族转移到对岸。此时河的起始岸上剩下一名传教士和一名食人族,船上也有一名传教士和一名食人族,因此没有人被吃掉。
  • 他将食人族留在对岸,然后返回起始岸。
  • 此时起始岸上有 2 名传教士和 1 名食人族,因此每个人仍然安全。
  • 他接上一名传教士并划船到对岸,将传教士留在那里。
  • 他返回,接上剩下的食人族,最后划船到对岸。

在第二个测试用例中,只有一个食人族,因此在任何情况下他都无法吃掉任何人。所以,任何将所有人转移到对岸的方法都是有效的。

在第三个测试用例中,无法避免两个食人族和一个传教士出现在河的同一岸的情况。

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.