Tunnel
Time limit1sMemory limit128 MB
Given a tunnel's ceiling and floor y-coordinates over N columns, construct the shortest axis-aligned path from (0,0) to (N,0) that never touches either boundary.
- Level
Medium7 of 10
- Topics
- Greedy, Geometry, Simulation
- Solved
- No attempts yet
Problem
A tunnel is drawn on a Cartesian plane.
The tunnel ceiling starts at (0, 1) and ends at (N, 1). The tunnel floor starts at (0, -1) and ends at (N, -1). A path through the tunnel must start at (0, 0) and end at (N, 0).
The ceiling, floor, and path are all polylines made by joining segments parallel to the x-axis or y-axis. Every corner has integer coordinates, and as the polyline is followed, the x-coordinate of the next segment never becomes smaller than that of the previous segment.
Each y-coordinate of the ceiling and floor is an integer from -1000 to 1000, inclusive.
The path must not touch the ceiling or the floor, not even at a corner.
The figure shows one possible tunnel. The ceiling and floor are drawn with solid lines, and the path is drawn with a dotted line.
Write a program that finds a shortest path through the tunnel.
Input
The first line contains the tunnel width N (1 <= N <= 100,000).
The second line contains N y-coordinates of the ceiling, from left to right.
The third line contains N y-coordinates of the floor, from left to right.
Output
Print N y-coordinates of the path on the first line, from left to right.
A shortest path may not be unique, but at least one valid shortest path always exists.