문제
개구리 왕눈이는 N개의 연꽃잎이 있는 연못에 살고 있다. 연꽃잎은 1부터 N까지 차례대로 번호가 매겨져 있다. 연못을 위에서 봤을 때 2차원 평면에 연꽃잎이 (x,y) 좌표에 떠 있는 것 처럼 보인다. 왕눈이는 대각선으로 뛰는 것과 음의 방향으로 뛰는 것을 무서워 한다. 좀 더 자세히 말하자면 (x 1 ,y1 )에서 (x2 ,y2 )로 뛰기 위해서는 아래 두 조건 중 하나를 만족해야한다.
x2 > x1 이고 y2 = y1
y2 > y1 이고 x2 = x1
각 연꽃잎 마다 일정 수의 파리가 있고, 왕눈이는 파리를 먹으며 힘을 회복한다.
왕눈이가 한 번 연꽃잎을 이동하기 위해서는 K 만큼 힘이 든다. 왕눈이는 처음 1번 연꽃잎에서 시작하여 N번 연꽃잎으로 이동하려고 한다. 다만, 도착하고 난 뒤 힘의 최대이고 싶어한다. 처음 왕눈이가 가진 힘은 0 이다. 힘은 항상 0 이상 이어야 한다.
왕눈이를 도와 연꽃잎 사이를 이동하는 경로를 출력하는 프로그램을 작성하시오.
출력
첫 줄에 N번 연꽃잎에 도착 한 뒤 최대 힘의 양을 출력한다.
두 번째 줄에는 1번 연꽃잎과 N번 연꽃잎을 포함하여 방문한 연꽃잎의 수 L을 출력한다.
다음 L개의 줄에 방문한 연꽃잎의 좌표들을 차례대로 출력한다.
만약, 가능한 답이 여러 가지인 경우 그 중 아무거나 하나 출력한다.
예제 출력 1
복사
5
4
1 1
2 1
2 3
3 3
W3sicHJvYmxlbV9pZCI6IjI5ODkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWFkNmNcdWI5YWMgXHVjNjU1XHViMjA4XHVjNzc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWFjMWNcdWFkNmNcdWI5YWMgXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IE5cdWFjMWNcdWM3NTggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzc0IFx1Yzc4OFx1YjI5NCBcdWM1ZjBcdWJhYmJcdWM1ZDAgXHVjMGI0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YjllNFx1YWNhOFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YzVmMFx1YmFiYlx1Yzc0NCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHViZDI0XHVjNzQ0IFx1YjU0YyAyXHVjYzI4XHVjNmQwIFx1ZDNjOVx1YmE3NFx1YzVkMCZuYnNwO1x1YzVmMFx1YWY0M1x1Yzc4ZVx1Yzc3NCAoeCx5KSBcdWM4OGNcdWQ0NWNcdWM1ZDAgXHViNWEwIFx1Yzc4OFx1YjI5NCBcdWFjODMgXHVjYzk4XHViN2ZjIFx1YmNmNFx1Yzc3OFx1YjJlNC4gXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IFx1YjMwMFx1YWMwMVx1YzEyMFx1YzczY1x1Yjg1YyBcdWI2ZjBcdWIyOTQgXHVhYzgzXHVhY2ZjIFx1Yzc0Y1x1Yzc1OCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHViNmYwXHViMjk0IFx1YWM4M1x1Yzc0NCBcdWJiMzRcdWMxMWNcdWM2Y2MgXHVkNTVjXHViMmU0LiBcdWM4ODAgXHViMzU0IFx1Yzc5MFx1YzEzOFx1ZDc4OCBcdWI5ZDBcdWQ1NThcdWM3OTBcdWJhNzQgKHggPHN1Yj4xPFwvc3ViPix5PHN1Yj4xPFwvc3ViPilcdWM1ZDBcdWMxMWMgKHg8c3ViPjI8XC9zdWI+LHk8c3ViPjI8XC9zdWI+KVx1Yjg1YyBcdWI2ZjBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjXHViMjk0IFx1YzU0NFx1Yjc5OCBcdWI0NTAgXHVjODcwXHVhYzc0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWI5N2MgXHViOWNjXHVjODcxXHVkNTc0XHVjNTdjXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPng8c3ViPjI8XC9zdWI+ICZndDsgeDxzdWI+MTxcL3N1Yj4gXHVjNzc0XHVhY2UwIHk8c3ViPjI8XC9zdWI+ID0geTxzdWI+MTxcL3N1Yj48XC9saT5cclxuXHQ8bGk+eTxzdWI+MjxcL3N1Yj4gJmd0OyB5PHN1Yj4xPFwvc3ViPiBcdWM3NzRcdWFjZTAgeDxzdWI+MjxcL3N1Yj4gPSB4PHN1Yj4xPFwvc3ViPjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YWMwMSBcdWM1ZjBcdWFmNDNcdWM3OGUgXHViOWM4XHViMmU0IFx1Yzc3Y1x1YzgxNSBcdWMyMThcdWM3NTggXHVkMzBjXHViOWFjXHVhYzAwIFx1Yzc4OFx1YWNlMCwgXHVjNjU1XHViMjA4XHVjNzc0XHViMjk0IFx1ZDMwY1x1YjlhY1x1Yjk3YyBcdWJhMzlcdWM3M2NcdWJhNzAgXHVkNzk4XHVjNzQ0IFx1ZDY4Y1x1YmNmNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjU1XHViMjA4XHVjNzc0XHVhYzAwIFx1ZDU1YyBcdWJjODggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzQ0IFx1Yzc3NFx1YjNkOVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWNcdWIyOTQgSyBcdWI5Y2NcdWQwN2MgXHVkNzk4XHVjNzc0Jm5ic3A7XHViNGUwXHViMmU0LiBcdWM2NTVcdWIyMDhcdWM3NzRcdWIyOTQgXHVjYzk4XHVjNzRjIDFcdWJjODggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzVlYyBOXHViYzg4IFx1YzVmMFx1YWY0M1x1Yzc4ZVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWIyZTRcdWI5Y2MsIFx1YjNjNFx1Y2MyOVx1ZDU1OFx1YWNlMCBcdWIwOWMgXHViNGE0IFx1ZDc5OFx1Yzc1OCBcdWNkNWNcdWIzMDBcdWM3NzRcdWFjZTAmbmJzcDtcdWMyZjZcdWM1YjRcdWQ1NWNcdWIyZTQuIFx1Y2M5OFx1Yzc0YyBcdWM2NTVcdWIyMDhcdWM3NzRcdWFjMDAgXHVhYzAwXHVjOWM0IFx1ZDc5OFx1Yzc0MCAwIFx1Yzc3NFx1YjJlNC4gXHVkNzk4XHVjNzQwIFx1ZDU2ZFx1YzBjMSAwIFx1Yzc3NFx1YzBjMSBcdWM3NzRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2NTVcdWIyMDhcdWM3NzRcdWI5N2MgXHViM2M0XHVjNjQwIFx1YzVmMFx1YWY0M1x1Yzc4ZSBcdWMwYWNcdWM3NzRcdWI5N2MgXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1ZDU1YyBcdWJjODggXHVjNzc0XHViM2Q5XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWQ3OTggS1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuJm5ic3A7KDIgJmxlOyBOICZsZTsgMzAwIDAwMCwgMSAmbGU7IEsgJmxlOyAxMDAwKTxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDAgXHVhYzc4XHVjY2QwIFx1YWMwMSBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM3NTggXHVjODhjXHVkNDVjIFgsIFlcdWM2NDAgXHVkMzBjXHViOWFjXHVjNzU4IFx1YzU5MSBGXHVhYzAwJm5ic3A7XHVjYzI4XHViODQwXHViMzAwXHViODVjJm5ic3A7XHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBpKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWM4OGNcdWQ0NWNcdWM2NDAgXHVkMzBjXHViOWFjXHVjNzU4IFx1YzU5MVx1Yzc0MCZuYnNwO2lcdWJjODggXHVjNWYwXHVhZjQzXHVjNzhlXHVjNWQwIFx1YWQwMFx1ZDU1YyBcdWM4MTVcdWJjZjRcdWM3NzRcdWIyZTQuIFx1YzVmMFx1YWY0M1x1Yzc4ZVx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YjJlNC4mbmJzcDsoMCAmbGU7IFgsIFkgJmxlOyAxMDAgMDAwLCAwICZsZTsgRiAmbGU7IDEwMDApPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCZuYnNwO1x1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViM2M0XHViODVkIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwJm5ic3A7Tlx1YmM4OCBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM1ZDAgXHViM2M0XHVjYzI5IFx1ZDU1YyBcdWI0YTQgXHVjZDVjXHViMzAwJm5ic3A7XHVkNzk4XHVjNzU4IFx1YzU5MVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCZuYnNwO1x1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgMVx1YmM4OCBcdWM1ZjBcdWFmNDNcdWM3OGVcdWFjZmMgTlx1YmM4OCBcdWM1ZjBcdWFmNDNcdWM3OGVcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVjNWVjJm5ic3A7XHViYzI5XHViYjM4XHVkNTVjIFx1YzVmMFx1YWY0M1x1Yzc4ZVx1Yzc1OCBcdWMyMTggTFx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBMXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWJjMjlcdWJiMzhcdWQ1NWMgXHVjNWYwXHVhZjQzXHVjNzhlXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjRlNFx1Yzc0NCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5Y2NcdWM1N2QsIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIyZjVcdWM3NzQgXHVjNWVjXHViN2VjJm5ic3A7XHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMCBcdWFkZjggXHVjOTExIFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI5ODkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJCQVJJQ0EiLCJkZXNjcmlwdGlvbiI6IjxwPkJhcmljYSBpcyBhbiB1bnVzdWFsIGZyb2cuIFNoZSBsaXZlcyBpbiBhIHBvbmQgd2hlcmUgTiBwbGFudHMgZmxvYXQgb24gdGhlIHN1cmZhY2Ugb2YgdGhlIHdhdGVyLiBUaGUgcGxhbnRzIGFyZSBudW1iZXJlZCAxIHRocm91Z2ggTi4gV2hlbiB2aWV3aW5nIGZyb20gYWJvdmUsIHRoZSBsb2NhdGlvbiBvZiBlYWNoIHBsYW50IGlzIGdpdmVuIGJ5IGEgcGFpciBvZiBjb29yZGluYXRlcy4gV2hhdCBtYWtlcyBCYXJpY2EgdW51c3VhbCBpcyBoZXIgZmVhciBvZiBqdW1waW5nIGRpYWdvbmFsbHkgYW5kIGluIHRoZSBuZWdhdGl2ZSBkaXJlY3Rpb24uIE1vcmUgcHJlY2lzZWx5LCBzaGUgY2FuIGp1bXAgZnJvbSBhIHBsYW50IGF0IGNvb3JkaW5hdGVzICh4PHN1Yj4xPFwvc3ViPiwgeTxzdWI+MTxcL3N1Yj4pIHRvIGFub3RoZXIgYXQgY29vcmRpbmF0ZXMgKHg8c3ViPjI8XC9zdWI+LCB5PHN1Yj4yPFwvc3ViPikgb25seSBpZjombmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT54PHN1Yj4yPFwvc3ViPiAmZ3Q7IHg8c3ViPjE8XC9zdWI+IGFuZCB5PHN1Yj4yPFwvc3ViPiA9IHk8c3ViPjE8XC9zdWI+LCBvciZuYnNwOzxcL2xpPlxyXG5cdDxsaT55PHN1Yj4yPFwvc3ViPiAmZ3Q7IHk8c3ViPjE8XC9zdWI+IGFuZCB4PHN1Yj4yPFwvc3ViPiA9IHg8c3ViPjE8XC9zdWI+PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Rm9yIGVhY2ggcGxhbnQsIHdlIGtub3cgdGhlIG51bWJlciBvZiBmbGllcyBpbiBpdHMgaW1tZWRpYXRlIHZpY2luaXR5LiBCYXJpY2EgY2FuIHVzZSBoZXIgc3dpZnQgdG9uZ3VlIHRvIGVhdCBhbGwgZmxpZXMgbmVhciB0aGUgcGxhbnQgc2hlIGlzIGF0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5CYXJpY2EgYWJzb3JicyBvbmUgZW5lcmd5IHVuaXQgZm9yIGVhY2ggZmx5IHNoZSBlYXRzLCBhbmQgdXNlcyBLIGVuZXJneSB1bml0cyBmb3IgZWFjaCBqdW1wIHNoZSBtYWtlcy4gQmFyaWNhIGNhbiBub3QgbWFrZSBhIGp1bXAgaWYgc2hlIGRvZXNuJiMzOTt0IGhhdmUgZW5vdWdoIGVuZXJneSB1bml0cyBiZWZvcmVoYW5kLiZuYnNwOzxcL3A+XHJcblxyXG48cD5CYXJpY2Egd2FudHMgdG8gZ28gZnJvbSBwbGFudCAxIHRvIHBsYW50IE4gYW5kIGhhdmUgdGhlIGxhcmdlc3QgYW1vdW50IG9mIGVuZXJneSBwb3NzaWJsZSBhZnRlciBhcnJpdmluZy4gQmFyaWNhIGluaXRpYWxseSBoYXMgbm8gZW5lcmd5IGFuZCBtdXN0IGdhdGhlciBlbmVyZ3kgZm9yIGhlciBmaXJzdCBqdW1wIGZyb20gdGhlIGZsaWVzIGFyb3VuZCBwbGFudCAxLiZuYnNwOzxcL3A+XHJcblxyXG48cD5GaW5kIHRoZSBzZXF1ZW5jZSBvZiBwbGFudHMgQmFyaWNhIHNob3VsZCB0cmF2ZWwgdG8gYWNoaWV2ZSBoZXIgZ29hbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycyBOIGFuZCBLICgyICZsZTsgTiAmbGU7IDMwMCAwMDAsIDEgJmxlOyBLICZsZTsgMTAwMCkgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIFgsIFkgYW5kIEYgKDAgJmxlOyBYLCBZICZsZTsgMTAwIDAwMCwgMCAmbGU7IEYgJmxlOyAxMDAwKSBzZXBhcmF0ZWQgYnkgc3BhY2VzLCBtZWFuaW5nIHRoYXQgdGhlcmUgaXMgYSBwbGFudCBhdCBjb29yZGluYXRlcyAoWCwgWSkgd2l0aCBGIGZsaWVzIGFyb3VuZCBpdC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZpcnN0IHBsYW50IGluIHRoZSBpbnB1dCBpcyBwbGFudCAxLCB0aGUgc2Vjb25kIGlzIHBsYW50IDIgZXRjLiZuYnNwOzxcL3A+XHJcblxyXG48cD5ObyB0d28gcGxhbnRzIHdpbGwgc2hhcmUgdGhlIHNhbWUgcGFpciBvZiBjb29yZGluYXRlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhlIGlucHV0IGRhdGEgd2lsbCBndWFyYW50ZWUgdGhhdCBhIHNlcXVlbmNlIG9mIGp1bXBzLCBhbHRob3VnaCBub3QgbmVjZXNzYXJpbHkgdW5pcXVlLCB3aWxsIGFsd2F5cyBleGlzdC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIGZpbmFsIGVuZXJneSBsZXZlbCBvbiB0aGUgZmlyc3QgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T3V0cHV0IGFuIGludGVnZXIgTCwgdGhlIG51bWJlciBvZiBwbGFudHMgQmFyaWNhIHNob3VsZCB0cmF2ZWwsIGluY2x1ZGluZyBwbGFudHMgMSBhbmQgTi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+T24gdGhlIGZvbGxvd2luZyBMIGxpbmVzLCBvdXRwdXQgdGhlIHNlcXVlbmNlIG9mIHBsYW50cyBCYXJpY2Egc2hvdWxkIHRyYXZlbC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=
