시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 713 356 128 54.701%

문제

정수 N개로 이루어진 배열 A가 주어진다. 상근이는 수열의 수 하나를 골라서 값을 1 감소시킬 수 있다. 단, 숫자는 1보다 작아질 수 없다.

상근이는 위의 감소시키는 연산을 최대 T번 하려고 한다. 이때, 인접한 숫자의 차이의 최댓값을 최소로 하는 프로그램을 출력하시오.

입력

첫째 줄에 N과 T가 주어진다.(2 ≤ N ≤ 100 000, 1 ≤ T ≤ 109)

둘째 줄에는 배열에 들어있는 수가 주어진다. (109보다 작은 자연수)

출력

첫째 줄에 인접합 숫자의 차이의 최댓값을 가장 작게한 배열 A의 내용을 공백으로 구분하여 출력한다. 최대 T번 감소시켜야 한다.

예제 입력 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이기 때문이다.

W3sicHJvYmxlbV9pZCI6IjMwOTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjMjhcdWM3NzRcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMTggTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYzMwXHVjNWY0IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjXHVjMTFjIFx1YWMxMlx1Yzc0NCAxIFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTgsIFx1YzIyYlx1Yzc5MFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1Yzc5MVx1YzU0NFx1YzljOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhNFx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjZDVjXHViMzAwIFRcdWJjODggXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LigyICZsZTsgTiAmbGU7IDEwMCAwMDAsIDEgJmxlOyBUICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzc4XHVjODExXHVkNTY5IFx1YzIyYlx1Yzc5MFx1Yzc1OCZuYnNwO1x1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1YWM4Y1x1ZDU1YyBcdWJjMzBcdWM1ZjQgQVx1Yzc1OCBcdWIwYjRcdWM2YTlcdWM3NDQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuJm5ic3A7XHVjZDVjXHViMzAwIFRcdWJjODggXHVhYzEwXHVjMThjXHVjMmRjXHVjZjFjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVhYzAxXHVhYzAxXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWM4MTBcdWMyMThcdWIyOTQgKDEwMCooUysxKVwvKEQrMSkpXC8oXHViMzcwXHVjNzc0XHVkMTMwIFx1YWMxY1x1YzIxOCkgXHVjODEwXHVjNzc0XHViMmU0LiBcdWM3NzRcdWI1NGMsIERcdWIyOTQgXHVjZDljXHViODI1XHVkNTVjIFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYyBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTIsIFNcdWIyOTQgXHVjODE1XHViMmY1XHVjNzc0XHViMmU0LiBcdWM5ODksJm5ic3A7XHVjZDljXHViODI1XHVkNTVjIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM4MTVcdWIyZjVcdWM3NzggXHVhY2JkXHVjNmIwIDEwXHVjODEwXHVjNzQ0IFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjZDljXHViODI1XHVkNTVjIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWNkMWQgVFx1YmM4OCBcdWFjMTBcdWMxOGNcdWMyZGNcdWNmMWNcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YWRmOCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyAwXHVjODEwXHVjNzQ0IFx1YzViYlx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM4MWMgXHVjZDljXHViODI1XHVjNzQ0ICZxdW90OzEgMiZuYnNwOzMgNSA2JnF1b3Q7XHVjNzNjXHViODVjIFx1ZDU1OFx1YmE3NCAxMCooMlwvMyk9Ni42Nlx1YzgxMFx1Yzc0NCBcdWJjMWJcdWFjOGMgXHViNDFjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWM3NDAgMVx1Yzc3OFx1YjM3MCwgXHVjZDljXHViODI1XHVkNTVjIFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExY1x1Yzc1OCBcdWIyZjVcdWM3NDAgMlx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzMDkwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiXHUwMTdkSVZJQ0EiLCJkZXNjcmlwdGlvbiI6IjxwPkFycmF5IG9mIE4gaW50ZWdlcnMgaXMgZ2l2ZW4uIEluIG9uZSBtb3ZlIE1pcmtvIGNhbiBkZWNyZWFzZSBvbmUgb2YgaXRzIGVsZW1lbnRzIGJ5IG9uZSwgYW5kIHJlcGVhdCBpdCBhcmJpdHJhcmlseSBidXQgbm8gbnVtYmVyIGNhbiBiZSBsZXNzIHRoYW4gMS4gSGUgaXMgZ2l2ZW4gVCBtb3ZlcyBhbmQgaGFzIHRvIHVzZSB0aGVtIGFsbC4gSGUgd2FudHMgdGhhdCBhZnRlciBoZSBpcyBkb25lIG1heGltYWwgYWJzb2x1dGUgZGlmZmVyZW5jZSBvZiBhbnkgdHdvIG5laWdoYm91cmluZyBudW1iZXJzIGlzIG1pbmltYWwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbiBmaXJzdCBsaW5lIG9mIHN0YW5kYXJkIGlucHV0IHRoZXJlIGFyZSB0d28gaW50ZWdlcnMgTiBhbmQgVCAoMiAmbGU7IE4gJmxlOyAxMDAgMDAwLCAxICZsZTsgVCAmbGU7IDEwPHN1cD45PFwvc3VwPiksIGFycmF5IGxlbmd0aCBhbmQgbnVtYmVyIG9mIG1vdmVzIE1pcmtvIHNob3VsZCBtYWtlLjxcL3A+XHJcblxyXG48cD5JbiBuZXh0IGxpbmUgdGhlcmUgYXJlIE4gbmF0dXJhbCBudW1iZXJzIGxlc3MgdGhhbiAxMDxzdXA+OTxcL3N1cD4uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+SW4gZmlyc3QgYW5kIG9ubHkgbGluZSBvdXRwdXQgYXJyYXkgYWZ0ZXIgTWlya28gaGFzIGRvbmUgVCBtb3Zlcy4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiPHA+Rm9yIGV2ZXJ5IHRlc3QgY2FzZSB5b3VyIHNvbHV0aW9uIHNjb3JlcyBwb2ludHMgYXMgZm9sbG93czogTGV0IEQgYmUgbWF4aW1hbCBhYnNvbHV0ZSBkaWZmZXJlbmNlIG9mIGFueSB0d28gbmVpZ2hib3VyaW5nIG51bWJlcnMgaW4geW91ciBzb2x1dGlvbiBhbmQgUyBpbiBvZmZpY2lhbChvcHRpbWFsKSBzb2x1dGlvbiwgdGhlbiB5b3VyIHNjb3JlIGZvciB0aGF0IHRlc3QgY2FzZSBpcyAoMTAgKiAoUyArIDEpIFwvIChEKzEpKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U28gZm9yIGV4YW1wbGUsIGlmIHlvdXIgc29sdXRpb24gaGFzIGRpZmZlcmVuY2UgRCBlcXVhbCB0byBvcHRpbWFsIG9uZSwgeW91ciBzY29yZSBpcyAxMCBwb2ludHMuIElmIHlvdXIgc29sdXRpb24gb3V0cHV0IGFycmF5IHdoaWNoIGNhbm5vdCBiZSBtYWRlIGluIFQgbW92ZXMgb3IgdGhlcmUgd2FzIHNvbWUgb3RoZXIgZXJyb3IgZHVyaW5nIHRoZSBwcm9ncmFtIGV4ZWN1dGlvbiB5b3VyIHNjb3JlIGlzIDAgb24gdGhhdCB0ZXN0IGNhc2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkluIHRlc3QgZXhhbXBsZSwgZm9yIHByaW50ZWQgc29sdXRpb24geyA0IDIgMyA1IDYgfSBtYXhpbWFsIGRpZmZlcmVuY2Ugb2YgYW55IHR3byBuZWlnaGJvdXJpbmcgbnVtYmVycyBpcyAyLCBzbyBzY29yZSBpcyAxMCooMlwvMykgPSA2LjY2IHBvaW50cywgYmVjYXVzZSBvcHRpbWFsIHNvbHV0aW9uIGlzIDEuJm5ic3A7PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=