시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 14 7 6 66.667%

문제

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

터널의 천장은 (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+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMxNTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJ0dW5lbCIsImRlc2NyaXB0aW9uIjoiPHA+QSB0dW5uZWwgaXMgZHJhd24gaW4gdGhlIHJlY3Rhbmd1bGFyIGNvb3JkaW5hdGUgc3lzdGVtLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgY2VpbGluZyBvZiB0aGUgdHVubmVsIHN0YXJ0cyBpbiAoMCwxKSBhbmQgZW5kcyBpbiAoTiwxKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGZsb29yIG9mIHRoZSB0dW5uZWwgc3RhcnRzIGluICgwLC0xKSBhbmQgZW5kcyBpbiAoTiwtMSkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBwYXRoIHRocm91Z2ggdGhlIHR1bm5lbCBzdGFydHMgaW4gKDAsMCkgYW5kIGVuZHMgaW4gKE4sMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBjZWlsaW5nLCBmbG9vciBhbmQgcGF0aCBhcmUgc2VxdWVuY2VzIG9mIGhvcml6b250YWwgYW5kIHZlcnRpY2FsIHNlZ21lbnRzIHN1Y2ggdGhhdCBlYWNoIGNvcm5lciBoYXMgaW50ZWdlciBjb29yZGluYXRlcywgYW5kIHRoZSB4LWNvb3JkaW5hdGUgb2YgZWFjaCBjb3JuZXIgaXMgZ3JlYXRlciB0aGFuIG9yIGVxdWFsIHRvIHRoZSB4LWNvb3JkaW5hdGUgb2YgdGhlIHByZXZpb3VzIGNvcm5lci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWxsIG9mIHRoZSB5LWNvb3JkaW5hdGVzIG9mIHRoZSBjZWlsaW5nIGFuZCB0aGUgZmxvb3Igd2lsbCBiZSBpbnRlZ2VycyBiZXR3ZWVuIC0xMDAwIGFuZCAxMDAwLCBpbmNsdXNpdmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBwYXRoIG11c3Qgbm90IHRvdWNoIHRoZSBjZWlsaW5nIG9yIHRoZSBmbG9vciBvZiB0aGUgdHVubmVsLCBldmVuIG9uIGNvcm5lcnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSB0dW5uZWwgZnJvbSB0aGUgdGhpcmQgZXhhbXBsZSBpcyBnaXZlbiBpbiB0aGUgZmlndXJlIGJlbG93LiBUaGUgY2VpbGluZyBhbmQgdGhlIGZsb29yIGFyZSByZXByZXNlbnRlZCB3aXRoIHNvbGlkIGxpbmVzIGFuZCB0aGUgcGF0aCBpcyByZXByZXNlbnRlZCB3aXRoIHRoZSBkYXNoZWQgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvdHVuZWwucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTg2cHg7IHdpZHRoOjM5N3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHNvbWUgc2hvcnRlc3QgcGF0aCB0aHJvdWdoIHRoZSB0dW5uZWwuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4sIDEgJmxlOyBOICZsZTsgMTAwLDAwMCwgdGhlIHdpZHRoIG9mIHRoZSB0dW5uZWwuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBzZWNvbmQgbGluZSBjb250YWlucyBOIGludGVnZXJzICZuZGFzaDsgeS1jb29yZGluYXRlcyBvZiB0aGUgaG9yaXpvbnRhbCBzZWdtZW50cyBvZiB0aGUgY2VpbGluZywgZnJvbSBsZWZ0IHRvIHJpZ2h0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgdGhpcmQgbGluZSBjb250YWlucyBOIGludGVnZXJzICZuZGFzaDsgeS1jb29yZGluYXRlcyBvZiB0aGUgaG9yaXpvbnRhbCBzZWdtZW50cyBvZiB0aGUgZmxvb3IsIGZyb20gbGVmdCB0byByaWdodC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gTiBpbnRlZ2VycyAmbmRhc2g7IHktY29vcmRpbmF0ZXMgb2YgdGhlIGhvcml6b250YWwgc2VnbWVudHMgb2YgdGhlIHBhdGgsIGZyb20gbGVmdCB0byByaWdodC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogdGhlIHRlc3QgZGF0YSB3aWxsIGJlIHN1Y2ggdGhhdCBhIHNvbHV0aW9uLCBhbHRob3VnaCBub3QgbmVjZXNzYXJpbHkgdW5pcXVlLCBhbHdheXMgZXhpc3RzLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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