Make All Distinct
브론즈 II의견: 0
You have an integer array \(a_1\dots a_N\) with elements initially in the range
\([1,N]\)
(\(1\le N\le 2\cdot 10^5\)), as well as a nonzero integer \(K\)
(\(-N \le K\le N, K\neq 0\)).
You may perform the following operation as many times as you'd like (possibly
zero): select an index \(i\) and set \(a_i=a_i+K\).
Find the minimum number of operations to make all array elements distinct.
Problem credits: Akshaj Arora, Benjamin Qi
SCORING
- Inputs 2-4: \(N\le 50\)
- Inputs 5-7: \(N\le 2000\)
- Inputs 8-10: \(K=1\)
- Inputs 11-13: No additional constraints.
Problem credits: Akshaj Arora, Benjamin Qi
The input consists of \(T\) (\(1\le T\le 10\)) independent tests. Each test is
described as follows:
The first line contains \(N\) and \(K\).
The second line contains \(a_1\dots a_N\).
It is guaranteed that the sum of \(N\) over all tests does not exceed
\(10^6\).
For each test, output a single line containing the minimum number of operations.
Note: The large size of integers involved in this problem may require the use
of 64-bit integer data types (e.g., a "long long" in C/C++).
4
4 1
4 1 4 1
4 -3
4 1 4 1
4 4
4 1 4 1
3 -1
1 1 22
4
2
1For the first test, here is a possible sequence of two operations that makes all
elements distinct.
4 1 4 1
5 1 4 1 (a_1 += 1)
5 1 4 2 (a_4 += 1)
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Bronze
평가 및 의견
Make All Distinct
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Make All Distinct