Codeforces 924比赛第2分区(ABCDE题)的视频教学解析

A. Rectangle Cutting

Problem Statement

Bob has a rectangle of size $a\times b$. He tries to cut this rectangle into two rectangles with integer sides by making a cut parallel to one of the sides of the original rectangle. Then Bob tries to form some other rectangle from the two resulting rectangles, and he can rotate and move these two rectangles as he wishes.

Note that if two rectangles differ only by a $90^{\circ }$ rotation, they are considered the same. For example, the rectangles $6\times 4$ and $4\times 6$ are considered the same.

Thus, from the $2\times 6$ rectangle, another rectangle can be formed, because it can be cut into two $2\times 3$ rectangles, and then these two rectangles can be used to form the $4\times 3$ rectangle, which is different from the $2\times 6$ rectangle.

However, from the $2\times 1$ rectangle, another rectangle cannot be formed, because it can only be cut into two rectangles of $1\times 1$, and from these, only the $1\times 2$ and $2\times 1$ rectangles can be formed, which are considered the same.

Help Bob determine if he can obtain some other rectangle, or if he is just wasting his time.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. This is followed by the description of the test cases.

The single line of each test case contains two integers $a$ and $b$ ($1\le a,b\le 10^9$) — the size of Bob’s rectangle.

Output

For each test case, output “Yes” if Bob can obtain another rectangle from the $a\times b$ rectangle. Otherwise, output “No”.

You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive answers.

Example

Example

input
7
1 1
2 1
2 6
3 2
2 2
2 4
6 3

output
No
No
Yes
Yes
Yes
Yes
No

Note

In the first test case, the $1\times 1$ rectangle cannot be cut into two rectangles, so another rectangle cannot be obtained from it.

In the fourth test case, the $3\times 2$ rectangle can be cut into two $3\times 1$ rectangles, and from these, the $1\times 6$ rectangle can be formed.

In the fifth test case, the $2\times 2$ rectangle can be cut into two $1\times 2$ rectangles, and from these, the $1\times 4$ rectangle can be formed.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

bool Check(int A1, int B1, int A2, int B2) { return (A1 == A2 && B1 == B2) || (A1 == B2 && B1 == A2); }

void solve()
{
	int A, B;

	cin >> A >> B;

	if ((A & 1) && (B & 1)) cout << "No" << endl;
	else
	{
		if ((A % 2 == 0) && !Check(A, B, A / 2, B * 2)) cout << "Yes" << endl;
		else if ((B % 2 == 0) && !Check(A, B, A * 2, B / 2)) cout << "Yes" << endl;
		else cout << "No" << endl;
	}
}

signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int Data;

	cin >> Data;

	while (Data --)
		solve();

	return 0;
}

---

B. Equalize

Problem Statement

Vasya has two hobbies — adding permutations${}^{†}$ to arrays and finding the most frequently occurring element. Recently, he found an array $a$ and decided to find out the maximum number of elements equal to the same number in the array $a$ that he can obtain after adding some permutation to the array $a$.

More formally, Vasya must choose exactly one permutation $p_1,p_2,p_3,\dots ,p_n$ of length $n$, and then change the elements of the array $a$ according to the rule $a_i:=a_i+p_i$. After that, Vasya counts how many times each number occurs in the array $a$ and takes the maximum of these values. You need to determine the maximum value he can obtain.

${}^{†}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 2\cdot 10^4$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output a single number — the maximum number of elements equal to the same number after the operation of adding a permutation.

Example

Example

input
7
2
1 2
4
7 1 4 1
3
103 102 104
5
1 101 1 100 1
5
1 10 100 1000 1
2
3 1
3
1000000000 999999997 999999999

output
2
2
3
2
1
1
2

Note

In the first test case, it is optimal to choose $p=[2,1]$. Then after applying the operation, the array $a$ will be $[3,3]$, in which the number $3$ occurs twice, so the answer is $2$.

In the second test case, one of the optimal options is $p=[2,3,1,4]$. After applying the operation, the array $a$ will be $[9,4,5,5]$. Since the number $5$ occurs twice, the answer is $2$