In this problem, you are given a sequence
S1,
S2, ...,
Sn of squares of different sizes. The sides of the squares are integer numbers. We locate the squares on the positive
x-y quarter of the plane, such that their sides make 45 degrees with
x and
y axes, and one of their vertices are on
y=0 line. Let
bi be the
x coordinates of the bottom vertex of
Si. First, put
S1 such that its left vertex lies on
x=0. Then, put
Si, (
i > 1) at minimum
bi such that
a)
bi >
bi-1 and
b) the interior of
Si does not have intersection with the interior of
S1...
Si-1.
![](topimages/1458.gif)
The goal is to find which squares are visible, either entirely or partially, when viewed from above. In the example above, the squares S
1, S
2, and S
4 have this property. More formally, S
i is visible from above if it contains a point p, such that no square other than S
i intersect the vertical half-line drawn from p upwards.