Tilted Square Display
Time limit2sMemory limit128 MB
Place 45-degree tilted squares along the x-axis one by one without overlap, then find which squares are visible when viewed from directly above.
- Level
Medium7 of 10
- Topics
- Geometry, Simulation, Math, Stack
- Solved
- No attempts yet
Problem
There are N squares of distinct sizes. The squares are tilted by 45 degrees and displayed one by one on the x-axis. Let a_i be the side length of square S_i.
First, S_1 is placed so that it touches both the x-axis and the y-axis. For each square S_i, let b_i be the x-coordinate of the point where S_i touches the x-axis.
Then S_i is placed for i=2 through N in order. Its b_i must be greater than b_{i-1}, and S_i must not overlap any previously placed square. Among all valid positions, S_i is placed where b_i is as small as possible.
After all squares are placed, find the square numbers visible from the positive y-axis direction. A square is considered visible if there exists a point on it such that the ray starting at that point in the positive y-axis direction does not meet any other square.
Input
The first line contains the number of squares N (1 <= N <= 100).
The second line contains N natural numbers a_1, a_2, ..., a_N, the side lengths of the squares in order. Each length is at most 1,000, and all lengths are distinct.
Output
Print the numbers of the squares visible from the positive y-axis direction in increasing order, separated by spaces.