CF1826C.Dreaming of Freedom

普及-

通过率:0%

时间限制:2.50s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Because to take away a man's freedom of choice, even his freedom to make the wrong choice, is to manipulate him as though he were a puppet and not a person.

— Madeleine L'Engle

There are nn programmers choosing their favorite algorithm amongst mm different choice options. Before the first round, all mm options are available. In each round, every programmer makes a vote for one of the remaining algorithms. After the round, only the algorithms with the maximum number of votes remain. The voting process ends when there is only one option left. Determine whether the voting process can continue indefinitely or no matter how people vote, they will eventually choose a single option after some finite amount of rounds?

因为剥夺一个人的选择自由——哪怕是犯错的自由——就等于将他当作提线木偶而非有自主意识的人来操控。

——玛德琳·英格尔

有 nn 名程序员要在 mm 种不同的算法选项中选出自己最喜爱的算法。在第一轮开始前,全部 mm 种选项均可用。每一轮中,每名程序员需从当前剩余的算法中投一票。本轮结束后,仅保留得票数最多的那些算法(即所有得票数等于该轮最高票数的算法)。投票过程持续进行,直至仅剩一种算法为止。请判断:该投票过程是否可能无限进行下去?还是说,无论程序员如何投票,最终总会在有限轮次后确定唯一胜出的算法?

输入格式

The first line contains a single integer tt (1≤t≤1051 \leq t \leq 10^5) — the number of test cases.

Each test case consists of a single line containing two integers nn and mm (1≤n,m≤1061 \leq n, m \leq 10^6) — the number of people and choice options respectively.

第一行包含一个整数 tt(1≤t≤1051 \leq t \leq 10^5)—— 测试用例的数量。

每个测试用例由一行组成,包含两个整数 nn 和 mm(1≤n,m≤1061 \leq n, m \leq 10^6)—— 分别表示人数和选择项的数量。

输出格式

For each test case output "YES" if the programmers will eventually choose a single option, and "NO" otherwise.

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as a positive answer).

对于每个测试用例,如果程序员最终会选定唯一一个选项,则输出 “YES”;否则输出 “NO”。

你可以以任意大小写形式输出每个字母(例如,YES、Yes、yes、yEs 均会被识别为肯定回答)。

输入输出样例

  • 输入#1

    5
    3 2
    4 2
    5 3
    1000000 1000000
    1 1000000

    输出#1

    YES
    NO
    YES
    NO
    YES

说明/提示

In the first example, there are 88 ways people could vote: 1∣1∣1,1∣1∣2,1∣2∣1,1∣2∣2,2∣1∣1,2∣1∣2,2∣2∣1,2∣2∣2{1|1|1, 1|1|2, 1|2|1, 1|2|2, 2|1|1, 2|1|2, 2|2|1, 2|2|2}.

In cases 11, 22, 33, and 55, the programmers are left with the first algorithm, and in the remaining cases people are left with the second one, so the voting ends in one round in any case.

In the second example, the programmers could always vote 1∣1∣2∣21|1|2|2. Both algorithms have the maximum number of votes and remain for the next round, so the voting never ends.

在第一个例子中,人们投票的方式共有 88 种:1∣1∣1,1∣1∣2,1∣2∣1,1∣2∣2,2∣1∣1,2∣1∣2,2∣2∣1,2∣2∣2{1|1|1, 1|1|2, 1|2|1, 1|2|2, 2|1|1, 2|1|2, 2|2|1, 2|2|2}。

在情况 11、22、33 和 55 中,程序员最终保留第一个算法;而在其余情况下,人们最终保留第二个算法,因此投票总能在一轮内结束。

在第二个例子中,程序员始终可以投票为 1∣1∣2∣21|1|2|2。此时两种算法获得的票数均为最大值,均进入下一轮,因此投票永远不会结束。

输入解题思路,AI测评打分。不知道怎么写?

首页