시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 208 | 66 | 63 | 36.416% |
Your friend Charmion asked you to hang some canvases out to dry on a straight washing line for an art project she has been working on. The canvases are artfully arranged such that none of them overlap, although they may touch along the edges. For stability, each canvas must be held by two pegs, but because the canvases are very rigid, they can be held from anywhere.
Each canvas is an integral number of centimetres wide (at least 10 cm). Each peg is slightly less than 1 cm wide. Canvases and pegs are all placed at integral centimetre positions along the line.
Unnecessary things touching any canvas is a smudge risk, thus every canvas should be held by exactly two pegs, no more and no less. Given all of the pegs that are already attached to the line, place as few as possible additional pegs as necessary to hold all of the canvases.
Figure C.1: Illustration of a solution to Sample Input 2. Pre-existing pegs are marked in white.
The input consists of:
Canvases are given from left to right and may touch only at edges, that is ri ≤ ℓi+1 for each i.
If the canvases can be secured, output the smallest number of extra pegs needed to secure all of the canvases while touching each exactly twice. On the next line output the integer positions of all of the new pegs.
Otherwise, output “impossible”.
If there are multiple optimal solutions, you may output any one of them.
4 0 18 18 28 28 40 49 60 4 6 12 35 60
3 28 19 49
5 2 15 15 25 25 40 42 52 52 62 3 5 29 52
4 15 25 49 58
3 0 60 60 120 120 140 4 20 60 80 120
impossible
ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2019 C번