算法练习专栏——Codeforces——Codeforces Round 942 (Div. 2)

A：Contest Proposal

Problem - A - Codeforces

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, \ldots, a_n$ and $b_1, b_2, \ldots, 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 \leq n \leq 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

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.

翻译

一个竞赛包含n 个问题，而第 i 个问题的难度预计最多bi 。现在已经有 n 个问题提案，而 i 个问题的难度是 ai 。最初，$a_1,a_2,…,a_n$ 和$b_1,b_2,…,b_n$ 都是按照不递减的顺序排列的。

有些问题可能比预期的更难，因此作者必须提出更多的问题。当提出难度为 $w$ 的新问题时，最难的问题将从竞赛中删除，问题将以难度不递减的方式排序。

换句话说，在每次操作中，你都要选择一个整数 $w$ ，将其插入数组 $a$ 中，对数组 $a$ 进行非递减排序，并从中删除最后一个元素。

求在所有 i$ 中，使得$a_i \le b_i$ 的最小新问题数。

输入

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

每个测试用例的第一行只包含一个正整数 $n$ ( $1 \leq n \leq 100$ )，表示问题的数量。

每个测试用例的第二行包含一个长度为 $n$ $(1\le a_1 \le a_2 \le … \le a_n) $ 的数组 $a$。

每个测试用例的第三行包含一个长度为 $n$ $(1\le b_1 \le b_2 \le … \le b_n)$ 的数组 $b$。

输出

对于每个测试用例，请在新行中打印一个整数作为答案。

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

注

在第一个测试案例中

• 提出难度为 $w=800$ 的问题， $a$ 变为 $[800,1000,1400,2000,2000,2200]$ 。
• 提出难度为 $w=1800$ 的问题， $a$ 变为 $[800,1000,1400,1800,2000,2000]$ 。

可以证明，提出更少的新问题是不可能达到目标的。

在第二个测试案例中

• 提出一个难度为 $w=1$ 的问题， $a$ 变为 $[1,4,5,6,7,8]$ 。
• 提出难度为 $w=2$ 的问题， $a$ 变为 $[1,2,4,5,6,7]$ 。
• 提出一个难度为 $w=3$ 的问题， $a$ 变为 $[1,2,3,4,5,6]$ 。

可以证明，提出更少的新问题是不可能达到目标的。

思路

代码

#include <iostream>
using namespace std;
const int N = 110;
int a[N], b[N];
 
int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= n; i++) cin >> b[i];
        int j = 1;
        for (int i = 1; i <= n; i++) {
            if (a[j] <= b[i]) {
                j++;
            }
        }
        cout << n - j + 1 << '\n';
    }



    return 0;
}

B：Coin Games

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 \leq n \leq 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

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.

翻译

桌子上有 $$n$$ 枚硬币围成一个圆圈，每枚硬币要么朝上，要么朝下。爱丽丝和鲍勃轮流玩下面的游戏，爱丽丝先玩。

在每次操作中，玩家选择一枚正面朝上的硬币，取出硬币并翻转与其相邻的两枚硬币。如果(操作前)只剩下两枚硬币，则取出一枚，另一枚不翻转(因为会翻转两次)。如果(操作前)只剩下一枚硬币，则不会翻转任何硬币。如果(操作前)没有正面朝上的硬币，玩家就输了。

如果两人都以最佳方式下棋，谁会赢呢？可以证明，游戏将在有限次的操作中结束，其中一人将获胜。

输入

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

每个测试用例的第一行只包含一个正整数 $n$ ( $1 \leq n \leq 100$ )，代表硬币的数量。

每个测试用例的第二行后面都有一个长度为 $n$ 的字符串 $s$ ，其中只包含 “U “和 “D”，代表每个硬币朝上或朝下。

输出

对于每个测试用例，如果 Alice 将赢得游戏，则打印 “YES”，否则打印 “NO”。

您可以用任何大小写(大写或小写)输出答案。例如，字符串 “yEs”、”yes”、”Yes “和 “YES “将被识别为肯定回答。

Example

input

3
5
UUDUD
5
UDDUD
2
UU

output

YES
NO
NO

注

在第一个测试案例中，游戏过程可能如下。

• 爱丽丝选择第一枚硬币， $s$ 变成 “DDUU”。
• 鲍勃选择最后一枚硬币， $s$ 变成 “UDD”。
• 爱丽丝选择第一枚硬币， $s$ 变成 “UU”。
• 鲍勃选择第一枚硬币， $s$ 变成 “U”。
• 爱丽丝选择了唯一一枚硬币， $s$ 变成了 “空”。
• 鲍勃现在不能选择任何一枚硬币，他输掉了游戏。

可以证明，如果两人都以最优方式下棋，鲍勃总是会输。

思路

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
int n;

int main()
{
    int t;
    cin >> t;
    while (t--) {
        int n, res = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            char c;
            cin >> c;
            if (c == 'U') res++;
        }
        if (res % 2 == 0) cout << "NO\n";
        else cout << "YES\n";
    }

    return 0;

}

C.：Permutation Counting

Problem - C - Codeforces

You have some cards. An integer between $1$ and $n$ is written on each card: specifically, for each $i$ from $1$ to $n$, you have $a_i$ cards which have the number $i$ written on them.

There is also a shop which contains unlimited cards of each type. You have $k$ coins, so you can buy $k$ new cards in total, and the cards you buy can contain any integer between $1$ and $n$.

After buying the new cards, you rearrange all your cards in a line. The score of a rearrangement is the number of (contiguous) subarrays of length $n$ which are a permutation of $[1, 2, \ldots, n]$. What’s the maximum score you can get?

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 two integers $n$, $k$ ($1\le n \le 2 \cdot 10^5$, $0\le k \le 10^{12}$) — the number of distinct types of cards and the number of coins.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{12}$) — the number of cards of type $i$ you have at the beginning.

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

Output

For each test case, output a single line containing an integer: the maximum score you can get.

Example

input

8
1 10
1
2 4
8 4
3 4
6 1 8
3 9
7 6 2
5 3
6 6 7 4 6
9 7
7 6 1 7 6 2 4 3 3
10 10
1 3 1 2 1 9 3 5 7 5
9 8
5 8 7 5 1 3 2 9 8

output

11
15
15
22
28
32
28
36

Note

In the first test case, the final (and only) array we can get is $[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$ (including $11$ single $1$s), which contains $11$ subarrays consisting of a permutation of $[1]$.

In the second test case, we can buy $0$ cards of type $1$ and $4$ cards of type $2$, and then we rearrange the cards as following: $[1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]$. There are $8$ subarrays equal to $[1, 2]$ and $7$ subarrays equal to $[2, 1]$, which make a total of $15$ subarrays which are a permutation of $[1, 2]$. It can also be proved that this is the maximum score we can get.

In the third test case, one of the possible optimal rearrangements is $[3, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 3]$.

翻译

你有几张牌。每张卡片上都写着一个介于 $1$ 和 $n$ 之间的整数：具体来说，从 $1$ 到 $n$ 的每张 $i$ ，你们的卡片。

还有一个商店，里面有无限量的各种类型的卡片。你有 $k$ 枚金币，因此你总共可以购买 $k$ 张新卡片，你购买的卡片可以包含 $1$ 到 $n$$ 之间的任意整数。

买完新牌后，你要将所有牌重新排列成一行。重新排列的得分是长度为 $n$ 的(连续)子数组的数量，这些子数组是 $[1, 2, \ldots, n]$ 的排列组合。你能得到的最高分是多少？

输出

对于每个测试用例，输出一行包含一个整数的数据：你能得到的最大分数。

输出

对于每个测试用例，输出一行包含一个整数的数据：你能得到的最大分数。

Example

input

8
1 10
1
2 4
8 4
3 4
6 1 8
3 9
7 6 2
5 3
6 6 7 4 6
9 7
7 6 1 7 6 2 4 3 3
10 10
1 3 1 2 1 9 3 5 7 5
9 8
5 8 7 5 1 3 2 9 8

output

11
15
15
22
28
32
28
36

思路

​ 本人思路：可以分析出来，将所有的数字按照1,2,3…n,1,2,3,…,n,1,2,….这样的顺序一致排列下去可以得到的排序的子数组种类最多（其实是我打表打出来的），然后就有了两种想法，可以每n个为一组，少则用k的补上，多的一些数字往后面加上即可，什么意思呢？比如说：现在有1,2,3,数字各7,6,2,个，k=5，那么排序下来是这样的，1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,1但是直接按照这种思路模拟就会很困难，我估计如果要使用这种思路来写这道题目可能要使用到树状数组了，然后还有蛮多的细节需要处理，因此我没写出来。

​ 之后的思路：使用贪心+二分的思想来写，这里的难点就是这个二分的点是什么，这里我们可以选择选取1~n这些数的组数来作为二分的目标，找到了最终的1,2,...,n的组数，而最后对于剩下多余的数字。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 2e5 + 10;
LL a[N];
LL n, k;

bool check(LL kk) {
    LL sum = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] >= kk) continue;
        else sum += kk - a[i];
        // cout << sum << ' ' << k << '\n';
        if (sum > k) return false;
    }
    return sum <= k;
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while (t--){
        LL sum = 0;
        cin >> n >> k;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum += a[i];
        }

        sort(a + 1, a + n + 1);
        LL l = a[1], r = 2e12 + 10;
        
        // 二分找到最大可能可以组成的1,2,3...,n的组数
        while(l < r){
            LL mid = l + r + 1 >> 1 ;
            if(check(mid)) l = mid;
            else r = mid - 1;
        }

        // cout << r << '\n';
        
        // 现在有 r 组 1 ~ n 的组合，那么就应该有 n (r - 1) + 1 组数据 
        LL ans = n * r - n + 1;


        LL checked = sum + k - 1LL * r * n;
        // 如果我们可以通过 k 购买数字可以刚刚好组成r组的话就直接输出ans即可。
        if (checked == 0) {
            cout << ans << '\n';
            continue;
        }
        // 组成目标组数之后看看还可以买多少张卡片
        for(int i = 1;i <= n;i++)
		{
            if(a[i] < r) k -= r - a[i];
        }
        
        // 现在直接从 n 往前枚举到 1 ，对于多余部分，只要有多余部分就可以 + 1，而最后如果 k = 0了同时卡片 i 也没有了，这样的话就结束了。

        // cout << ans << '\n';

        // 注意：这个地方可能有同学会有这样的疑惑：
        // 交错排序为：123123，但是还多出1个2，k = 2,这个时候我们可以排序成这个样子2132132，对于其他情况也是一样的，比如1234512345,多出来1个1，1个3和1个5，这时候我们就可以变为1352413524135这种模式。
        for (int i = n; i >= 1; i--) {
            if (a[i] > r) ans++;
            else if (k) {
                ans ++;
                k--;
            } else {
                break;
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

D1：Reverse Card (Easy Version)

The two versions are different problems. You may want to read both versions. You can make hacks only if both versions are solved.

You are given two positive integers $n$, $m$.

Calculate the number of ordered pairs $(a, b)$ satisfying the following conditions:

• $1\le a\le n$, $1\le b\le m$;
• $a+b$ is a multiple of $b \cdot \gcd(a,b)$.

Input

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

The first line of each test case contains two integers $n$, $m$ ($1\le n,m\le 2 \cdot 10^6$).

It is guaranteed that neither the sum of $n$ nor the sum of $m$ over all test cases exceeds $2 \cdot 10^6$.

Output

For each test case, print a single integer: the number of valid pairs.

Example

input

6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141

output

1
3
4
14
153
1643498

Note

In the first test case, only $(1,1)$ satisfies the conditions.

In the fourth test case, $(1,1),(2,1),(2,2),(3,1),(4,1),(5,1),(6,1),(6,2),(6,3),(7,1),(8,1),(9,1),(10,1),(10,2)$ satisfy the conditions.

翻译

两个版本的问题不同。您可能需要同时阅读两个版本。只有两个版本的问题都解决了，您才能进行破解。

给你两个正整数 $$n$ , $m$$ 。

计算满足以下条件的有序数对 $$(a, b)$$ 的个数：

• $1\le a\le n$ , $1\le b\le m$ ;
• $a+b$ 是 $b \cdot \gcd(a,b)$ 的倍数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1\le t\le 10^4$ )。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n$ , $m$ ( $1\le n,m\le 2 \cdot 10^6$ )。

保证所有测试用例中 $n$ 和 $m$ 的总和不超过 $2 \cdot 10^6$ 。

输出

为每个测试用例打印一个整数：有效配对的数量。

Example

input

6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141

output

1
3
4
14
153
1643498

注

在第一个测试案例中，只有 $(1,1)$ 满足条件。

在第四个测试用例中， $(1,1),(2,1),(2,2),(3,1),(4,1),(5,1),(6,1),(6,2),(6,3),(7,1),(8,1),(9,1),(10,1),(10,2)$ 满足条件。

思路

​ 这道题目是一道纯粹的数学公式推导类型题目，具体的推导过程请看代码部分。

代码

#include <iostream>
using namespace std;
typedef long long LL;


int main()
{
    int t;
    LL n, m;
    cin >> t;
    while (t--){
        LL ans = 0;
        cin >> n >> m;
        // (a + b) % (b * gcd(a, b)) == 0;
        // 所以知道 (a + b) % b == 0
        // a = kb;
        // 所有 gcd(a, b) = b;
        // (kb + b) % (b * b) == 0;
        // k = (b - 1, 2b - 1, 3b - 1, ...)
        // a = kb = (kk * b - 1) * b = kk * b ^ 2 - b <= n
        // kk <= (n + b) / b^2

        for (LL b = 1; b <= m; b++) {
            if (b == 1) ans += n;
            else {
                ans += (n + b) / (b * b);
            }
        }
        cout << ans << '\n'; 
    }
 

    return 0;
}

D2：Reverse Card (Hard Version)

两个版本的问题不同。您可能需要同时阅读两个版本。只有两个版本的问题都解决了，您才能进行破解。

给你两个正整数 $n$ ， $m$ 。

请计算满足下列条件的有序数对 $(a, b)$ 的个数：

• $1\le a\le n$ , $1\le b\le m$ ;
• $b \cdot \gcd(a,b)$ 是 $a+b$​ 的倍数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1\le t\le 10^4$ )。测试用例说明如下。

每个测试用例的第一行包含两个整数 $n$ 、 $m$ ( $1\le n,m\le 2 \cdot 10^6$ )。

保证所有测试用例中 $n$ 和 $m$ 的总和都不超过 $2 \cdot 10^6$ 。

输出

为每个测试用例打印一个整数：有效配对的数量。

Example

input

6
1 1
2 3
3 5
10 8
100 1233
1000000 1145141

output

0
1
1
6
423
5933961

注

在第一个测试案例中，没有一对符合条件。

在第四个测试用例中， $(2,2),(3,6),(4,4),(6,3),(6,6),(8,8)$ 满足条件。

代码

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long
typedef long long LL;
const int mod = 1e9+7;
const int N = 2e5+10;
using namespace std;
 
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
 
// 1 . b * gcd(a , b) % (a + b) == 0
// 2 . 设 g =  gcd(a,b) , 则 a=xg , b=yg ;   
// 3 . ==> gy * g = k * (gx + gy)
// 4 . ==> gy = k * (x + y);
// 5 . 由2可得 : x,y互质。那么y,x+y也互质
// 6 . ==> g = k * (x+y);
// 7 . ==> a=k*(x+y)*x,b=k*(x+y)*y ，满足a%x==0,b%y==0,gcd(x,y)==1  
 
inline void solve(){
	int a , b ; cin >> a >> b ;
	int ans = 0 ;
	for(int x=1;x<=a/x;x++){
		for(int y=1;y<=b/y;y++){
			if(gcd(x,y)==1){
				int cnt = min(a/((x+y)*x),b/((x+y)*y));
				if(cnt>=1) ans += cnt ;
			}
		}
	}	
	cout << ans << endl ;
}
 
signed main()
{
    IOS；
    int _ = 1;
    cin >> _;
    while(_ --) solve();
    return 0;
}