31067번 - 다오의 경주 대회 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 1200 | 800 | 725 | 66.944% |
문제
경주 연습을 하는 다오
다오는 경주 대회를 열기 위해 $N$개의 트랙을 준비했다. $i$번째로 경주하는 트랙의 길이는 $A_i$이다.
관중들은 트랙의 길이가 점점 길어져야 경주가 재미있다고 생각한다. 즉, $A_1<A_2<\cdots <A_N$인 경우 경주가 재미있다고 생각한다. 이를 위해 다오는 다음과 같은 시행을 0회 이상 할 수 있다.
- $1\le i\le N$인 $i$를 고른 뒤, $i$번째 트랙의 길이를 $K$만큼 늘린다. 즉, $A_i$를 $A_i+K$로 바꾼다.
- 위 시행은 각 $i$에 대해 최대 한 번만 할 수 있다.
다오가 트랙의 길이를 점점 증가하도록 만들 수 있는지 판단하고, 만약 가능하다면 이를 위해 필요한 시행의 최소 횟수를 구하시오.
입력
첫째 줄에는 트랙의 수 $N$과 트랙을 늘릴 수 있는 길이 $K$가 띄어쓰기를 사이에 두고 정수로 주어진다.
둘째 줄에는 각 트랙의 길이를 나타내는 정수 $A_1$, $A_2$, $\cdots$, $A_N$이 띄어쓰기를 사이에 두고 주어진다.
출력
만약 다오가 트랙의 길이를 점점 증가하도록 만들 수 있다면, 이를 위해 필요한 최소 시행의 횟수를 출력하여라.
만약 다오가 트랙의 길이를 점점 증가하도록 만들 수 없다면, -1을 출력하여라.
제한
- $1\le N\le 10^5$
- $1\le K\le 10^9$
- $0\le A_i\le 10^9$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 10 | $N \le 3$ |
| 2 | 30 | $N \le 10$ |
| 3 | 60 | 문제에 주어진 조건 이외에 추가 제한 조건이 없다. |
예제 입력 1
3 2 4 3 4
예제 출력 1
2
2번과 3번 트랙의 길이를 $2$만큼 늘리면 각 트랙의 길이는 $A=[4, 5, 6]$이 되어 트랙의 길이가 점점 길어진다.
예제 입력 2
3 5 7 5 5
예제 출력 2
-1
트랙의 길이가 점점 증가하도록 트랙의 길이를 늘리는 방법이 존재하지 않는다.
예제 입력 3
6 5 2 4 3 9 5 8
예제 출력 3
3
3번, 5번, 6번 트랙의 길이를 $5$만큼 늘리면 각 트랙의 길이는 $A=[2, 4, 8, 9, 10, 13]$이 되어 트랙의 길이가 점점 길어진다.
출처
School > 서울과학고등학교 > SciOI 2023 A-2번
- 문제를 만든 사람: 79brue
- 문제를 검수한 사람: ibm2006, jimini23, mjhmjh1104, naeby, utilforever, whqkrkt04
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호