시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 602 166 131 27.696%

문제

월드피자 원주 지점에서 N개의 피자 반죽을 오븐에 넣고 구우려고 한다. 그런데, 월드피자에서 만드는 피자 반죽은 지름이 제각각이다. 그런가하면, 월드피자에서 사용하는 오븐의 모양도 몹시 오묘하다. 이 오븐은 깊은 관처럼 생겼는데, 관의 반지름이 깊이에 따라 들쭉날쭉하게 변한다. 아래는 오븐의 단면 예시이다.

피자 반죽은 완성되는 순서대로 오븐에 들어간다. 이렇게 N개의 피자가 오븐에 모두 들어가고 나면, 맨 위의 피자가 얼마나 깊이 들어가 있는지가 궁금하다. 이를 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1<=D, N<=300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 반지름이 차례대로 주어진다. 셋째 줄에는 피자 반죽이 완성되는 순서대로, 그 각각의 지름이 주어진다. 오븐의 반지름이나 피자 반죽의 지름은 10억 이하의 자연수이다.

출력

첫째 줄에, 마지막 피자 반죽이 위치를 출력한다. 오븐의 최상단이 1이고, 최하단 가장 깊은 곳이 D이 된다. 만약 피자가 모두 오븐에 들어가지 않는다면, 0을 출력한다.

예제 입력 1

7 3
5 6 4 3 6 2 3
3 2 5

예제 출력 1

2

힌트

W3sicHJvYmxlbV9pZCI6IjE3NTYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWM3OTAgXHVhZDdkXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM2ZDRcdWI0ZGNcdWQ1M2NcdWM3OTAgXHVjNmQwXHVjOGZjIFx1YzljMFx1YzgxMFx1YzVkMFx1YzExYyBOXHVhYzFjXHVjNzU4IFx1ZDUzY1x1Yzc5MCBcdWJjMThcdWM4ZmRcdWM3NDQgXHVjNjI0XHViZTEwXHVjNWQwIFx1YjEyM1x1YWNlMCBcdWFkNmNcdWM2YjBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZjBcdWIzNzAsIFx1YzZkNFx1YjRkY1x1ZDUzY1x1Yzc5MFx1YzVkMFx1YzExYyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHVkNTNjXHVjNzkwIFx1YmMxOFx1YzhmZFx1Yzc0MCBcdWM5YzBcdWI5ODRcdWM3NzQgXHVjODFjXHVhYzAxXHVhYzAxXHVjNzc0XHViMmU0LiBcdWFkZjhcdWI3ZjBcdWFjMDBcdWQ1NThcdWJhNzQsIFx1YzZkNFx1YjRkY1x1ZDUzY1x1Yzc5MFx1YzVkMFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWIyOTQgXHVjNjI0XHViZTEwXHVjNzU4IFx1YmFhOFx1YzU5MVx1YjNjNCBcdWJhYjlcdWMyZGMgXHVjNjI0XHViYjE4XHVkNTU4XHViMmU0LiBcdWM3NzQgXHVjNjI0XHViZTEwXHVjNzQwIFx1YWU0YVx1Yzc0MCBcdWFkMDBcdWNjOThcdWI3ZmMgXHVjMGRkXHVhY2JjXHViMjk0XHViMzcwLCBcdWFkMDBcdWM3NTggXHViYzE4XHVjOWMwXHViOTg0PHNwYW4gc3R5bGU9XCJsaW5lLWhlaWdodDoxLjZlbVwiPlx1Yzc3NCBcdWFlNGFcdWM3NzRcdWM1ZDAgXHViNTMwXHViNzdjIFx1YjRlNFx1Y2I0OVx1YjBhMFx1Y2I0OVx1ZDU1OFx1YWM4YyBcdWJjYzBcdWQ1NWNcdWIyZTQuIFx1YzU0NFx1Yjc5OFx1YjI5NCBcdWM2MjRcdWJlMTBcdWM3NTggXHViMmU4XHViYTc0IFx1YzYwOFx1YzJkY1x1Yzc3NFx1YjJlNC48XC9zcGFuPjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvSnVkZ2VPbmxpbmVcL3VwbG9hZFwvMjAxMDA2XC9waXp6MS5QTkdcIiBzdHlsZT1cImhlaWdodDoxNTdweDsgd2lkdGg6MjY4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkNTNjXHVjNzkwIFx1YmMxOFx1YzhmZFx1Yzc0MCBcdWM2NDRcdWMxMzFcdWI0MThcdWIyOTQgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzYyNFx1YmUxMFx1YzVkMCBcdWI0ZTRcdWM1YjRcdWFjMDRcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBOXHVhYzFjXHVjNzU4IFx1ZDUzY1x1Yzc5MFx1YWMwMCBcdWM2MjRcdWJlMTBcdWM1ZDAgXHViYWE4XHViNDUwIFx1YjRlNFx1YzViNFx1YWMwMFx1YWNlMCBcdWIwOThcdWJhNzQsIFx1YjllOCBcdWM3MDRcdWM3NTggXHVkNTNjXHVjNzkwXHVhYzAwIFx1YzViY1x1YjljOFx1YjA5OCBcdWFlNGFcdWM3NzQgXHViNGU0XHVjNWI0XHVhYzAwIFx1Yzc4OFx1YjI5NFx1YzljMFx1YWMwMCBcdWFkODFcdWFlMDhcdWQ1NThcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBcdWM1NGNcdWM1NDRcdWIwYjRcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNjI0XHViZTEwXHVjNzU4IFx1YWU0YVx1Yzc3NCBEXHVjNjQwIFx1ZDUzY1x1Yzc5MCBcdWJjMThcdWM4ZmRcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVhY2Y1XHViYzMxXHVjNzQ0IFx1YzBhY1x1Yzc3NFx1YzVkMCBcdWI0NTBcdWFjZTAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSZsdDs9RCwgTiZsdDs9MzAwLDAwMCkgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2MjRcdWJlMTBcdWM3NTggXHVjZDVjXHVjMGMxXHViMmU4XHViZDgwXHVkMTMwIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBcdWFlNGFcdWM3NzRcdWM1ZDAgXHViNTMwXHViOTc4IFx1YzYyNFx1YmUxMFx1Yzc1OCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjMTRiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ1M2NcdWM3OTAgXHViYzE4XHVjOGZkXHVjNzc0IFx1YzY0NFx1YzEzMVx1YjQxOFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMsIFx1YWRmOCBcdWFjMDFcdWFjMDFcdWM3NTggXHVjOWMwXHViOTg0XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNjI0XHViZTEwXHVjNzU4IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc3NFx1YjA5OCBcdWQ1M2NcdWM3OTAgXHViYzE4XHVjOGZkXHVjNzU4IFx1YzljMFx1Yjk4NFx1Yzc0MCAxMFx1YzViNSBcdWM3NzRcdWQ1NThcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAsIFx1YjljOFx1YzljMFx1YjljOSBcdWQ1M2NcdWM3OTAgXHViYzE4XHVjOGZkXHVjNzc0IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzYyNFx1YmUxMFx1Yzc1OCBcdWNkNWNcdWMwYzFcdWIyZThcdWM3NzQgMVx1Yzc3NFx1YWNlMCwgXHVjZDVjXHVkNTU4XHViMmU4IFx1YWMwMFx1YzdhNSBcdWFlNGFcdWM3NDAgXHVhY2YzXHVjNzc0IERcdWM3NzQgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVkNTNjXHVjNzkwXHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWM2MjRcdWJlMTBcdWM1ZDAgXHViNGU0XHVjNWI0XHVhYzAwXHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNFx1YmE3NCwgMFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC9KdWRnZU9ubGluZVwvdXBsb2FkXC8yMDEwMDZcL3BpejIuUE5HXCIgc3R5bGU9XCJoZWlnaHQ6MTU2cHg7IHdpZHRoOjI2NnB4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxNzU2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIERpc2tzIiwiZGVzY3JpcHRpb24iOiI8cD5Gb3IgaGlzIGJpcnRoZGF5IHByZXNlbnQgbGl0dGxlIEpvaG5ueSBoYXMgcmVjZWl2ZWQgZnJvbSBoaXMgcGFyZW50cyBhIG5ldyBwbGF5dGhpbmcgd2hpY2ggY29uc2lzdHMgb2YgYSB0dWJlIGFuZCBhIHNldCBvZiBkaXNrcy4gVGhlIGFmb3JlbWVudGlvbmVkIHR1YmUgaXMgb2YgdW51c3VhbCBzaGFwZS4gTmFtZWx5LCBpdCBpcyBtYWRlIG9mIGEgY2VydGFpbiBudW1iZXIgb2YgY3lsaW5kZXJzIChvZiBlcXVhbCBoZWlnaHQpIHdpdGggYXBlcnR1cmVzIG9mIGRpZmZlcmVudCBkaWFtZXRlcnMgY2FydmVkIGNvYXhpYWxseSB0aHJvdWdoIHRoZW0uIFRoZSB0dWJlIGlzIGNsb3NlZCBhdCB0aGUgYm90dG9tLCBvcGVuIGF0IHRoZSB0b3AuIEFuIGV4ZW1wbGFyeSB0dWJlIGNvbnNpc3Rpbmcgb2YgY3lsaW5kZXJzIHdob3NlIGFwZXJ0dXJlcyBoYXZlIHRoZSBkaWFtZXRlcnM6IDVjbSwgNmNtLCA0Y20sIDNjbSwgNmNtLCAyY20gYW5kIDNjbSBpcyBwcmVzZW50ZWQgaW4gdGhlIGltYWdlIGJlbG93LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2tyYTEucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjA2cHg7IHdpZHRoOjM1MHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlRoZSBkaXNrcyBpbiBKb2hubnkmIzM5O3MgcGxheXRoaW5nIGFyZSBjeWxpbmRlcnMgb2YgZGlmZmVyZW50IGRpYW1ldGVycyBhbmQgaGVpZ2h0IGVxdWFsIHRvIHRob3NlIGZvcm1pbmcgdGhlIHR1YmUuPFwvcD5cclxuXHJcbjxwPkpvaG5ueSBoYXMgaW52ZW50ZWQgYSBmb2xsb3dpbmcgZ2FtZTogaGF2aW5nIGEgY2VydGFpbiBzZXQgb2YgZGlza3MgYXQgaGlzIGRpc3Bvc2FsLCBoZSBzZWVrcyB0byBmaW5kIHdoYXQgZGVwdGggdGhlIGxhc3Qgb2YgdGhlbSB3b3VsZCBzdG9wIGF0LCBhc3N1bWluZyB0aGF0IHRoZXkgYXJlIGJlaW5nIHRocm93biBpbnRvIHRoZSBjZW50cmUgb2YgdGhlIHR1YmUuIElmLCBmb3IgaW5zdGFuY2UsIHdlIHdlcmUgdG8gdGhyb3cgZGlza3Mgb2YgY29uc2VjdXRpdmUgZGlhbWV0ZXJzOiAzY20sIDJjbSBhbmQgNWNtLCB3ZSB3b3VsZCBvYnRhaW4gdGhlIGZvbGxvd2luZyBzaXR1YXRpb246PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wva3JhMi5wbmdcIiBzdHlsZT1cImhlaWdodDoyMDZweDsgd2lkdGg6MzUwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+QXMgeW91IGNhbiBzZWUsIHVwb24gYmVpbmcgdGhyb3duIGluLCBldmVyeSBkaXNrIGZhbGxzIHVudGlsIGl0IGdldHMgc3R1Y2sgKHdoaWNoIG1lYW5zIHRoYXQgaXQgbGllcyBhdG9wIGEgY3lsaW5kZXIsIGFwZXJ0dXJlIG9mIHdoaWNoIGhhcyBhIGRpYW1ldGVyIHNtYWxsZXIgdGhhbiB0aGUgZGlhbWV0ZXIgb2YgdGhlIGRpc2spIG9yIGl0IGlzIHN0b3BwZWQgYnkgYW4gb2JzdGFjbGU6IHRoZSBib3R0b20gb2YgdGhlIHR1YmUgb3IgYW5vdGhlciBkaXNrLCB3aGljaCBoYXMgYWxyZWFkeSBzdG9wcGVkLjxcL3A+XHJcblxyXG48cD5UaGUgZ2FtZSBiZWluZyBkaWZmaWN1bHQsIEpvaG5ueSBjb25zdGFudGx5IGFza3MgaGlzIHBhcmVudHMgZm9yIGhlbHAuIEFzIEpvaG5ueSYjMzk7cyBwYXJlbnRzIGRvIG5vdCBsaWtlIHN1Y2ggaW50ZWxsZWN0dWFsIGdhbWVzLCB0aGV5IGhhdmUgYXNrZWQgeW91IC0gYW4gYWNxdWFpbnRhbmNlIG9mIHRoZWlycyBhbmQgYSBwcm9ncmFtbWVyIC0gdG8gd3JpdGUgYSBwcm9ncmFtbWUgd2hpY2ggd2lsbCBwcm92aWRlIHRoZW0gd2l0aCBhbnN3ZXJzIHRvIEpvaG5ueSYjMzk7cyBxdWVzdGlvbnMuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbW1lIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIHRoZSBkZXNjcmlwdGlvbiBvZiB0aGUgdHViZSBhbmQgdGhlIGRpc2tzIHdoaWNoIEpvaG5ueSB3aWxsIHRocm93IGludG8gaXQgZnJvbSB0aGUgc3RhbmRhcmQgaW5wdXQsPFwvbGk+XHJcblx0PGxpPmNvbXB1dGVzIHRoZSBkZXB0aCB3aGljaCB0aGUgbGFzdCBkaXNrIHRocm93biBieSBKb2hubnkgc3RvcHMgYXQsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgb3V0Y29tZSB0byB0aGUgc3RhbmRhcmQgb3V0cHV0LjxcL2xpPlxyXG48XC91bD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiB0aGUgc3RhbmRhcmQgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIG4gYW5kIG0gKDEgJmxlOyBuLG0gJmxlOyAzMDAgMDAwKSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgc3BhY2UgYW5kIGRlbm90aW5nIHRoZSBoZWlnaHQgb2YgSm9obm55JiMzOTtzIHR1YmUgKHRoZSBudW1iZXIgb2YgY3lsaW5kZXJzIGl0IGNvbXByaXNlcykgYW5kIHRoZSBudW1iZXIgb2YgZGlza3MgSm9obm55IGludGVuZHMgdG8gdGhyb3cgaW50byBpdCwgcmVzcGVjdGl2ZWx5LiBUaGUgc2Vjb25kIGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIG4gaW50ZWdlcnMgcjxzdWI+MTxcL3N1Yj4scjxzdWI+MjxcL3N1Yj4sLi4uLHI8c3ViPm48XC9zdWI+ICgxICZsZTsgcjxzdWI+aTxcL3N1Yj4gJmxlOyAxIDAwMCAwMDAgMDAwIGZvciAxICZsZTsgaSAmbGU7IG4pIHNlcGFyYXRlZCBieSBzaW5nbGUgc3BhY2VzIGFuZCBkZW5vdGluZyB0aGUgZGlhbWV0ZXJzIG9mIHRoZSBhcGVydHVyZXMgY2FydmVkIHRocm91Z2ggdGhlIGNvbnNlY3V0aXZlIGN5bGluZGVycyAoaW4gdG9wLWRvd24gb3JkZXIpLCB3aGljaCB0aGUgdHViZSBjb25zaXN0cyBvZi4gVGhlIHRoaXJkIGxpbmUgY29udGFpbnMgbSBpbnRlZ2VycyBrPHN1Yj4xPFwvc3ViPixrPHN1Yj4yPFwvc3ViPiwuLi4sazxzdWI+bTxcL3N1Yj4gKDEgJmxlOyBrPHN1Yj5qPFwvc3ViPiAmbGU7IDEgMDAwIDAwMCAwMDAgZm9yIDEgJmxlOyBqICZsZTsgbSkgc2VwYXJhdGVkIGJ5IHNpbmdsZSBzcGFjZXMgYW5kIGRlbm90aW5nIHRoZSBkaWFtZXRlcnMgb2YgY29uc2VjdXRpdmUgZGlza3Mgd2hpY2ggSm9obm55IGludGVuZHMgdG8gdGhyb3cgaW50byB0aGUgdHViZS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCBzaG91bGQgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyIGRlbm90aW5nIHRoZSBkZXB0aCB3aGljaCB0aGUgbGFzdCBkaXNrIHN0b3BzIGF0LiBTaG91bGQgdGhlIGRpc2sgbm90IGZhbGwgaW50byB0aGUgdHViZSBhdCBhbGwsIHRoZSBhbnN3ZXIgc2hvdWxkIGJlIDAuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

Olympiad > Polish Olympiad in Informatics > POI 2005/2006 > Stage 1 1번

  • 문제를 번역한 사람: author10
  • 문제의 오타를 찾은 사람: mic1021