시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB51025321252.346%

문제

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

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

수열 A와 B는 정수로만 이루어진 수열이고, 수열 B의 원소는 32비트 정수형 범위 안에 들어있어야 한다.

입력

첫 번째 줄에 N이 주어진다. (N ≤ 1,000,000) 두 번째 줄에 수열 A의 원소가 순서대로 주어진다. (0 ≤ Ai ≤ 2 × 109)

출력

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

예제 입력 1

7
9 4 8 20 14 15 18

예제 출력 1

6
7
8
13
14
15
18

힌트

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

W3sicHJvYmxlbV9pZCI6IjEzMzI0IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiQk9KIFx1YzIxOFx1YzVmNCAyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMyMThcdWM1ZjQgQTxzdWI+MTxcL3N1Yj4sIEE8c3ViPjI8XC9zdWI+Jm5ic3A7Li4gQTxzdWI+TjxcL3N1Yj4mbmJzcDtcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5CPHN1Yj4xPFwvc3ViPiZuYnNwOyZsdDsgQjxzdWI+MjxcL3N1Yj4mbmJzcDsmbHQ7IC4uLiAmbHQ7IEI8c3ViPk48XC9zdWI+Jm5ic3A7XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YmE3NFx1YzExYywgfEI8c3ViPjE8XC9zdWI+Jm5ic3A7LSBBPHN1Yj4xPFwvc3ViPnwgKyB8QjxzdWI+MjxcL3N1Yj4mbmJzcDstIEE8c3ViPjI8XC9zdWI+fCAuLi4gfEI8c3ViPk48XC9zdWI+Jm5ic3A7LSBBPHN1Yj5OPFwvc3ViPnwgXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjQgQlx1YWMwMCBcdWM4NzRcdWM3YWNcdWQ1NjAgXHViNTRjLCBcdWIyZjlcdWMyZTBcdWM3NDAgXHVhZGY4XHViN2VjXHVkNTVjIFx1YWMxMlx1Yzc1OCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YzVmNCBBXHVjNjQwIEJcdWIyOTQgXHVjODE1XHVjMjE4XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWM3NzRcdWFjZTAsIFx1YzIxOFx1YzVmNCBCXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YjI5NCAzMlx1YmU0NFx1ZDJiOCBcdWM4MTVcdWMyMThcdWQ2MTUgXHViYzk0XHVjNzA0IFx1YzU0OFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIChOICZsZTsgMSwwMDAsMDAwKSZuYnNwO1x1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzIxOFx1YzVmNCBBXHVjNzU4IFx1YzZkMFx1YzE4Y1x1YWMwMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IEE8c3ViPmk8XC9zdWI+Jm5ic3A7JmxlOyAyICZ0aW1lczsmbmJzcDsxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+fEI8c3ViPjE8XC9zdWI+Jm5ic3A7LSBBPHN1Yj4xPFwvc3ViPnwgKyB8QjxzdWI+MjxcL3N1Yj4mbmJzcDstIEE8c3ViPjI8XC9zdWI+fCAuLi4gfEI8c3ViPk48XC9zdWI+Jm5ic3A7LSBBPHN1Yj5OPFwvc3ViPnwgXHVhYzEyXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1OFx1YjI5NCBcdWMyMThcdWM1ZjRcdWM3NDQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1YzZkMFx1YzE4Y1x1Yjk3YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDBcdWMxMWMgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjZDljXHViODI1XHVkNTVjIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWFjMDEgXHVjNmQwXHVjMThjXHViMjk0LCAzMlx1YmU0NFx1ZDJiOCBcdWM4MTVcdWMyMThcdWQ2MTUgXHViYzk0XHVjNzA0IFx1YzU0OFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDBcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5CID0gezYsNyw4LDEzLDE0LDE1LDE4fSBcdWMyMThcdWM1ZjRcdWM3NzQgfEI8c3ViPjE8XC9zdWI+Jm5ic3A7LSBBPHN1Yj4xPFwvc3ViPnwgKyB8QjxzdWI+MjxcL3N1Yj4mbmJzcDstIEE8c3ViPjI8XC9zdWI+fCAuLi4gfEI8c3ViPk48XC9zdWI+Jm5ic3A7LSBBPHN1Yj5OPFwvc3ViPnwgXHVhYzEyXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1ZDY1NFx1ZDU1Y1x1YjJlNC4gXHVjZDVjXHVjMThjXHVkNjU0XHViNDFjIFx1YWMxMlx1Yzc0MCAxM1x1Yzc3NFx1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjEzMzI0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU2VxdWVuY2UgMiIsImRlc2NyaXB0aW9uIjoiPHA+PHU+U2hvcnQgZm9ybXVsYXRpb24uPFwvdT4gVGhlIG51bWJlciBzZXF1ZW5jZSBpcyBnaXZlbi4gWW91ciB0YXNrIGlzIHRvIGNvbnN0cnVjdCB0aGUgaW5jcmVhc2luZyBzZXF1ZW5jZSB0aGF0IGFwcHJveGltYXRlcyB0aGUgZ2l2ZW4gb25lIGluIHRoZSBiZXN0IHdheS4gVGhlIGJlc3QgYXBwcm94aW1hdGluZyBzZXF1ZW5jZSBpcyB0aGUgc2VxdWVuY2Ugd2l0aCB0aGUgbGVhc3QgdG90YWwgZGV2aWF0aW9uIGZyb20gdGhlIGdpdmVuIHNlcXVlbmNlLjxcL3A+XHJcblxyXG48cD48dT5Nb3JlIHByZWNpc2VseS48XC91PiZuYnNwO0xldCB0PHN1Yj4xPFwvc3ViPiwgdDxzdWI+MjxcL3N1Yj4sIC4uLiwgdDxzdWI+TjxcL3N1Yj4gaXMgdGhlIGdpdmVuIG51bWJlciBzZXF1ZW5jZS4gWW91ciB0YXNrIGlzIHRvIGNvbnN0cnVjdCB0aGUgaW5jcmVhc2luZyBudW1iZXIgc2VxdWVuY2UgejxzdWI+MTxcL3N1Yj4gJmx0OyB6PHN1Yj4yPFwvc3ViPiAmbHQ7IC4uLiAmbHQ7IHo8c3ViPk48XC9zdWI+LjxcL3A+XHJcblxyXG48cD5UaGUgc3VtIHx0PHN1Yj4xPFwvc3ViPiAtIHo8c3ViPjE8XC9zdWI+fCArIHx0PHN1Yj4yPFwvc3ViPiAtIHo8c3ViPjI8XC9zdWI+fCArIC4uLiArIHx0PHN1Yj5OPFwvc3ViPiAtIHo8c3ViPk48XC9zdWI+fCBzaG91bGQgYmUgYSBtaW5pbWFsIGZlYXNpYmxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgaXMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwMDAwKSBpbiB0aGUgZmlyc3QgbGluZSBvZiBpbnB1dC4gRWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIHNpbmdsZSBpbnRlZ2VyICZuZGFzaDsgdGhlIGdpdmVuIHNlcXVlbmNlIGVsZW1lbnQuIFRoZXJlIGlzIHQ8c3ViPks8XC9zdWI+Jm5ic3A7aW4gdGhlIChLKzEpLXRoIGxpbmUuIEFueSBlbGVtZW50IGlzIHNhdGlzZnlpbmcgdG8gcmVsYXRpb24gMCAmbGU7IHQ8c3ViPks8XC9zdWI+Jm5ic3A7JmxlOyAyMDAwMDAwMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkVhY2ggb2YgdGhlIE4gbGluZXMgbXVzdCBjb250YWluIHNpbmdsZSBpbnRlZ2VyICZuZGFzaDsgdGhlIHJlY3VycmVudCBlbGVtZW50IG9mIHRoZSBiZXN0IGFwcHJveGltYXRpbmcgc2VxdWVuY2UuPFwvcD5cclxuXHJcbjxwPklmIHRoZXJlIGFyZSBzZXZlcmFsIHNvbHV0aW9ucywgeW91ciBwcm9ncmFtIG11c3Qgb3V0cHV0IGFueSBvbmUgc2VxdWVuY2Ugd2l0aCBhIGxlYXN0IHRvdGFsIGRldmlhdGlvbi48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

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

  • 빠진 조건을 찾은 사람: jh05013
  • 문제를 번역한 사람: koosaga

채점 및 기타 정보

  • 예제는 채점하지 않는다.