시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 850 462 158 55.245%

문제

정수 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이기 때문이다.

W3sicHJvYmxlbV9pZCI6IjMwOTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjMjhcdWM3NzRcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMTggTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYzMwXHVjNWY0IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjXHVjMTFjIFx1YWMxMlx1Yzc0NCAxIFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTgsIFx1YzIxOFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1Yzc5MVx1YzU0NFx1YzljOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhNFx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjZDVjXHViMzAwIFRcdWJjODggXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjZDljXHViODI1XHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LigyICZsZTsgTiAmbGU7IDEwMCAwMDAsIDEgJmxlOyBUICZsZTsgMTA8c3VwPjk8XC9zdXA+KTxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMzMFx1YzVmNFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWM3OTFcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4KTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNzc4XHVjODExXHVkNTVjJm5ic3A7XHVjMjE4XHVjNzU4Jm5ic3A7XHVjYzI4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMlx1Yzc0NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVhYzhjXHVkNTVjIFx1YmMzMFx1YzVmNCBBXHVjNzU4IFx1YjBiNFx1YzZhOVx1Yzc0NCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHVkNTU4XHVjNWVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDtcdWNkNWNcdWIzMDAgVFx1YmM4OCBcdWFjMTBcdWMxOGNcdWMyZGNcdWNmMWNcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzgxMFx1YzIxOFx1YjI5NCAoMTAwKihTKzEpXC8oRCsxKSlcLyhcdWIzNzBcdWM3NzRcdWQxMzAgXHVhYzFjXHVjMjE4KSBcdWM4MTBcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgRFx1YjI5NCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWMyMThcdWM3NTggXHVjYzI4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjMxM1x1YWMxMiwgU1x1YjI5NCBcdWM4MTVcdWIyZjVcdWM3NzRcdWIyZTQuIFx1Yzk4OSwmbmJzcDtcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzgxNVx1YjJmNVx1Yzc3OCBcdWFjYmRcdWM2YjAgMTBcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Y2QxZCBUXHViYzg4IFx1YWMxMFx1YzE4Y1x1YzJkY1x1Y2YxY1x1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIDBcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjVcdWM3NDQgJnF1b3Q7MSAyJm5ic3A7MyA1IDYmcXVvdDtcdWM3M2NcdWI4NWMgXHVkNTU4XHViYTc0IDEwKigyXC8zKT02LjY2XHVjODEwXHVjNzQ0IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc0MCAxXHVjNzc4XHViMzcwLCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjXHVjNzU4IFx1YjJmNVx1Yzc0MCAyXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwOTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJcdTAxN2RJVklDQSIsImRlc2NyaXB0aW9uIjoiPHA+QXJyYXkgb2YgTiBpbnRlZ2VycyBpcyBnaXZlbi4gSW4gb25lIG1vdmUgTWlya28gY2FuIGRlY3JlYXNlIG9uZSBvZiBpdHMgZWxlbWVudHMgYnkgb25lLCBhbmQgcmVwZWF0IGl0IGFyYml0cmFyaWx5IGJ1dCBubyBudW1iZXIgY2FuIGJlIGxlc3MgdGhhbiAxLiBIZSBpcyBnaXZlbiBUIG1vdmVzIGFuZCBoYXMgdG8gdXNlIHRoZW0gYWxsLiBIZSB3YW50cyB0aGF0IGFmdGVyIGhlIGlzIGRvbmUgbWF4aW1hbCBhYnNvbHV0ZSBkaWZmZXJlbmNlIG9mIGFueSB0d28gbmVpZ2hib3VyaW5nIG51bWJlcnMgaXMgbWluaW1hbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIGZpcnN0IGxpbmUgb2Ygc3RhbmRhcmQgaW5wdXQgdGhlcmUgYXJlIHR3byBpbnRlZ2VycyBOIGFuZCBUICgyICZsZTsgTiAmbGU7IDEwMCAwMDAsIDEgJmxlOyBUICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgYXJyYXkgbGVuZ3RoIGFuZCBudW1iZXIgb2YgbW92ZXMgTWlya28gc2hvdWxkIG1ha2UuPFwvcD5cclxuXHJcbjxwPkluIG5leHQgbGluZSB0aGVyZSBhcmUgTiBuYXR1cmFsIG51bWJlcnMgbGVzcyB0aGFuIDEwPHN1cD45PFwvc3VwPi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiBmaXJzdCBhbmQgb25seSBsaW5lIG91dHB1dCBhcnJheSBhZnRlciBNaXJrbyBoYXMgZG9uZSBUIG1vdmVzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIHlvdXIgc29sdXRpb24gc2NvcmVzIHBvaW50cyBhcyBmb2xsb3dzOiBMZXQgRCBiZSBtYXhpbWFsIGFic29sdXRlIGRpZmZlcmVuY2Ugb2YgYW55IHR3byBuZWlnaGJvdXJpbmcgbnVtYmVycyBpbiB5b3VyIHNvbHV0aW9uIGFuZCBTIGluIG9mZmljaWFsKG9wdGltYWwpIHNvbHV0aW9uLCB0aGVuIHlvdXIgc2NvcmUgZm9yIHRoYXQgdGVzdCBjYXNlIGlzICgxMCAqIChTICsgMSkgXC8gKEQrMSkpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TbyBmb3IgZXhhbXBsZSwgaWYgeW91ciBzb2x1dGlvbiBoYXMgZGlmZmVyZW5jZSBEIGVxdWFsIHRvIG9wdGltYWwgb25lLCB5b3VyIHNjb3JlIGlzIDEwIHBvaW50cy4gSWYgeW91ciBzb2x1dGlvbiBvdXRwdXQgYXJyYXkgd2hpY2ggY2Fubm90IGJlIG1hZGUgaW4gVCBtb3ZlcyBvciB0aGVyZSB3YXMgc29tZSBvdGhlciBlcnJvciBkdXJpbmcgdGhlIHByb2dyYW0gZXhlY3V0aW9uIHlvdXIgc2NvcmUgaXMgMCBvbiB0aGF0IHRlc3QgY2FzZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gdGVzdCBleGFtcGxlLCBmb3IgcHJpbnRlZCBzb2x1dGlvbiB7IDQgMiAzIDUgNiB9IG1heGltYWwgZGlmZmVyZW5jZSBvZiBhbnkgdHdvIG5laWdoYm91cmluZyBudW1iZXJzIGlzIDIsIHNvIHNjb3JlIGlzIDEwKigyXC8zKSA9IDYuNjYgcG9pbnRzLCBiZWNhdXNlIG9wdGltYWwgc29sdXRpb24gaXMgMS4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==