Repovive
  • Dashboard
  • Ranking
  • Submissions
  • Discussion
  1. Contests
  2. Premier Round 9
  3. 27A

My submissions

/
/
/
/

Announcements

My submissions

/
/
/
/

Announcements

Solve
Author

27A. Distinct Candies

500 pts·1s·256 MB

Constraints

Input

Output

Samples

Input
t
5
Case 1
4 2
Case 2
5 1
Case 3
1 0
Case 4
3 1
Case 5
6 3
Explanation
Case 1

Move two candies from the first container to the fourth, then one candy from the second container to the third. The final counts are 0, 1, 3, and 4.

Case 2

It is impossible to make the five counts distinct with only five candies.

Case 3

There is only one container, so no moves are needed.

Case 4

Move one candy from the first container to the third. The final counts are 0, 1, and 2.

Case 5

Transfer three candies from the first container to the sixth, two from the second to the fifth, and one from the third to the fourth. The final counts are 0, 1, 2, 4, 5, and 6.

Output
Case 1
3
Case 2
-1
Case 3
0
Case 4
1
Case 5
6
Input
t
3
Case 1
2 0
Case 2
2 1
Case 3
5 2
Explanation
Case 1

Both containers are empty, so no move is possible and their counts remain equal.

Case 2

Move one candy to the other container. The final counts are 0 and 2.

Case 3

The final counts can be 0, 1, 2, 3, and 4. Transfer two candies from the first container to the fifth and one from the second to the fourth. At least three moves are needed.

Output
Case 1
-1
Case 2
1
Case 3
3
Input
t
2
Case 1
4 10
Case 2
7 3
Explanation
Case 1

Transfer two candies from the first container to the fourth and one from the second to the third. The final counts are 8, 9, 11, and 12. Three moves are necessary.

Case 2

Transfer three candies from the first container to the seventh, two from the second to the sixth, and one from the third to the fifth. The final counts are 0, 1, 2, 3, 4, 5, and 6. At least six moves are necessary.

Output
Case 1
3
Case 2
6

There are nnn containers, each initially containing exactly mmm candies.

In one move, you take one candy from a nonempty container and put it into another container.

Find the minimum number of moves needed to make all containers contain pairwise distinct numbers of candies. Empty containers are allowed.

If this is impossible, print −1-1−1.

  • 1≤t≤1041 \le t \le 10^41≤t≤104
  • 1≤n≤1091 \le n \le 10^91≤n≤109
  • 0≤m≤1090 \le m \le 10^90≤m≤109
  • All input values are integers.
ttt nm}×t\left. \begin{array}{l} n \quad m \end{array} \right\} \times tnm​}×t
ans}×t\left. \begin{array}{l} ans \end{array} \right\} \times tans​}×t

For each test case, ansansans is the minimum number of moves, or −1-1−1 if it is impossible.