시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 2508 | 507 | 367 | 29.959% |
정수 N개로 이루어진 배열 A가 주어진다. 상근이는 수열의 수 하나를 골라서 값을 1 감소시킬 수 있다. 단, 수는 1보다 작아질 수 없다.
상근이는 위의 감소시키는 연산을 최대 T번 하려고 한다. 이때, 인접한 수의 차이의 최댓값을 최소로 하는 프로그램을 작성하시오.
첫째 줄에 N과 T가 주어진다. (2 ≤ N ≤ 100 000, 1 ≤ T ≤ 109)
둘째 줄에는 배열 A에 들어있는 수 A1, A2, ..., AN이 주어진다. (1 ≤ Ai < 109)
첫째 줄에 인접한 수의 차이의 최댓값을 가장 작게한 배열 A의 A1, A2, ..., AN을 공백으로 구분하여 출력한다.
5 2 3 2 3 2 2
2 2 2 2 2
5 5 4 2 3 7 6
3 2 3 4 5
3 6 10 10 1
9 5 1
각각의 테스트 케이스에 대해서, 점수는 (100×(S+1)/(D+1))/(데이터 개수) 점이다. 이때, D는 출력한 수열에서 인접한 수의 차이의 최댓값, S는 정답이다. 즉, 출력한 수열이 정답인 경우 10점을 얻게 된다. 하지만, 출력한 수열이 총 T번 감소시켜서 만들 수 없는 경우에는 그 테스트 케이스에 대해서 0점을 얻게 된다.
예를 들어, 예제 출력 2를 "1 2 3 5 6"으로 하면 10×(2/3)=6.66점을 받게 된다. 정답은 1인데, 출력한 수열에서의 답은 2이기 때문이다.
Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Additional task 1번