시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 4337 938 628 20.892%

문제

N명의 아이들이 한 줄로 줄을 서서 놀이공원에서 1인승 놀이기구를 기다리고 있다. 이 놀이공원에는 총 M종류의 1인승 놀이기구가 있으며, 1번부터 M번까지 번호가 매겨져 있다.

모든 놀이기구는 각각 운행 시간이 정해져 있어서, 운행 시간이 지나면 탑승하고 있던 아이는 내리게 된다. 놀이 기구가 비어 있으면 현재 줄에서 가장 앞에 서 있는 아이가 빈 놀이기구에 탑승한다. 만일 여러 개의 놀이기구가 동시에 비어 있으면, 더 작은 번호가 적혀 있는 놀이기구를 먼저 탑승한다고 한다.

놀이기구가 모두 비어 있는 상태에서 첫 번째 아이가 놀이기구에 탑승한다고 할 때, 줄의 마지막 아이가 타게 되는 놀이기구의 번호를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1<= N<= 2,000,000,000)과 M(1<= M<= 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 이하의 자연수이며, 단위는 분이다.

출력

첫째 줄에 마지막 아이가 타게 되는 놀이기구의 번호를 출력한다.

예제 입력 1

22 5
1 2 3 4 5

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjE1NjEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIxODBcdWM3NzQgXHVhY2Y1XHVjNmQwIiwiZGVzY3JpcHRpb24iOiI8cD5OXHViYTg1XHVjNzU4IFx1YzU0NFx1Yzc3NFx1YjRlNFx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YzkwNFx1Yzc0NCBcdWMxMWNcdWMxMWMgXHViMTgwXHVjNzc0XHVhY2Y1XHVjNmQwXHVjNWQwXHVjMTFjIDFcdWM3NzhcdWMyYjkgXHViMTgwXHVjNzc0XHVhZTMwXHVhZDZjXHViOTdjIFx1YWUzMFx1YjJlNFx1YjlhY1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWIxODBcdWM3NzRcdWFjZjVcdWM2ZDBcdWM1ZDBcdWIyOTQgXHVjZDFkIE1cdWM4ODVcdWI5NThcdWM3NTggMVx1Yzc3OFx1YzJiOSBcdWIxODBcdWM3NzRcdWFlMzBcdWFkNmNcdWFjMDAgXHVjNzg4XHVjNzNjXHViYTcwLCAxXHViYzg4XHViZDgwXHVkMTMwIE1cdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWIxODBcdWM3NzRcdWFlMzBcdWFkNmNcdWIyOTQgXHVhYzAxXHVhYzAxIFx1YzZiNFx1ZDU4OSBcdWMyZGNcdWFjMDRcdWM3NzQgXHVjODE1XHVkNTc0XHVjODM4IFx1Yzc4OFx1YzViNFx1YzExYywgXHVjNmI0XHVkNTg5IFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM5YzBcdWIwOThcdWJhNzQgXHVkMGQxXHVjMmI5XHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjM1OCBcdWM1NDRcdWM3NzRcdWIyOTQgXHViMGI0XHViOWFjXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViMTgwXHVjNzc0IFx1YWUzMFx1YWQ2Y1x1YWMwMCBcdWJlNDRcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTc0IFx1ZDYwNFx1YzdhYyBcdWM5MDRcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1YzU1ZVx1YzVkMCBcdWMxMWMgXHVjNzg4XHViMjk0IFx1YzU0NFx1Yzc3NFx1YWMwMCBcdWJlNDggXHViMTgwXHVjNzc0XHVhZTMwXHVhZDZjXHVjNWQwIFx1ZDBkMVx1YzJiOVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNzdjIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHViMTgwXHVjNzc0XHVhZTMwXHVhZDZjXHVhYzAwIFx1YjNkOVx1YzJkY1x1YzVkMCBcdWJlNDRcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTc0LCBcdWIzNTQgXHVjNzkxXHVjNzQwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWM4MDFcdWQ2MDAgXHVjNzg4XHViMjk0IFx1YjE4MFx1Yzc3NFx1YWUzMFx1YWQ2Y1x1Yjk3YyBcdWJhM2NcdWM4MDAgXHVkMGQxXHVjMmI5XHVkNTVjXHViMmU0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMTgwXHVjNzc0XHVhZTMwXHVhZDZjXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWJlNDRcdWM1YjQgXHVjNzg4XHViMjk0IFx1YzBjMVx1ZDBkY1x1YzVkMFx1YzExYyBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzU0NFx1Yzc3NFx1YWMwMCBcdWIxODBcdWM3NzRcdWFlMzBcdWFkNmNcdWM1ZDAgXHVkMGQxXHVjMmI5XHVkNTVjXHViMmU0XHVhY2UwIFx1ZDU2MCBcdWI1NGMsIFx1YzkwNFx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjNTQ0XHVjNzc0XHVhYzAwIFx1ZDBjMFx1YWM4YyBcdWI0MThcdWIyOTQgXHViMTgwXHVjNzc0XHVhZTMwXHVhZDZjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTigxJmx0Oz0gTiZsdDs9IDIsMDAwLDAwMCwwMDApXHVhY2ZjIE0oMSZsdDs9IE0mbHQ7PSAxMCwwMDApXHVjNzc0IFx1YmU0OFx1Y2U3OFx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViMTgwXHVjNzc0XHVhZTMwXHVhZDZjXHVjNzU4IFx1YzZiNFx1ZDU4OSBcdWMyZGNcdWFjMDRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IE1cdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzZiNFx1ZDU4OSBcdWMyZGNcdWFjMDRcdWM3NDAgMSBcdWM3NzRcdWMwYzEgMzAgXHVjNzc0XHVkNTU4XHVjNzU4IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YmE3MCwgXHViMmU4XHVjNzA0XHViMjk0IFx1YmQ4NFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljOFx1YzljMFx1YjljOSBcdWM1NDRcdWM3NzRcdWFjMDAgXHVkMGMwXHVhYzhjIFx1YjQxOFx1YjI5NCBcdWIxODBcdWM3NzRcdWFlMzBcdWFkNmNcdWM3NTggXHViYzg4XHVkNjM4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNTYxIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTFVOQSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlcmUgYXJlIE0gY2FycyBvbiBhIHJpZGUgaW4gYW4gYW11c2VtZW50IHBhcmssIG51bWJlcmVkIDEgdG8gTSwgYW5kIE4gY2hpbGRyZW4gYXJlIHdhaXRpbmcgaW4gYSBxdWV1ZSB0byBlbnRlciB0aGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIGNhciBoYXMgaXRzIHJpZGUgZHVyYXRpb24gKG1heGltdW0gMzAgbWludXRlcykgYW5kIGNhbiBob3N0IG9ubHkgb25lIGNoaWxkIGF0IGEgdGltZS4gT25jZSBhIGNhciBpcyBlbXB0eSwgdGhlIG5leHQgY2hpbGQgaW4gcXVldWUgZW50ZXJzIGl0LiBJZiB0d28gY2FycyBhcmUgZW1wdHkgYXQgdGhlIHNhbWUgdGltZSwgdGhlIGNoaWxkIGVudGVycyB0aGUgb25lIGhhdmluZyBhIHNtYWxsZXIgbnVtYmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGNhbGN1bGF0ZSBudW1iZXIgb2YgdGhlIGNhciB0aGUgbGFzdCBjaGlsZCBpbiBxdWV1ZSB3aWxsIGVudGVyLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGZpbGUgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIE0gc2VwYXJhdGVkIGJ5IGEgd2hpdGVzcGFjZS4gTiBpcyB0aGUgbnVtYmVyIG9mIGNoaWxkcmVuIGluIHF1ZXVlIGFuZCBNIGlzIG51bWJlciBvZiBjYXJzIG9uIGEgcmlkZSwgMSAmbGU7IE4gJmxlOyAyLDAwMCwwMDAsMDAwOyAxICZsZTsgTSAmbGU7IDEwMDAwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgbmV4dCBsaW5lIGNvbnNpc3RzIG9mIE0gaW50ZWdlcnMgc2VwYXJhdGVkIGJ5IHdoaXRlc3BhY2VzLiBUaGVzZSBpbnRlZ2VycyByZXByZXNlbnQgZHVyYXRpb25zIG9mIHJpZGVzIGZvciBlYWNoIG9mIE0gY2FycyBnaXZlbiBpbiBtaW51dGVzLiBFYWNoIG9mIHRoZXNlIG51bWJlcnMgd2lsbCBiZSBub3QgbGVzcyB0aGFuIDEgYW5kIG5vdCBncmVhdGVyIHRoYW4gMzAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCB0aGUgb25seSBsaW5lIG9mIHRoZSBvdXRwdXQgZmlsZSBzaG91bGQgY29udGFpbiB0aGUgbnVtYmVyIG9mIHRoZSBjYXIgYXMgZGVmaW5lZCBhYm92ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2003 > Regional Competition - Seniors 3번