레이팅 미적용원소가 처음에 범위 \([1,N]\) (\(1\le N\le 2\cdot 10^5\))에 속하는 정수 배열 \(a_1\dots a_N\)과 0이 아닌 정수 \(K\) (\(-N \le K\le N, K\neq 0\))가 있다.
다음 연산을 원하는 만큼(0번 포함) 수행할 수 있다: 인덱스 \(i\)를 선택하고 \(a_i=a_i+K\)로 만든다.
배열의 모든 원소를 서로 다르게 만들기 위한 최소 연산 횟수를 구하시오.
문제 제공: Akshaj Arora, Benjamin Qi
채점 방식
- 입력 2-4: \(N\le 50\)
- 입력 5-7: \(N\le 2000\)
- 입력 8-10: \(K=1\)
- 입력 11-13: 추가 제약 조건이 없다.
문제 제공: Akshaj Arora, Benjamin Qi
입력은 \(T\) (\(1\le T\le 10\))개의 독립적인 테스트로 구성된다. 각 테스트는 다음과 같이 주어진다.
첫째 줄에 \(N\)과 \(K\)가 주어진다.
둘째 줄에 \(a_1\dots a_N\)이 주어진다.
모든 테스트에 대한 \(N\)의 합은 \(10^6\)을 넘지 않음이 보장된다.
각 테스트마다 최소 연산 횟수를 한 줄에 출력한다.
참고: 이 문제에서 다루는 정수의 크기가 크기 때문에 64비트 정수 자료형(예: C/C++의 "long long")을 사용해야 할 수 있다.
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