시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 9 4 4 66.667%

문제

수열 A1, A2 .. AN 이 주어진다.

B1 < B2 < ... < BN 을 만족하면서, |B1 - A1| + |B2 - A2| ... |BN - AN| 을 최소화하는 수열 B가 존재할 때, 당신은 그러한 값의 가능한 최솟값을 출력해야 한다.

입력

첫번째 줄에 N이 주어진다. (N ≤ 1000000)

이후 N개의 줄에 수열 A의 원소가 순서대로 주어진다. (0 ≤ Ai ≤ 2 × 109)

출력

|B1 - A1| + |B2 - A2| ... |BN - AN| 값을 최소화하는 수열을 아무거나 출력한다. 각각의 원소를 N개의 줄에 걸쳐서 출력해야 한다. 출력한 수열의 각 원소는, 32비트 정수형 범위 안에 들어가야 한다.

예제 입력

7
9 4 8 20 14 15 18

예제 출력

6
7
8
13
14
15
18

힌트

B = {6,7,8,13,14,15,18} 수열이 |B1 - A1| + |B2 - A2| ... |BN - AN| 값을 최소화한다. 최소화된 값은 13이다. 

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2004 3-2번

  • 문제를 번역한 사람: koosaga