시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1458 150 106 26.700%

문제

정수 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을 공백으로 구분하여 출력한다.

예제 입력 1

5 5
4 2 3 7 6

예제 출력 1

3 2 3 4 5

힌트

각각의 테스트 케이스에 대해서, 점수는 (100×(S+1)/(D+1))/(데이터 개수) 점이다. 이때, D는 출력한 수열에서 인접한 수의 차이의 최댓값, S는 정답이다. 즉, 출력한 수열이 정답인 경우 10점을 얻게 된다. 하지만, 출력한 수열이 총 T번 감소시켜서 만들 수 없는 경우에는 그 테스트 케이스에 대해서 0점을 얻게 된다.

예를 들어, 위의 예제 출력을 "1 2 3 5 6"으로 하면 10×(2/3)=6.66점을 받게 된다. 정답은 1인데, 출력한 수열에서의 답은 2이기 때문이다.

W3sicHJvYmxlbV9pZCI6IjMwOTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjMjhcdWM3NzRcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMTggTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYzMwXHVjNWY0IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjXHVjMTFjIFx1YWMxMlx1Yzc0NCAxIFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTgsIFx1YzIxOFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1Yzc5MVx1YzU0NFx1YzljOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhNFx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjZDVjXHViMzAwIFRcdWJjODggXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAgMDAwLCAxICZsZTsgVCAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMzBcdWM1ZjQgQVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4IEE8c3ViPjE8XC9zdWI+LCBBPHN1Yj4yPFwvc3ViPiwgLi4uLCBBPHN1Yj5OPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4gJmx0OyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3NzhcdWM4MTFcdWQ1NWMmbmJzcDtcdWMyMThcdWM3NTgmbmJzcDtcdWNjMjhcdWM3NzRcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWFjOGNcdWQ1NWMgXHViYzMwXHVjNWY0IEFcdWM3NTggQTxzdWI+MTxcL3N1Yj4sIEE8c3ViPjI8XC9zdWI+LCAuLi4sIEE8c3ViPk48XC9zdWI+XHVjNzQ0Jm5ic3A7XHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjODEwXHVjMjE4XHViMjk0ICgxMDAmdGltZXM7KFMrMSlcLyhEKzEpKVwvKFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWFjMWNcdWMyMTgpIFx1YzgxMFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBEXHViMjk0IFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YzIxOFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyLCBTXHViMjk0IFx1YzgxNVx1YjJmNVx1Yzc3NFx1YjJlNC4gXHVjOTg5LCZuYnNwO1x1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjODE1XHViMmY1XHVjNzc4IFx1YWNiZFx1YzZiMCAxMFx1YzgxMFx1Yzc0NCBcdWM1YmJcdWFjOGMgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM3NzQgXHVjZDFkIFRcdWJjODggXHVhYzEwXHVjMThjXHVjMmRjXHVjZjFjXHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFkZjggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgMFx1YzgxMFx1Yzc0NCBcdWM1YmJcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBcdWM3MDRcdWM3NTggXHVjNjA4XHVjODFjIFx1Y2Q5Y1x1YjgyNVx1Yzc0NCAmcXVvdDsxIDImbmJzcDszIDUgNiZxdW90O1x1YzczY1x1Yjg1YyBcdWQ1NThcdWJhNzQgMTAmdGltZXM7KDJcLzMpPTYuNjZcdWM4MTBcdWM3NDQgXHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzQwIDFcdWM3NzhcdWIzNzAsIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWNcdWM3NTggXHViMmY1XHVjNzQwIDJcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA5MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ilx1MDE3ZElWSUNBIiwiZGVzY3JpcHRpb24iOiI8cD5BcnJheSBvZiBOIGludGVnZXJzIGlzIGdpdmVuLiBJbiBvbmUgbW92ZSBNaXJrbyBjYW4gZGVjcmVhc2Ugb25lIG9mIGl0cyBlbGVtZW50cyBieSBvbmUsIGFuZCByZXBlYXQgaXQgYXJiaXRyYXJpbHkgYnV0IG5vIG51bWJlciBjYW4gYmUgbGVzcyB0aGFuIDEuIEhlIGlzIGdpdmVuIFQgbW92ZXMgYW5kIGhhcyB0byB1c2UgdGhlbSBhbGwuIEhlIHdhbnRzIHRoYXQgYWZ0ZXIgaGUgaXMgZG9uZSBtYXhpbWFsIGFic29sdXRlIGRpZmZlcmVuY2Ugb2YgYW55IHR3byBuZWlnaGJvdXJpbmcgbnVtYmVycyBpcyBtaW5pbWFsLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gZmlyc3QgbGluZSBvZiBzdGFuZGFyZCBpbnB1dCB0aGVyZSBhcmUgdHdvIGludGVnZXJzIE4gYW5kIFQgKDIgJmxlOyBOICZsZTsgMTAwIDAwMCwgMSAmbGU7IFQgJmxlOyAxMDxzdXA+OTxcL3N1cD4pLCBhcnJheSBsZW5ndGggYW5kIG51bWJlciBvZiBtb3ZlcyBNaXJrbyBzaG91bGQgbWFrZS48XC9wPlxyXG5cclxuPHA+SW4gbmV4dCBsaW5lIHRoZXJlIGFyZSBOIG5hdHVyYWwgbnVtYmVycyBsZXNzIHRoYW4gMTA8c3VwPjk8XC9zdXA+LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIGZpcnN0IGFuZCBvbmx5IGxpbmUgb3V0cHV0IGFycmF5IGFmdGVyIE1pcmtvIGhhcyBkb25lIFQgbW92ZXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkZvciBldmVyeSB0ZXN0IGNhc2UgeW91ciBzb2x1dGlvbiBzY29yZXMgcG9pbnRzIGFzIGZvbGxvd3M6IExldCBEIGJlIG1heGltYWwgYWJzb2x1dGUgZGlmZmVyZW5jZSBvZiBhbnkgdHdvIG5laWdoYm91cmluZyBudW1iZXJzIGluIHlvdXIgc29sdXRpb24gYW5kIFMgaW4gb2ZmaWNpYWwob3B0aW1hbCkgc29sdXRpb24sIHRoZW4geW91ciBzY29yZSBmb3IgdGhhdCB0ZXN0IGNhc2UgaXMgKDEwICogKFMgKyAxKSBcLyAoRCsxKSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNvIGZvciBleGFtcGxlLCBpZiB5b3VyIHNvbHV0aW9uIGhhcyBkaWZmZXJlbmNlIEQgZXF1YWwgdG8gb3B0aW1hbCBvbmUsIHlvdXIgc2NvcmUgaXMgMTAgcG9pbnRzLiBJZiB5b3VyIHNvbHV0aW9uIG91dHB1dCBhcnJheSB3aGljaCBjYW5ub3QgYmUgbWFkZSBpbiBUIG1vdmVzIG9yIHRoZXJlIHdhcyBzb21lIG90aGVyIGVycm9yIGR1cmluZyB0aGUgcHJvZ3JhbSBleGVjdXRpb24geW91ciBzY29yZSBpcyAwIG9uIHRoYXQgdGVzdCBjYXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiB0ZXN0IGV4YW1wbGUsIGZvciBwcmludGVkIHNvbHV0aW9uIHsgNCAyIDMgNSA2IH0gbWF4aW1hbCBkaWZmZXJlbmNlIG9mIGFueSB0d28gbmVpZ2hib3VyaW5nIG51bWJlcnMgaXMgMiwgc28gc2NvcmUgaXMgMTAqKDJcLzMpID0gNi42NiBwb2ludHMsIGJlY2F1c2Ugb3B0aW1hbCBzb2x1dGlvbiBpcyAxLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Additional task 1번

  • 데이터를 추가한 사람: 3587jjh
  • 문제의 오타를 찾은 사람: zych1751

채점 및 기타 정보

  • 100점 이상을 획득해야 를 받는다.