시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 676 330 114 54.545%

문제

정수 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+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhNFx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjZDVjXHViMzAwIFRcdWJjODggXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHVjNzc4XHVjODExXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4oMiAmbGU7IE4gJmxlOyAxMDAgMDAwLCAxICZsZTsgVCAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMzBcdWM1ZjRcdWM1ZDAgXHViNGU0XHVjNWI0XHVjNzg4XHViMjk0IFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxMDxzdXA+OTxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yzc3OFx1YzgxMVx1ZDU2OSBcdWMyMmJcdWM3OTBcdWM3NTgmbmJzcDtcdWNjMjhcdWM3NzRcdWM3NTggXHVjZDVjXHViMzAwXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWFjOGNcdWQ1NWMgXHViYzMwXHVjNWY0IEFcdWM3NTggXHViMGI0XHVjNmE5XHVjNzQ0IFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiZuYnNwO1x1Y2Q1Y1x1YjMwMCBUXHViYzg4IFx1YWMxMFx1YzE4Y1x1YzJkY1x1Y2YxY1x1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjODEwXHVjMjE4XHViMjk0ICgxMDAqKFMrMSlcLyhEKzEpKVwvKFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWFjMWNcdWMyMTgpIFx1YzgxMFx1Yzc3NFx1YjJlNC4gXHVjNzc0IFx1YjU0YywgRFx1YjI5NCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWM3NTggXHVjYzI4XHVjNzc0XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMiwgU1x1YjI5NCBcdWM4MTVcdWIyZjVcdWM3NzRcdWIyZTQuIFx1Yzk4OSwmbmJzcDtcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzgxNVx1YjJmNVx1Yzc3OCBcdWFjYmRcdWM2YjAgMTBcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Y2QxZCBUXHViYzg4IFx1YWMxMFx1YzE4Y1x1YzJkY1x1Y2YxY1x1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIDBcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNzA0XHVjNzU4IFx1YzYwOFx1YzgxYyBcdWNkOWNcdWI4MjVcdWM3NDQgJnF1b3Q7MSAyJm5ic3A7MyA1IDYmcXVvdDtcdWM3M2NcdWI4NWMgXHVkNTU4XHViYTc0IDEwKigyXC8zKT02LjY2XHVjODEwXHVjNzQ0IFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc0MCAxXHVjNzc4XHViMzcwLCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjXHVjNzU4IFx1YjJmNVx1Yzc0MCAyXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwOTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJcdTAxN2RJVklDQSIsImRlc2NyaXB0aW9uIjoiPHA+QXJyYXkgb2YgTiBpbnRlZ2VycyBpcyBnaXZlbi4gSW4gb25lIG1vdmUgTWlya28gY2FuIGRlY3JlYXNlIG9uZSBvZiBpdHMgZWxlbWVudHMgYnkgb25lLCBhbmQgcmVwZWF0IGl0IGFyYml0cmFyaWx5IGJ1dCBubyBudW1iZXIgY2FuIGJlIGxlc3MgdGhhbiAxLiBIZSBpcyBnaXZlbiBUIG1vdmVzIGFuZCBoYXMgdG8gdXNlIHRoZW0gYWxsLiBIZSB3YW50cyB0aGF0IGFmdGVyIGhlIGlzIGRvbmUgbWF4aW1hbCBhYnNvbHV0ZSBkaWZmZXJlbmNlIG9mIGFueSB0d28gbmVpZ2hib3VyaW5nIG51bWJlcnMgaXMgbWluaW1hbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkluIGZpcnN0IGxpbmUgb2Ygc3RhbmRhcmQgaW5wdXQgdGhlcmUgYXJlIHR3byBpbnRlZ2VycyBOIGFuZCBUICgyICZsZTsgTiAmbGU7IDEwMCAwMDAsIDEgJmxlOyBUICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgYXJyYXkgbGVuZ3RoIGFuZCBudW1iZXIgb2YgbW92ZXMgTWlya28gc2hvdWxkIG1ha2UuPFwvcD5cclxuXHJcbjxwPkluIG5leHQgbGluZSB0aGVyZSBhcmUgTiBuYXR1cmFsIG51bWJlcnMgbGVzcyB0aGFuIDEwPHN1cD45PFwvc3VwPi4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5JbiBmaXJzdCBhbmQgb25seSBsaW5lIG91dHB1dCBhcnJheSBhZnRlciBNaXJrbyBoYXMgZG9uZSBUIG1vdmVzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiI8cD5Gb3IgZXZlcnkgdGVzdCBjYXNlIHlvdXIgc29sdXRpb24gc2NvcmVzIHBvaW50cyBhcyBmb2xsb3dzOiBMZXQgRCBiZSBtYXhpbWFsIGFic29sdXRlIGRpZmZlcmVuY2Ugb2YgYW55IHR3byBuZWlnaGJvdXJpbmcgbnVtYmVycyBpbiB5b3VyIHNvbHV0aW9uIGFuZCBTIGluIG9mZmljaWFsKG9wdGltYWwpIHNvbHV0aW9uLCB0aGVuIHlvdXIgc2NvcmUgZm9yIHRoYXQgdGVzdCBjYXNlIGlzICgxMCAqIChTICsgMSkgXC8gKEQrMSkpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TbyBmb3IgZXhhbXBsZSwgaWYgeW91ciBzb2x1dGlvbiBoYXMgZGlmZmVyZW5jZSBEIGVxdWFsIHRvIG9wdGltYWwgb25lLCB5b3VyIHNjb3JlIGlzIDEwIHBvaW50cy4gSWYgeW91ciBzb2x1dGlvbiBvdXRwdXQgYXJyYXkgd2hpY2ggY2Fubm90IGJlIG1hZGUgaW4gVCBtb3ZlcyBvciB0aGVyZSB3YXMgc29tZSBvdGhlciBlcnJvciBkdXJpbmcgdGhlIHByb2dyYW0gZXhlY3V0aW9uIHlvdXIgc2NvcmUgaXMgMCBvbiB0aGF0IHRlc3QgY2FzZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SW4gdGVzdCBleGFtcGxlLCBmb3IgcHJpbnRlZCBzb2x1dGlvbiB7IDQgMiAzIDUgNiB9IG1heGltYWwgZGlmZmVyZW5jZSBvZiBhbnkgdHdvIG5laWdoYm91cmluZyBudW1iZXJzIGlzIDIsIHNvIHNjb3JlIGlzIDEwKigyXC8zKSA9IDYuNjYgcG9pbnRzLCBiZWNhdXNlIG9wdGltYWwgc29sdXRpb24gaXMgMS4mbmJzcDs8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==