시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 46 13 12 32.432%

문제

직교좌표로 이루어진 평면 위에 터널이 그려져있다.

터널의 천장은 (0,1)에서 시작해 (N,1)에서 끝난다.

터널의 바닥은 (0,-1)에서 시작해 (N,-1)에서 끝난다.

터널을 통과하는 경로는 (0,0)에서 시작해 (N,0)에서 끝난다.

천장, 바닥, 경로는 모두 x축 또는 y축에 평행한 선분이 이어진 형태이며, 모든 코너는 정수 좌표이고, 다음 선분의 x좌표는 이전 선분의 x선분보다 크거나 같다.

천장과 바닥의 y좌표는 각각 -1000에서 1000사이의 정수이다.

경로는 천장이나 바닥과 닿아서는 안되며, 코너에서도 천장이나 바닥과 닿아서는 안 된다.

터널의 예제는 주어진 그림과 같다. 천장과 바닥은 실선으로, 경로는 점선으로 그려져있다.

터널을 통과하는 최단 경로를 찾는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 터널의 너비 N이 주어진다.

두 번째 줄에는 천장의 y좌표가 N개의 정수로 왼쪽부터 오른쪽으로 주어진다.

세 번째 줄에는 바닥의 y좌표가 N개의 정수로 왼쪽부터 오른쪽으로 주어진다.

출력

출력의 첫 번째 줄에 경로의 y좌표 N개를 왼쪽부터 오른쪽으로 출력한다.

최단경로는 유일하지 않을 수도 있지만 항상 존재한다.

예제 입력 1

14
1 2 2 0 1 3 3 3 3 2 0 2 2 1
-1 -2 -2 -3 -3 -3 -1 0 -2 -3 -3 -3 -2 -1

예제 출력 1

0 0 -1 -1 -1 0 1 1 1 -1 -1 -1 0 0
W3sicHJvYmxlbV9pZCI6IjMxNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQxMzBcdWIxMTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzljMVx1YWQ1MFx1Yzg4Y1x1ZDQ1Y1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM5YzQgXHVkM2M5XHViYTc0IFx1YzcwNFx1YzVkMCBcdWQxMzBcdWIxMTBcdWM3NzQgXHVhZGY4XHViODI0XHVjODM4XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxMzBcdWIxMTBcdWM3NTggXHVjYzljXHVjN2E1XHVjNzQwICgwLDEpXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NCAoTiwxKVx1YzVkMFx1YzExYyBcdWIwNWRcdWIwOWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDEzMFx1YjExMFx1Yzc1OCBcdWJjMTRcdWIyZTVcdWM3NDAgKDAsLTEpXHVjNWQwXHVjMTFjIFx1YzJkY1x1Yzc5MVx1ZDU3NCAoTiwtMSlcdWM1ZDBcdWMxMWMgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxMzBcdWIxMTBcdWM3NDQgXHVkMWI1XHVhY2ZjXHVkNTU4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YjI5NCAoMCwwKVx1YzVkMFx1YzExYyBcdWMyZGNcdWM3OTFcdWQ1NzQgKE4sMClcdWM1ZDBcdWMxMWMgXHViMDVkXHViMDljXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjOWNcdWM3YTUsIFx1YmMxNFx1YjJlNSwgXHVhY2JkXHViODVjXHViMjk0IFx1YmFhOFx1YjQ1MCB4XHVjZDk1IFx1YjYxMFx1YjI5NCB5XHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1YyBcdWMxMjBcdWJkODRcdWM3NzQgXHVjNzc0XHVjNWI0XHVjOWM0IFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YmE3MCwgXHViYWE4XHViNGUwIFx1Y2Y1NFx1YjEwOFx1YjI5NCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWM3NGMgXHVjMTIwXHViZDg0XHVjNzU4IHhcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNzc0XHVjODA0IFx1YzEyMFx1YmQ4NFx1Yzc1OCB4XHVjMTIwXHViZDg0XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2M5Y1x1YzdhNVx1YWNmYyBcdWJjMTRcdWIyZTVcdWM3NTggeVx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWFjMDFcdWFjMDEgLTEwMDBcdWM1ZDBcdWMxMWMgMTAwMFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWNjOWNcdWM3YTVcdWM3NzRcdWIwOTggXHViYzE0XHViMmU1XHVhY2ZjIFx1YjJmZlx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDhcdWI0MThcdWJhNzAsIFx1Y2Y1NFx1YjEwOFx1YzVkMFx1YzExY1x1YjNjNCBcdWNjOWNcdWM3YTVcdWM3NzRcdWIwOTggXHViYzE0XHViMmU1XHVhY2ZjIFx1YjJmZlx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC93d3cuYWNtaWNwYy5uZXRcL3VwbG9hZFwvaW1hZ2VzMlwvdHVuZWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg2cHg7IHdpZHRoOjM5N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1ZDEzMFx1YjExMFx1Yzc1OCBcdWM2MDhcdWM4MWNcdWIyOTQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWIyZTQuIFx1Y2M5Y1x1YzdhNVx1YWNmYyBcdWJjMTRcdWIyZTVcdWM3NDAgXHVjMmU0XHVjMTIwXHVjNzNjXHViODVjLCBcdWFjYmRcdWI4NWNcdWIyOTQgXHVjODEwXHVjMTIwXHVjNzNjXHViODVjIFx1YWRmOFx1YjgyNFx1YzgzOFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMTMwXHViMTEwXHVjNzQ0IFx1ZDFiNVx1YWNmY1x1ZDU1OFx1YjI5NCBcdWNkNWNcdWIyZTggXHVhY2JkXHViODVjXHViOTdjIFx1Y2MzZVx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1ZDEzMFx1YjExMFx1Yzc1OCBcdWIxMDhcdWJlNDQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1Y2M5Y1x1YzdhNVx1Yzc1OCB5XHVjODhjXHVkNDVjXHVhYzAwIE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMxMzggXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJjMTRcdWIyZTVcdWM3NTggeVx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBOXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM2N2NcdWNhYmRcdWJkODBcdWQxMzAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2JkXHViODVjXHVjNzU4IHlcdWM4OGNcdWQ0NWMgTlx1YWMxY1x1Yjk3YyBcdWM2N2NcdWNhYmRcdWJkODBcdWQxMzAgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzNjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZDVjXHViMmU4XHVhY2JkXHViODVjXHViMjk0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YzljMFx1YjljYyBcdWQ1NmRcdWMwYzEgXHVjODc0XHVjN2FjXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE1NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6InR1bmVsIiwiZGVzY3JpcHRpb24iOiI8cD5BIHR1bm5lbCBpcyBkcmF3biBpbiB0aGUgcmVjdGFuZ3VsYXIgY29vcmRpbmF0ZSBzeXN0ZW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjZWlsaW5nIG9mIHRoZSB0dW5uZWwgc3RhcnRzIGluICgwLDEpIGFuZCBlbmRzIGluIChOLDEpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmxvb3Igb2YgdGhlIHR1bm5lbCBzdGFydHMgaW4gKDAsLTEpIGFuZCBlbmRzIGluIChOLC0xKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHBhdGggdGhyb3VnaCB0aGUgdHVubmVsIHN0YXJ0cyBpbiAoMCwwKSBhbmQgZW5kcyBpbiAoTiwwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNlaWxpbmcsIGZsb29yIGFuZCBwYXRoIGFyZSBzZXF1ZW5jZXMgb2YgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgc2VnbWVudHMgc3VjaCB0aGF0IGVhY2ggY29ybmVyIGhhcyBpbnRlZ2VyIGNvb3JkaW5hdGVzLCBhbmQgdGhlIHgtY29vcmRpbmF0ZSBvZiBlYWNoIGNvcm5lciBpcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gdGhlIHgtY29vcmRpbmF0ZSBvZiB0aGUgcHJldmlvdXMgY29ybmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbGwgb2YgdGhlIHktY29vcmRpbmF0ZXMgb2YgdGhlIGNlaWxpbmcgYW5kIHRoZSBmbG9vciB3aWxsIGJlIGludGVnZXJzIGJldHdlZW4gLTEwMDAgYW5kIDEwMDAsIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHBhdGggbXVzdCBub3QgdG91Y2ggdGhlIGNlaWxpbmcgb3IgdGhlIGZsb29yIG9mIHRoZSB0dW5uZWwsIGV2ZW4gb24gY29ybmVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHR1bm5lbCBmcm9tIHRoZSB0aGlyZCBleGFtcGxlIGlzIGdpdmVuIGluIHRoZSBmaWd1cmUgYmVsb3cuIFRoZSBjZWlsaW5nIGFuZCB0aGUgZmxvb3IgYXJlIHJlcHJlc2VudGVkIHdpdGggc29saWQgbGluZXMgYW5kIHRoZSBwYXRoIGlzIHJlcHJlc2VudGVkIHdpdGggdGhlIGRhc2hlZCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC90dW5lbC5wbmdcIiBzdHlsZT1cImhlaWdodDoxODZweDsgd2lkdGg6Mzk3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgc29tZSBzaG9ydGVzdCBwYXRoIHRocm91Z2ggdGhlIHR1bm5lbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiwgMSAmbGU7IE4gJmxlOyAxMDAsMDAwLCB0aGUgd2lkdGggb2YgdGhlIHR1bm5lbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgJm5kYXNoOyB5LWNvb3JkaW5hdGVzIG9mIHRoZSBob3Jpem9udGFsIHNlZ21lbnRzIG9mIHRoZSBjZWlsaW5nLCBmcm9tIGxlZnQgdG8gcmlnaHQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgJm5kYXNoOyB5LWNvb3JkaW5hdGVzIG9mIHRoZSBob3Jpem9udGFsIHNlZ21lbnRzIG9mIHRoZSBmbG9vciwgZnJvbSBsZWZ0IHRvIHJpZ2h0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBOIGludGVnZXJzICZuZGFzaDsgeS1jb29yZGluYXRlcyBvZiB0aGUgaG9yaXpvbnRhbCBzZWdtZW50cyBvZiB0aGUgcGF0aCwgZnJvbSBsZWZ0IHRvIHJpZ2h0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgdGVzdCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IGEgc29sdXRpb24sIGFsdGhvdWdoIG5vdCBuZWNlc3NhcmlseSB1bmlxdWUsIGFsd2F5cyBleGlzdHMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2006 > Regional Competition - Juniors 3번

  • 문제를 다시 작성한 사람: jh05013
  • 문제를 번역한 사람: waylight3