| Home | I n t e r n e t C o n t e s t | i n t e r n e t c o n t e s t |
C E O I 2 0 0 0 |
Regulations Schedule Organising Team Cluj&Romania Sponsors Secretariat Internet Contest Links
|
Problem 1 : X-Planet All the inhabitants of the planet X build their houses in a triangular shape. In order to save time and effort, they use a special construction method. Everything starts with a straight wall. After that, for the construction of every new house they just add two new walls to an already existing wall, thus resul-ting in a closed, triangular shaped house. Of course, the two new added walls might also be used as starting walls for new houses. Sometimes, using this con-struc-tion pattern, they arrive at situations where some houses are completely enclosed in others (like in the figure). However, this is not a problem, because kids might live in the included houses. To light up their houses, the X-habitants install a light bulb on every corner of the final construction (a bulb in a corner is common to all the houses sharing that corner). On each corner, there is a switch whose touch toggles the state (on/off) of the bulb from both that corner and also that of all the bulbs of the connected corners. Two corners are considered connected if they are placed at the end of the same wall. Task Write a program that finds a switch touch sequence that will turn on all the light bulbs, starting from a given state. Input File name: X.IN Line 1: N Lines 2..2xN - 2: I J Line 2xN - 1: S1 S2 ... SN The input data are guaranteed to represent a building that can be constructed in the specified pattern. Output File name: X.OUT Line 1: L1 L2 ... LK Limits Example X.IN X.OUT 6 1 6 1 3 1 4 1 5 2 3 2 4 3 4 3 6 4 5 4 6 0 1 1 1 0 0In the figure below you can see a possible building steps for the example file; the labels for the bulbs initially illuminated are underlined.  |
||