310018: CF1772G. Gaining Rating
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Gaining Rating
题意翻译
给你 $n$ 个人，每个人有一个能力值 $a_i$ 你的能力值最开始从 $x$ 开始，目标是到 $y$。如果你打赢了一个能力值小于等于你的人，那么你的能力值 $+1$，反之 $-1$。问你在尽可能平均的情况下，也就是如果你要打 $i$ 那么不应该存在一个 $j$ 使得打 $i$ 的场次比打 $j$ 的场次多。求最少场次，或者判断无解。题目描述
Monocarp is playing chess on one popular website. He has $ n $ opponents he can play with. The $ i $ -th opponent has rating equal to $ a_i $ . Monocarp's initial rating is $ x $ . Monocarp wants to raise his rating to the value $ y $ ( $ y > x $ ). When Monocarp is playing against one of the opponents, he will win if his current rating is bigger or equal to the opponent's rating. If Monocarp wins, his rating is increased by $ 1 $ , otherwise it is decreased by $ 1 $ . The rating of his opponent does not change. Monocarp wants to gain rating $ y $ playing as few games as possible. But he can't just grind it, playing against weak opponents. The website has a rule that you should play against all opponents as evenly as possible. Speaking formally, if Monocarp wants to play against an opponent $ i $ , there should be no other opponent $ j $ such that Monocarp has played more games against $ i $ than against $ j $ . Calculate the minimum possible number of games Monocarp needs to gain rating $ y $ or say it's impossible. Note that ratings of Monocarp's opponents don't change, while Monocarp's rating does change.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains three integers $ n $ , $ x $ and $ y $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le x < y \le 10^{12} $ ) — the number of Monocarp's opponents, his initial and desired ratings. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{12} $ ) — ratings of Monocarp's opponents. Additional constraint on the input: the total sum of $ n $ over all $ t $ test cases doesn't exceed $ 2 \cdot 10^5 $ .
输出格式
For each test case, print a single integer — the minimum number of games Monocarp needs to play to gain rating $ y $ , or $ -1 $ if it's impossible.
输入输出样例
输入样例 #1
3
7 2 10
3 1 9 2 5 20 8
7 1 10
3 1 9 2 5 20 8
5 10 12
100 1 200 11 300输出样例 #1
20
-1
2说明
In the first test case, Monocarp can use the following strategy: 1. Monocarp plays against the $ 2 $ -nd opponent to increase rating ( $ 2 \to 3 $ ); 2. Monocarp plays against the $ 1 $ -st opponent to increase rating ( $ 3 \to 4 $ ); 3. Monocarp plays against the $ 4 $ -th opponent to increase rating ( $ 4 \to 5 $ ); 4. Monocarp plays against the $ 5 $ -th opponent to increase rating ( $ 5 \to 6 $ ); 5. Now Monocarp have to play with remaining three opponents. So, he will lose $ 3 $ times and get rating $ 3 $ ( $ 6 \to 5 \to 4 \to 3 $ ); 6. After that, Monocarp will repeat steps 1-5 again. After $ 14 $ games, he has played twice with each opponent and get final rating $ 4 $ . 7. Monocarp plays against the $ 1 $ -st opponent to increase rating ( $ 4 \to 5 $ ); 8. Monocarp plays against the $ 2 $ -nd opponent to increase rating ( $ 5 \to 6 $ ); 9. Monocarp plays against the $ 4 $ -th opponent to increase rating ( $ 6 \to 7 $ ); 10. Monocarp plays against the $ 5 $ -th opponent to increase rating ( $ 7 \to 8 $ ); 11. Monocarp plays against the $ 7 $ -th opponent to increase rating ( $ 8 \to 9 $ ); 12. Monocarp plays against the $ 3 $ -rd opponent to increase rating ( $ 9 \to 10 $ ); In total, Monocarp, played twice against the $ 6 $ -th opponent and three times against other opponents and got rating $ 10 $ in $ 14 + 6 = 20 $ games.In the second test case, it can be proven that whichever games Monocarp plays, he can't get his rating higher than $ 4 $ .Input
题意翻译
给你 $n$ 个人，每个人有一个能力值 $a_i$ 你的能力值最开始从 $x$ 开始，目标是到 $y$。如果你打赢了一个能力值小于等于你的人，那么你的能力值 $+1$，反之 $-1$。问你在尽可能平均的情况下，也就是如果你要打 $i$ 那么不应该存在一个 $j$ 使得打 $i$ 的场次比打 $j$ 的场次多。求最少场次，或者判断无解。Output
**题意翻译**
给你 $n$ 个人，每个人有一个能力值 $a_i$，你的能力值最开始从 $x$ 开始，目标是到 $y$。如果你打赢了一个能力值小于等于你的人，那么你的能力值 $+1$，反之 $-1$。问你在尽可能平均的情况下，也就是如果你要打 $i$ 那么不应该存在一个 $j$ 使得打 $i$ 的场次比打 $j$ 的场次多。求最少场次，或者判断无解。
**题目描述**
Monocarp is playing chess on one popular website. He has $ n $ opponents he can play with. The $ i $-th opponent has rating equal to $ a_i $. Monocarp's initial rating is $ x $. Monocarp wants to raise his rating to the value $ y $ ( $ y > x $ ).
When Monocarp is playing against one of the opponents, he will win if his current rating is bigger or equal to the opponent's rating. If Monocarp wins, his rating is increased by $ 1 $, otherwise it is decreased by $ 1 $. The rating of his opponent does not change.
Monocarp wants to gain rating $ y $ playing as few games as possible. But he can't just grind it, playing against weak opponents. The website has a rule that you should play against all opponents as evenly as possible. Speaking formally, if Monocarp wants to play against an opponent $ i $, there should be no other opponent $ j $ such that Monocarp has played more games against $ i $ than against $ j $.
Calculate the minimum possible number of games Monocarp needs to gain rating $ y $ or say it's impossible. Note that ratings of Monocarp's opponents don't change, while Monocarp's rating does change.
**输入输出格式**
**输入格式**
第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) —— 测试用例的数量。
每个测试用例的第一行包含三个整数 $ n $, $ x $ 和 $ y $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le x < y \le 10^{12} $ ) —— Monocarp的对手数量，他的初始评分和期望评分。
第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{12} $ ) —— Monocarp的对手的评分。
输入的额外限制：所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。
**输出格式**
对于每个测试用例，打印一个整数 —— Monocarp达到评分 $ y $ 所需玩的最少游戏数，如果不可能，则打印 $ -1 $。
**输入输出样例**
**输入样例 #1**
```
3
7 2 10
3 1 9 2 5 20 8
7 1 10
3 1 9 2 5 20 8
5 10 12
100 1 200 11 300
```
**输出样例 #1**
```
20
-1
2
```
**说明**
在第一个测试用例中，Monocarp可以采用以下策略：
1. Monocarp与第 $ 2 $ 个对手对战，提升评分（$ 2 \to 3 $）；
2. Monocarp与第 $ 1 $ 个对手对战，提升评分（$ 3 \to 4 $）；
3. Monocarp与第 $ 4 $ 个对手对战，提升评分（$ 4 \to 5 $）；
4. Monocarp与第 $ 5 $ 个对手对战，提升评分（$ 5 \to 6 $）；
5. 现在，Monocarp需要与剩下的三个对手对战。因此，他将输掉 $ 3 $ 次，评分变为 $ 3 $（$ 6 \to 5 \to 4 \to 3 $）；
6. 之后，Monocarp将重复步骤 1-5。在 $ 14 $ 场比赛后，他已经与每个对手各玩了两次，最终评分为 $ 4 $。
7. Monocarp与第 $ 1 $ 个对手对战，提升评分（$ 4 \to 5 $）；
8. Monocarp与第 $ 2 $ 个对手对战，提升评分（$ 5 \to 6 $）；
9. Monocarp与第 $ 4 $ 个对手对战，提升评分（$ 6 \to 7 $）；
10. Monocarp与第 $ 5 $ 个对手对战，提升评分（$**题意翻译** 给你 $n$ 个人，每个人有一个能力值 $a_i$，你的能力值最开始从 $x$ 开始，目标是到 $y$。如果你打赢了一个能力值小于等于你的人，那么你的能力值 $+1$，反之 $-1$。问你在尽可能平均的情况下，也就是如果你要打 $i$ 那么不应该存在一个 $j$ 使得打 $i$ 的场次比打 $j$ 的场次多。求最少场次，或者判断无解。 **题目描述** Monocarp is playing chess on one popular website. He has $ n $ opponents he can play with. The $ i $-th opponent has rating equal to $ a_i $. Monocarp's initial rating is $ x $. Monocarp wants to raise his rating to the value $ y $ ( $ y > x $ ). When Monocarp is playing against one of the opponents, he will win if his current rating is bigger or equal to the opponent's rating. If Monocarp wins, his rating is increased by $ 1 $, otherwise it is decreased by $ 1 $. The rating of his opponent does not change. Monocarp wants to gain rating $ y $ playing as few games as possible. But he can't just grind it, playing against weak opponents. The website has a rule that you should play against all opponents as evenly as possible. Speaking formally, if Monocarp wants to play against an opponent $ i $, there should be no other opponent $ j $ such that Monocarp has played more games against $ i $ than against $ j $. Calculate the minimum possible number of games Monocarp needs to gain rating $ y $ or say it's impossible. Note that ratings of Monocarp's opponents don't change, while Monocarp's rating does change. **输入输出格式** **输入格式** 第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) —— 测试用例的数量。 每个测试用例的第一行包含三个整数 $ n $, $ x $ 和 $ y $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le x < y \le 10^{12} $ ) —— Monocarp的对手数量，他的初始评分和期望评分。 第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{12} $ ) —— Monocarp的对手的评分。 输入的额外限制：所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试用例，打印一个整数 —— Monocarp达到评分 $ y $ 所需玩的最少游戏数，如果不可能，则打印 $ -1 $。 **输入输出样例** **输入样例 #1** ``` 3 7 2 10 3 1 9 2 5 20 8 7 1 10 3 1 9 2 5 20 8 5 10 12 100 1 200 11 300 ``` **输出样例 #1** ``` 20 -1 2 ``` **说明** 在第一个测试用例中，Monocarp可以采用以下策略： 1. Monocarp与第 $ 2 $ 个对手对战，提升评分（$ 2 \to 3 $）； 2. Monocarp与第 $ 1 $ 个对手对战，提升评分（$ 3 \to 4 $）； 3. Monocarp与第 $ 4 $ 个对手对战，提升评分（$ 4 \to 5 $）； 4. Monocarp与第 $ 5 $ 个对手对战，提升评分（$ 5 \to 6 $）； 5. 现在，Monocarp需要与剩下的三个对手对战。因此，他将输掉 $ 3 $ 次，评分变为 $ 3 $（$ 6 \to 5 \to 4 \to 3 $）； 6. 之后，Monocarp将重复步骤 1-5。在 $ 14 $ 场比赛后，他已经与每个对手各玩了两次，最终评分为 $ 4 $。 7. Monocarp与第 $ 1 $ 个对手对战，提升评分（$ 4 \to 5 $）； 8. Monocarp与第 $ 2 $ 个对手对战，提升评分（$ 5 \to 6 $）； 9. Monocarp与第 $ 4 $ 个对手对战，提升评分（$ 6 \to 7 $）； 10. Monocarp与第 $ 5 $ 个对手对战，提升评分（$
给你 $n$ 个人，每个人有一个能力值 $a_i$，你的能力值最开始从 $x$ 开始，目标是到 $y$。如果你打赢了一个能力值小于等于你的人，那么你的能力值 $+1$，反之 $-1$。问你在尽可能平均的情况下，也就是如果你要打 $i$ 那么不应该存在一个 $j$ 使得打 $i$ 的场次比打 $j$ 的场次多。求最少场次，或者判断无解。
**题目描述**
Monocarp is playing chess on one popular website. He has $ n $ opponents he can play with. The $ i $-th opponent has rating equal to $ a_i $. Monocarp's initial rating is $ x $. Monocarp wants to raise his rating to the value $ y $ ( $ y > x $ ).
When Monocarp is playing against one of the opponents, he will win if his current rating is bigger or equal to the opponent's rating. If Monocarp wins, his rating is increased by $ 1 $, otherwise it is decreased by $ 1 $. The rating of his opponent does not change.
Monocarp wants to gain rating $ y $ playing as few games as possible. But he can't just grind it, playing against weak opponents. The website has a rule that you should play against all opponents as evenly as possible. Speaking formally, if Monocarp wants to play against an opponent $ i $, there should be no other opponent $ j $ such that Monocarp has played more games against $ i $ than against $ j $.
Calculate the minimum possible number of games Monocarp needs to gain rating $ y $ or say it's impossible. Note that ratings of Monocarp's opponents don't change, while Monocarp's rating does change.
**输入输出格式**
**输入格式**
第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) —— 测试用例的数量。
每个测试用例的第一行包含三个整数 $ n $, $ x $ 和 $ y $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le x < y \le 10^{12} $ ) —— Monocarp的对手数量，他的初始评分和期望评分。
第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{12} $ ) —— Monocarp的对手的评分。
输入的额外限制：所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。
**输出格式**
对于每个测试用例，打印一个整数 —— Monocarp达到评分 $ y $ 所需玩的最少游戏数，如果不可能，则打印 $ -1 $。
**输入输出样例**
**输入样例 #1**
```
3
7 2 10
3 1 9 2 5 20 8
7 1 10
3 1 9 2 5 20 8
5 10 12
100 1 200 11 300
```
**输出样例 #1**
```
20
-1
2
```
**说明**
在第一个测试用例中，Monocarp可以采用以下策略：
1. Monocarp与第 $ 2 $ 个对手对战，提升评分（$ 2 \to 3 $）；
2. Monocarp与第 $ 1 $ 个对手对战，提升评分（$ 3 \to 4 $）；
3. Monocarp与第 $ 4 $ 个对手对战，提升评分（$ 4 \to 5 $）；
4. Monocarp与第 $ 5 $ 个对手对战，提升评分（$ 5 \to 6 $）；
5. 现在，Monocarp需要与剩下的三个对手对战。因此，他将输掉 $ 3 $ 次，评分变为 $ 3 $（$ 6 \to 5 \to 4 \to 3 $）；
6. 之后，Monocarp将重复步骤 1-5。在 $ 14 $ 场比赛后，他已经与每个对手各玩了两次，最终评分为 $ 4 $。
7. Monocarp与第 $ 1 $ 个对手对战，提升评分（$ 4 \to 5 $）；
8. Monocarp与第 $ 2 $ 个对手对战，提升评分（$ 5 \to 6 $）；
9. Monocarp与第 $ 4 $ 个对手对战，提升评分（$ 6 \to 7 $）；
10. Monocarp与第 $ 5 $ 个对手对战，提升评分（$**题意翻译** 给你 $n$ 个人，每个人有一个能力值 $a_i$，你的能力值最开始从 $x$ 开始，目标是到 $y$。如果你打赢了一个能力值小于等于你的人，那么你的能力值 $+1$，反之 $-1$。问你在尽可能平均的情况下，也就是如果你要打 $i$ 那么不应该存在一个 $j$ 使得打 $i$ 的场次比打 $j$ 的场次多。求最少场次，或者判断无解。 **题目描述** Monocarp is playing chess on one popular website. He has $ n $ opponents he can play with. The $ i $-th opponent has rating equal to $ a_i $. Monocarp's initial rating is $ x $. Monocarp wants to raise his rating to the value $ y $ ( $ y > x $ ). When Monocarp is playing against one of the opponents, he will win if his current rating is bigger or equal to the opponent's rating. If Monocarp wins, his rating is increased by $ 1 $, otherwise it is decreased by $ 1 $. The rating of his opponent does not change. Monocarp wants to gain rating $ y $ playing as few games as possible. But he can't just grind it, playing against weak opponents. The website has a rule that you should play against all opponents as evenly as possible. Speaking formally, if Monocarp wants to play against an opponent $ i $, there should be no other opponent $ j $ such that Monocarp has played more games against $ i $ than against $ j $. Calculate the minimum possible number of games Monocarp needs to gain rating $ y $ or say it's impossible. Note that ratings of Monocarp's opponents don't change, while Monocarp's rating does change. **输入输出格式** **输入格式** 第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) —— 测试用例的数量。 每个测试用例的第一行包含三个整数 $ n $, $ x $ 和 $ y $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le x < y \le 10^{12} $ ) —— Monocarp的对手数量，他的初始评分和期望评分。 第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^{12} $ ) —— Monocarp的对手的评分。 输入的额外限制：所有测试用例中 $ n $ 的总和不超过 $ 2 \cdot 10^5 $。 **输出格式** 对于每个测试用例，打印一个整数 —— Monocarp达到评分 $ y $ 所需玩的最少游戏数，如果不可能，则打印 $ -1 $。 **输入输出样例** **输入样例 #1** ``` 3 7 2 10 3 1 9 2 5 20 8 7 1 10 3 1 9 2 5 20 8 5 10 12 100 1 200 11 300 ``` **输出样例 #1** ``` 20 -1 2 ``` **说明** 在第一个测试用例中，Monocarp可以采用以下策略： 1. Monocarp与第 $ 2 $ 个对手对战，提升评分（$ 2 \to 3 $）； 2. Monocarp与第 $ 1 $ 个对手对战，提升评分（$ 3 \to 4 $）； 3. Monocarp与第 $ 4 $ 个对手对战，提升评分（$ 4 \to 5 $）； 4. Monocarp与第 $ 5 $ 个对手对战，提升评分（$ 5 \to 6 $）； 5. 现在，Monocarp需要与剩下的三个对手对战。因此，他将输掉 $ 3 $ 次，评分变为 $ 3 $（$ 6 \to 5 \to 4 \to 3 $）； 6. 之后，Monocarp将重复步骤 1-5。在 $ 14 $ 场比赛后，他已经与每个对手各玩了两次，最终评分为 $ 4 $。 7. Monocarp与第 $ 1 $ 个对手对战，提升评分（$ 4 \to 5 $）； 8. Monocarp与第 $ 2 $ 个对手对战，提升评分（$ 5 \to 6 $）； 9. Monocarp与第 $ 4 $ 个对手对战，提升评分（$ 6 \to 7 $）； 10. Monocarp与第 $ 5 $ 个对手对战，提升评分（$