Codeforces 第 942 轮（第 2 分部 ABCDE 问题）视频解析

A. Contest Proposal

Problem Statement

A contest contains $n$ problems and the difficulty of the $i$-th problem is expected to be at most $b_i$. There are already $n$ problem proposals and the difficulty of the $i$-th problem is $a_i$. Initially, both $a_1,a_2,\dots ,a_n$ and $b_1,b_2,\dots ,b_n$ are sorted in non-decreasing order.

Some of the problems may be more difficult than expected, so the writers must propose more problems. When a new problem with difficulty $w$ is proposed, the most difficult problem will be deleted from the contest, and the problems will be sorted in a way that the difficulties are non-decreasing.

In other words, in each operation, you choose an integer $w$, insert it into the array $a$, sort array $a$ in non-decreasing order, and remove the last element from it.

Find the minimum number of new problems to make $a_i\le b_i$ for all $i$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 100$). The description of the test cases follows.

The first line of each test case contains only one positive integer $n$ ($1\le n\le 100$), representing the number of problems.

The second line of each test case contains an array $a$ of length $n$ ($1\le a_1\le a_2\le \cdots \le a_n\le 10^9$).

The third line of each test case contains an array $b$ of length $n$ ($1\le b_1\le b_2\le \cdots \le b_n\le 10^9$).

Output

For each test case, print an integer as your answer in a new line.

Example

Example

input
2
6
1000 1400 2000 2000 2200 2700
800 1200 1500 1800 2200 3000
6
4 5 6 7 8 9
1 2 3 4 5 6

output
2
3

Note

In the first test case:

• Propose a problem with difficulty $w=800$ and $a$ becomes $[800,1000,1400,2000,2000,2200]$.
• Propose a problem with difficulty $w=1800$ and $a$ becomes $[800,1000,1400,1800,2000,2000]$.

It can be proved that it’s impossible to reach the goal by proposing fewer new problems.

In the second test case:

• Propose a problem with difficulty $w=1$ and $a$ becomes $[1,4,5,6,7,8]$.
• Propose a problem with difficulty $w=2$ and $a$ becomes $[1,2,4,5,6,7]$.
• Propose a problem with difficulty $w=3$ and $a$ becomes $[1,2,3,4,5,6]$.

It can be proved that it’s impossible to reach the goal by proposing fewer new problems.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

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

void solve() {
	int n;
	cin >> n;

	std::vector<int> a(n + 1), b(n + 1);
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= n; i ++)
		cin >> b[i];

	int res = 0;
	for (int i = 1, j = 1; i <= n; i ++) {
		while (i <= n && a[j] > b[i]) res ++, i ++;
		j ++;
	}

	cout << res << endl;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

B. Coin Games

Problem Statement

There are $n$ coins on the table forming a circle, and each coin is either facing up or facing down. Alice and Bob take turns to play the following game, and Alice goes first.

In each operation, the player chooses a facing-up coin, removes the coin, and flips the two coins that are adjacent to it. If (before the operation) there are only two coins left, then one will be removed and the other won’t be flipped (as it would be flipped twice). If (before the operation) there is only one coin left, no coins will be flipped. If (before the operation) there are no facing-up coins, the player loses.

Decide who will win the game if they both play optimally. It can be proved that the game will end in a finite number of operations, and one of them will win.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 100$). The description of the test cases follows.

The first line of each test case contains only one positive integer $n$ ($1\le n\le 100$), representing the number of the coins.

A string $s$ of length $n$ follows on the second line of each test case, containing only “U” and “D”, representing that each coin is facing up or facing down.

Output

For each test case, print “YES” if Alice will win the game, and “NO” otherwise.

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 responses.

Example

Example

input
3
5
UUDUD
5
UDDUD
2
UU

output
YES
NO
NO

Note

In the first test case, the game may go as follows.

• Alice chooses the first coin and $s$ becomes “DDUU”.
• Bob chooses the last coin and $s$ becomes “UDD”.
• Alice chooses the first coin and $s$ becomes “UU”.
• Bob chooses the first coin and $s$ becomes “U”.
• Alice chooses the only coin and $s$ becomes empty.
• Bob can’t choose any coin now, and he loses the game.

It can be proved that Bob will always lose if they both play optimally.

Solution

具体见文后视频。

---

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

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

void flip(char &tmp) {
	if (tmp == 'U') tmp = 'D';
	else tmp = 'U';
}

void solve() {
	int n;
	string s;
	cin >> n >> s;
	s = ' ' + s;

	int cpy = n;
	for (int i = 1; i <= cpy; i ++) {
		bool flg = 1;
		for (int j = 1; j <= n; j ++)
			if (s[j] == 'U') {
				if (j == 1) flip(s[n]);
				else flip(s[j - 1]);
				if (j == n) flip(s[1]);
				else flip(s[j + 1]);
				s.erase(s.begin() + j), n --;
				flg = 0;
				break;
			}
		if (flg) {
			if (i & 1) cout << "NO" << endl;
			else cout << "YES" << endl;
			return;
		}
	}
	if (cpy & 1) cout << "YES" << endl;
	else cout << "NO" << endl;
}

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

						

							上一篇：							
								LeetCode 解决问题 (0913)：猫和老鼠（Python）							
						
						

							下一篇：							
								世界*大师的设计法则 NO.7 "拟人化形式							
						
					
															

						

							推荐阅读						
						

														

								
									

										Codeforces 第 942 轮（第 2 分部 ABCDE 问题）视频解析									
								
							
														

								
									

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