시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1466 640 595 46.088%

문제

학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어의 점수는 레벨을 클리어하면서 얻은 점수의 합으로, 이 점수를 바탕으로 온라인 순위를 매긴다. 동준이는 레벨을 난이도 순으로 배치했다. 하지만, 실수로 쉬운 레벨이 어려운 레벨보다 점수를 많이 받는 경우를 만들었다.

이 문제를 해결하기 위해 동준이는 특정 레벨의 점수를 감소시키려고 한다. 이렇게해서 각 레벨을 클리어할 때 주는 점수가 증가하게 만드려고 한다.

각 레벨을 클리어할 때 얻는 점수가 주어졌을 때, 몇 번 감소시키면 되는지 구하는 프로그램을 작성하시오. 점수는 항상 양수이어야 하고, 1만큼 감소시키는 것이 1번이다. 항상 답이 존재하는 경우만 주어진다. 정답이 여러가지인 경우에는 점수를 내리는 것을 최소한으로 하는 방법을 찾아야 한다.

입력

첫째 줄에 레벨의 수 N이 주어진다. (1 ≤ N ≤ 100) 다음 N개 줄에는 각 레벨을 클리어하면 얻는 점수가 첫 번째 레벨부터 마지막 레벨까지 순서대로 주어진다. 점수는 20,000보다 작은 양의 정수이다.

출력

첫째 줄에 점수를 몇 번 감소시키면 되는지 출력한다.

예제 입력 1

4
5
3
7
5

예제 출력 1

6
W3sicHJvYmxlbV9pZCI6IjI4NDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjOGNcdWM3ODRcdWM3NDQgXHViOWNjXHViNGUwIFx1YjNkOVx1YzkwMFx1Yzc3NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVkNTU5XHVhZDUwXHVjNWQwXHVjMTFjIFx1YWRmOFx1Yjc5OFx1ZDUzZFx1YzJhNCBcdWMyMThcdWM1YzVcdWM3NDQgXHViNGU0XHVjNzQwIFx1YjNkOVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWMyMThcdWM1YzVcdWMyZGNcdWFjMDRcdWM1ZDAgXHViNGU0XHVjNzQwIFx1YjBiNFx1YzZhOVx1Yzc0NCBcdWJjMTRcdWQwZDVcdWM3M2NcdWI4NWMgXHVjMmE0XHViOWM4XHVkMmI4XHVkM2YwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YWM4Y1x1Yzc4NFx1YzVkMFx1YjI5NCBcdWNkMWQgTlx1YWMxY1x1Yzc1OCBcdWI4MDhcdWJjYThcdWM3NzQgXHVjNzg4XHVhY2UwLCBcdWFjMDEgXHViODA4XHViY2E4XHVjNzQ0IFx1ZDA3NFx1YjlhY1x1YzViNFx1ZDU2MCBcdWI1NGMgXHViOWM4XHViMmU0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1Yzc1OCBcdWM4MTBcdWMyMThcdWIyOTQgXHViODA4XHViY2E4XHVjNzQ0IFx1ZDA3NFx1YjlhY1x1YzViNFx1ZDU1OFx1YmE3NFx1YzExYyBcdWM1YmJcdWM3NDAgXHVjODEwXHVjMjE4XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YywgXHVjNzc0IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWJjMTRcdWQwZDVcdWM3M2NcdWI4NWMgXHVjNjI4XHViNzdjXHVjNzc4IFx1YzIxY1x1YzcwNFx1Yjk3YyBcdWI5ZTRcdWFlMzRcdWIyZTQuIFx1YjNkOVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWI4MDhcdWJjYThcdWM3NDQgXHViMDljXHVjNzc0XHViM2M0IFx1YzIxY1x1YzczY1x1Yjg1YyBcdWJjMzBcdWNlNThcdWQ1ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVjMmU0XHVjMjE4XHViODVjIFx1YzI2Y1x1YzZiNCBcdWI4MDhcdWJjYThcdWM3NzQgXHVjNWI0XHViODI0XHVjNmI0IFx1YjgwOFx1YmNhOFx1YmNmNFx1YjJlNCBcdWM4MTBcdWMyMThcdWI5N2MgXHViOWNlXHVjNzc0IFx1YmMxYlx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5N2MgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHViYjM4XHVjODFjXHViOTdjIFx1ZDU3NFx1YWNiMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViM2Q5XHVjOTAwXHVjNzc0XHViMjk0IFx1ZDJiOVx1YzgxNSBcdWI4MDhcdWJjYThcdWM3NTggXHVjODEwXHVjMjE4XHViOTdjIFx1YWMxMFx1YzE4Y1x1YzJkY1x1ZDBhNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4Y1x1ZDU3NFx1YzExYyBcdWFjMDEgXHViODA4XHViY2E4XHVjNzQ0IFx1ZDA3NFx1YjlhY1x1YzViNFx1ZDU2MCBcdWI1NGMgXHVjOGZjXHViMjk0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWM5OWRcdWFjMDBcdWQ1NThcdWFjOGMgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YjgwOFx1YmNhOFx1Yzc0NCBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NjAgXHViNTRjIFx1YzViYlx1YjI5NCBcdWM4MTBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYTg3IFx1YmM4OCBcdWFjMTBcdWMxOGNcdWMyZGNcdWQwYTRcdWJhNzQgXHViNDE4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM4MTBcdWMyMThcdWIyOTQgXHVkNTZkXHVjMGMxIFx1YzU5MVx1YzIxOFx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NThcdWFjZTAsIDFcdWI5Y2NcdWQwN2MgXHVhYzEwXHVjMThjXHVjMmRjXHVkMGE0XHViMjk0IFx1YWM4M1x1Yzc3NCAxXHViYzg4XHVjNzc0XHViMmU0LiBcdWQ1NmRcdWMwYzEgXHViMmY1XHVjNzc0IFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWI5Y2MgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4MTVcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCZuYnNwOzxzcGFuIHN0eWxlPVwiY29sb3I6cmdiKDg1LCA4NSwgODUpOyBmb250LWZhbWlseTpvcGVuIHNhbnMsaGVsdmV0aWNhIG5ldWUsaGVsdmV0aWNhLGFyaWFsLGFwcGxlIHNkIGdvdGhpYyBuZW8sbm90byBzYW5zIGNqayBrcixub3RvIHNhbnMga3IsXHViMDk4XHViMjE0XHViYzE0XHViOTc4XHVhY2UwXHViNTE1LFx1YjA5OFx1YjIxNFx1YWNlMFx1YjUxNSxuYW51bWdvdGhpYyxcdWI5ZDFcdWM3NDBcdWFjZTBcdWI1MTUsbWFsZ3VuIGdvdGhpYyxuYW51bSBnb3RoaWMsc2Fucy1zZXJpZlwiPlx1YzgxMFx1YzIxOFx1Yjk3YyBcdWIwYjRcdWI5YWNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1YzczY1x1Yjg1YyBcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQ0IFx1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvc3Bhbj48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViODA4XHViY2E4XHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YjgwOFx1YmNhOFx1Yzc0NCBcdWQwNzRcdWI5YWNcdWM1YjRcdWQ1NThcdWJhNzQgXHVjNWJiXHViMjk0IFx1YzgxMFx1YzIxOFx1YWMwMCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjgwOFx1YmNhOFx1YmQ4MFx1ZDEzMCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViODA4XHViY2E4XHVhZTRjXHVjOWMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzgxMFx1YzIxOFx1YjI5NCAyMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4MTBcdWMyMThcdWI5N2MgXHViYTg3IFx1YmM4OCBcdWFjMTBcdWMxOGNcdWMyZGNcdWQwYTRcdWJhNzQgXHViNDE4XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODQ3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUkFaSU5FIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBoYXMgZGV2ZWxvcGVkIGhpcyBvd24gdmlkZW8gZ2FtZS4gVGhlIGdhbWUgaGFzIE4gbGV2ZWxzIGFuZCBlYWNoIHN1Y2Nlc3NmdWxseSBjb21wbGV0ZWQgbGV2ZWwgaXMgd29ydGggYSBjZXJ0YWluIG51bWJlciBvZiBwb2ludHMsIHdoaWNoIGFkZCB1cCB0byB0aGUgcGxheWVyJnJzcXVvO3MgdG90YWwgc2NvcmUgb24gYW4gb25saW5lIHJhbmsgbGlzdCBvZiBhbGwgcGxheWVycy4gTWlya28gaGFzIG9yZGVyZWQgaGlzIGxldmVscyBieSBkaWZmaWN1bHR5IGZyb20gdGhlIGVhc2llc3QgdG8gdGhlIG1vc3QgZGlmZmljdWx0LCBidXQgaGUgaGFzIG1hZGUgYSBtaXN0YWtlIGFuZCBtYWRlIHNvbWUgZGlmZmljdWx0IGxldmVscyB3b3J0aCBsZXNzIHBvaW50cyB0aGFuIHNvbWUgb2YgdGhlIGVhc2llciBvbmVzLjxcL3A+XHJcblxyXG48cD5UbyBvdmVyY29tZSB0aGlzIHByb2JsZW0sIE1pcmtvIGhhcyBkZWNpZGVkIHRvIHJlZHVjZSB0aGUgbnVtYmVyIG9mIHBvaW50cyBmb3IgY2VydGFpbiBsZXZlbHMgd2l0aCB0aGUgZ29hbCBvZiBtYWtpbmcgdGhlIHBvaW50IHNlcXVlbmNlIHN0cmljdGx5IGluY3JlYXNpbmcgKHNvIGluIHRoZSBlbmQgZWFzaWVyIGxldmVscyBhcmUgd29ydGggbGVzcyBwb2ludHMgdGhhbiB0aGUgZGlmZmljdWx0IG9uZXMpLjxcL3A+XHJcblxyXG48cD5IZWxwIE1pcmtvIGZpeCBoaXMgdmlkZW8gZ2FtZSBpbiBzdWNoIGEgd2F5IHRoYXQgdGhlIHRvdGFsIG51bWJlciBvZiBwb2ludHMgcmVkdWNlZCBpcyBtaW5pbWFsLiBGaW5hbCBwb2ludHMgaGF2ZSB0byBiZSBwb3NpdGl2ZS4gWW91IGNhbiBhc3N1bWUgdGhhdCBhIHNvbHV0aW9uIGV4aXN0cyBmb3IgZWFjaCB0ZXN0IGNhc2U8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwKSwgdGhlIG51bWJlciBvZiBsZXZlbHMuPFwvcD5cclxuXHJcbjxwPlRoZSBuZXh0IE4gbGluZXMgY29udGFpbiBwb3NpdGl2ZSBpbnRlZ2VycyBsZXNzIHRoYW4gMjAgMDAwLCB0aGUgbnVtYmVyIG9mIHBvaW50cyB0aGF0IE1pcmtvIGhhcyBhc3NvY2lhdGVkIHdpdGggZWFjaCBsZXZlbCwgZnJvbSB0aGUgZmlyc3QgdG8gdGhlIGxhc3QgbGV2ZWwuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBvbmUgbnVtYmVyIC0gdGhlIG1pbmltdW0gdG90YWwgbnVtYmVyIG9mIHBvaW50cyBNaXJrbyBoYXMgdG8gc3VidHJhY3QgdG8gZnVsZmlsbCByZXF1aXJlbWVudHMgZ2l2ZW4gaW4gdGhlIHRhc2sgc3RhdGVtZW50IGFib3ZlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #6 3번