시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB250850736729.959%

문제

정수 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 2
3 2 3 2 2

예제 출력 1

2 2 2 2 2

예제 입력 2

5 5
4 2 3 7 6

예제 출력 2

3 2 3 4 5

예제 입력 3

3 6
10 10 1

예제 출력 3

9 5 1

힌트

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

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

W3sicHJvYmxlbV9pZCI6IjMwOTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNjMjhcdWM3NzRcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM4MTVcdWMyMTggTlx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHViYzMwXHVjNWY0IEFcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMjE4XHVjNWY0XHVjNzU4IFx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVhY2U4XHViNzdjXHVjMTFjIFx1YWMxMlx1Yzc0NCAxIFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWIyZTgsIFx1YzIxOFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1Yzc5MVx1YzU0NFx1YzljOCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzA0XHVjNzU4IFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhNFx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjZDVjXHViMzAwIFRcdWJjODggXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVhY2ZjIFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyAxMDAgMDAwLCAxICZsZTsgVCAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMzBcdWM1ZjQgQVx1YzVkMCBcdWI0ZTRcdWM1YjRcdWM3ODhcdWIyOTQgXHVjMjE4IEE8c3ViPjE8XC9zdWI+LCBBPHN1Yj4yPFwvc3ViPiwgLi4uLCBBPHN1Yj5OPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQTxzdWI+aTxcL3N1Yj4gJmx0OyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHVjMjE4XHVjNzU4IFx1Y2MyOFx1Yzc3NFx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NDQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1YWM4Y1x1ZDU1YyBcdWJjMzBcdWM1ZjQgQVx1Yzc1OCBBPHN1Yj4xPFwvc3ViPiwgQTxzdWI+MjxcL3N1Yj4sIC4uLiwgQTxzdWI+TjxcL3N1Yj5cdWM3NDQgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVjODEwXHVjMjE4XHViMjk0ICgxMDAmdGltZXM7KFMrMSlcLyhEKzEpKVwvKFx1YjM3MFx1Yzc3NFx1ZDEzMCBcdWFjMWNcdWMyMTgpIFx1YzgxMFx1Yzc3NFx1YjJlNC4gXHVjNzc0XHViNTRjLCBEXHViMjk0IFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHVjNzc4XHVjODExXHVkNTVjIFx1YzIxOFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyLCBTXHViMjk0IFx1YzgxNVx1YjJmNVx1Yzc3NFx1YjJlNC4gXHVjOTg5LCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1YzgxNVx1YjJmNVx1Yzc3OCBcdWFjYmRcdWM2YjAgMTBcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBcdWNkOWNcdWI4MjVcdWQ1NWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Y2QxZCBUXHViYzg4IFx1YWMxMFx1YzE4Y1x1YzJkY1x1Y2YxY1x1YzExYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVhZGY4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIDBcdWM4MTBcdWM3NDQgXHVjNWJiXHVhYzhjIFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjNjA4XHVjODFjIFx1Y2Q5Y1x1YjgyNSAyXHViOTdjICZxdW90OzEgMiAzIDUgNiZxdW90O1x1YzczY1x1Yjg1YyBcdWQ1NThcdWJhNzQgMTAmdGltZXM7KDJcLzMpPTYuNjZcdWM4MTBcdWM3NDQgXHViYzFiXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzQwIDFcdWM3NzhcdWIzNzAsIFx1Y2Q5Y1x1YjgyNVx1ZDU1YyBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWNcdWM3NTggXHViMmY1XHVjNzQwIDJcdWM3NzRcdWFlMzAgXHViNTRjXHViYjM4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA5MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ilx1MDE3ZElWSUNBIiwiZGVzY3JpcHRpb24iOiI8cD5BcnJheSBvZiBOIGludGVnZXJzIGlzIGdpdmVuLiBJbiBvbmUgbW92ZSBNaXJrbyBjYW4gZGVjcmVhc2Ugb25lIG9mIGl0cyBlbGVtZW50cyBieSBvbmUsIGFuZCByZXBlYXQgaXQgYXJiaXRyYXJpbHkgYnV0IG5vIG51bWJlciBjYW4gYmUgbGVzcyB0aGFuIDEuIEhlIGlzIGdpdmVuIFQgbW92ZXMgYW5kIGhhcyB0byB1c2UgdGhlbSBhbGwuIEhlIHdhbnRzIHRoYXQgYWZ0ZXIgaGUgaXMgZG9uZSBtYXhpbWFsIGFic29sdXRlIGRpZmZlcmVuY2Ugb2YgYW55IHR3byBuZWlnaGJvdXJpbmcgbnVtYmVycyBpcyBtaW5pbWFsLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW4gZmlyc3QgbGluZSBvZiBzdGFuZGFyZCBpbnB1dCB0aGVyZSBhcmUgdHdvIGludGVnZXJzIE4gYW5kIFQgKDIgJmxlOyBOICZsZTsgMTAwIDAwMCwgMSAmbGU7IFQgJmxlOyAxMDxzdXA+OTxcL3N1cD4pLCBhcnJheSBsZW5ndGggYW5kIG51bWJlciBvZiBtb3ZlcyBNaXJrbyBzaG91bGQgbWFrZS48XC9wPlxyXG5cclxuPHA+SW4gbmV4dCBsaW5lIHRoZXJlIGFyZSBOIG5hdHVyYWwgbnVtYmVycyBsZXNzIHRoYW4gMTA8c3VwPjk8XC9zdXA+LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkluIGZpcnN0IGFuZCBvbmx5IGxpbmUgb3V0cHV0IGFycmF5IGFmdGVyIE1pcmtvIGhhcyBkb25lIFQgbW92ZXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPkZvciBldmVyeSB0ZXN0IGNhc2UgeW91ciBzb2x1dGlvbiBzY29yZXMgcG9pbnRzIGFzIGZvbGxvd3M6IExldCBEIGJlIG1heGltYWwgYWJzb2x1dGUgZGlmZmVyZW5jZSBvZiBhbnkgdHdvIG5laWdoYm91cmluZyBudW1iZXJzIGluIHlvdXIgc29sdXRpb24gYW5kIFMgaW4gb2ZmaWNpYWwob3B0aW1hbCkgc29sdXRpb24sIHRoZW4geW91ciBzY29yZSBmb3IgdGhhdCB0ZXN0IGNhc2UgaXMgKDEwICogKFMgKyAxKSBcLyAoRCsxKSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNvIGZvciBleGFtcGxlLCBpZiB5b3VyIHNvbHV0aW9uIGhhcyBkaWZmZXJlbmNlIEQgZXF1YWwgdG8gb3B0aW1hbCBvbmUsIHlvdXIgc2NvcmUgaXMgMTAgcG9pbnRzLiBJZiB5b3VyIHNvbHV0aW9uIG91dHB1dCBhcnJheSB3aGljaCBjYW5ub3QgYmUgbWFkZSBpbiBUIG1vdmVzIG9yIHRoZXJlIHdhcyBzb21lIG90aGVyIGVycm9yIGR1cmluZyB0aGUgcHJvZ3JhbSBleGVjdXRpb24geW91ciBzY29yZSBpcyAwIG9uIHRoYXQgdGVzdCBjYXNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5JbiB0ZXN0IGV4YW1wbGUsIGZvciBwcmludGVkIHNvbHV0aW9uIHsgNCAyIDMgNSA2IH0gbWF4aW1hbCBkaWZmZXJlbmNlIG9mIGFueSB0d28gbmVpZ2hib3VyaW5nIG51bWJlcnMgaXMgMiwgc28gc2NvcmUgaXMgMTAqKDJcLzMpID0gNi42NiBwb2ludHMsIGJlY2F1c2Ugb3B0aW1hbCBzb2x1dGlvbiBpcyAxLiZuYnNwOzxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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

채점 및 기타 정보

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