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

문제

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

터널의 천장은 (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+XHJcblxyXG48cD5cdWNjOWNcdWM3YTUsIFx1YmMxNFx1YjJlNSwgXHVhY2JkXHViODVjXHViMjk0IFx1YmFhOFx1YjQ1MCB4XHVjZDk1IFx1YjYxMFx1YjI5NCB5XHVjZDk1XHVjNWQwIFx1ZDNjOVx1ZDU4OVx1ZDU1YyBcdWMxMjBcdWJkODRcdWM3NzQgXHVjNzc0XHVjNWI0XHVjOWM0IFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YmE3MCwgXHViYWE4XHViNGUwIFx1Y2Y1NFx1YjEwOFx1YjI5NCBcdWM4MTVcdWMyMTggXHVjODhjXHVkNDVjXHVjNzc0XHVhY2UwLCBcdWIyZTRcdWM3NGMgXHVjMTIwXHViZDg0XHVjNzU4IHhcdWM4OGNcdWQ0NWNcdWIyOTQgXHVjNzc0XHVjODA0IFx1YzEyMFx1YmQ4NFx1Yzc1OCB4XHVjMTIwXHViZDg0XHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Y2M5Y1x1YzdhNVx1YWNmYyBcdWJjMTRcdWIyZTVcdWM3NTggeVx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWFjMDFcdWFjMDEgLTEwMDBcdWM1ZDBcdWMxMWMgMTAwMFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWNjOWNcdWM3YTVcdWM3NzRcdWIwOTggXHViYzE0XHViMmU1XHVhY2ZjIFx1YjJmZlx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDhcdWI0MThcdWJhNzAsIFx1Y2Y1NFx1YjEwOFx1YzVkMFx1YzExY1x1YjNjNCBcdWNjOWNcdWM3YTVcdWM3NzRcdWIwOTggXHViYzE0XHViMmU1XHVhY2ZjIFx1YjJmZlx1YzU0NFx1YzExY1x1YjI5NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvdXBsb2FkXC9pbWFnZXMyXC90dW5lbC5wbmdcIiBzdHlsZT1cImhlaWdodDoxODZweDsgd2lkdGg6Mzk3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVkMTMwXHViMTEwXHVjNzU4IFx1YzYwOFx1YzgxY1x1YjI5NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVhZGY4XHViOWJjXHVhY2ZjIFx1YWMxOVx1YjJlNC4gXHVjYzljXHVjN2E1XHVhY2ZjIFx1YmMxNFx1YjJlNVx1Yzc0MCBcdWMyZTRcdWMxMjBcdWM3M2NcdWI4NWMsIFx1YWNiZFx1Yjg1Y1x1YjI5NCBcdWM4MTBcdWMxMjBcdWM3M2NcdWI4NWMgXHVhZGY4XHViODI0XHVjODM4XHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQxMzBcdWIxMTBcdWM3NDQgXHVkMWI1XHVhY2ZjXHVkNTU4XHViMjk0IFx1Y2Q1Y1x1YjJlOCBcdWFjYmRcdWI4NWNcdWI5N2MgXHVjYzNlXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkMTMwXHViMTEwXHVjNzU4IFx1YjEwOFx1YmU0NCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzljXHVjN2E1XHVjNzU4IHlcdWM4OGNcdWQ0NWNcdWFjMDAgTlx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMThcdWI4NWMgXHVjNjdjXHVjYWJkXHViZDgwXHVkMTMwIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzEzOCBcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YmMxNFx1YjJlNVx1Yzc1OCB5XHVjODhjXHVkNDVjXHVhYzAwIE5cdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2Q5Y1x1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYmRcdWI4NWNcdWM3NTggeVx1Yzg4Y1x1ZDQ1YyBOXHVhYzFjXHViOTdjIFx1YzY3Y1x1Y2FiZFx1YmQ4MFx1ZDEzMCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNkNWNcdWIyZThcdWFjYmRcdWI4NWNcdWIyOTQgXHVjNzIwXHVjNzdjXHVkNTU4XHVjOWMwIFx1YzU0YVx1Yzc0NCBcdWMyMThcdWIzYzQgXHVjNzg4XHVjOWMwXHViOWNjIFx1ZDU2ZFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzE1NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6InR1bmVsIiwiZGVzY3JpcHRpb24iOiI8cD5BIHR1bm5lbCBpcyBkcmF3biBpbiB0aGUgcmVjdGFuZ3VsYXIgY29vcmRpbmF0ZSBzeXN0ZW0uJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjZWlsaW5nIG9mIHRoZSB0dW5uZWwgc3RhcnRzIGluICgwLDEpIGFuZCBlbmRzIGluIChOLDEpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZmxvb3Igb2YgdGhlIHR1bm5lbCBzdGFydHMgaW4gKDAsLTEpIGFuZCBlbmRzIGluIChOLC0xKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHBhdGggdGhyb3VnaCB0aGUgdHVubmVsIHN0YXJ0cyBpbiAoMCwwKSBhbmQgZW5kcyBpbiAoTiwwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGNlaWxpbmcsIGZsb29yIGFuZCBwYXRoIGFyZSBzZXF1ZW5jZXMgb2YgaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgc2VnbWVudHMgc3VjaCB0aGF0IGVhY2ggY29ybmVyIGhhcyBpbnRlZ2VyIGNvb3JkaW5hdGVzLCBhbmQgdGhlIHgtY29vcmRpbmF0ZSBvZiBlYWNoIGNvcm5lciBpcyBncmVhdGVyIHRoYW4gb3IgZXF1YWwgdG8gdGhlIHgtY29vcmRpbmF0ZSBvZiB0aGUgcHJldmlvdXMgY29ybmVyLiZuYnNwOzxcL3A+XHJcblxyXG48cD5BbGwgb2YgdGhlIHktY29vcmRpbmF0ZXMgb2YgdGhlIGNlaWxpbmcgYW5kIHRoZSBmbG9vciB3aWxsIGJlIGludGVnZXJzIGJldHdlZW4gLTEwMDAgYW5kIDEwMDAsIGluY2x1c2l2ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHBhdGggbXVzdCBub3QgdG91Y2ggdGhlIGNlaWxpbmcgb3IgdGhlIGZsb29yIG9mIHRoZSB0dW5uZWwsIGV2ZW4gb24gY29ybmVycy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHR1bm5lbCBmcm9tIHRoZSB0aGlyZCBleGFtcGxlIGlzIGdpdmVuIGluIHRoZSBmaWd1cmUgYmVsb3cuIFRoZSBjZWlsaW5nIGFuZCB0aGUgZmxvb3IgYXJlIHJlcHJlc2VudGVkIHdpdGggc29saWQgbGluZXMgYW5kIHRoZSBwYXRoIGlzIHJlcHJlc2VudGVkIHdpdGggdGhlIGRhc2hlZCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXMyXC90dW5lbC5wbmdcIiBzdHlsZT1cImhlaWdodDoxODZweDsgd2lkdGg6Mzk3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgc29tZSBzaG9ydGVzdCBwYXRoIHRocm91Z2ggdGhlIHR1bm5lbC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGFuIGludGVnZXIgTiwgMSAmbGU7IE4gJmxlOyAxMDAsMDAwLCB0aGUgd2lkdGggb2YgdGhlIHR1bm5lbC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIHNlY29uZCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgJm5kYXNoOyB5LWNvb3JkaW5hdGVzIG9mIHRoZSBob3Jpem9udGFsIHNlZ21lbnRzIG9mIHRoZSBjZWlsaW5nLCBmcm9tIGxlZnQgdG8gcmlnaHQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0aGlyZCBsaW5lIGNvbnRhaW5zIE4gaW50ZWdlcnMgJm5kYXNoOyB5LWNvb3JkaW5hdGVzIG9mIHRoZSBob3Jpem9udGFsIHNlZ21lbnRzIG9mIHRoZSBmbG9vciwgZnJvbSBsZWZ0IHRvIHJpZ2h0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiBOIGludGVnZXJzICZuZGFzaDsgeS1jb29yZGluYXRlcyBvZiB0aGUgaG9yaXpvbnRhbCBzZWdtZW50cyBvZiB0aGUgcGF0aCwgZnJvbSBsZWZ0IHRvIHJpZ2h0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiB0aGUgdGVzdCBkYXRhIHdpbGwgYmUgc3VjaCB0aGF0IGEgc29sdXRpb24sIGFsdGhvdWdoIG5vdCBuZWNlc3NhcmlseSB1bmlxdWUsIGFsd2F5cyBleGlzdHMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

  • 잘못된 번역을 찾은 사람: jh05013
  • 문제를 번역한 사람: waylight3