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

2 0 0 0







Internet Contest


Web design: Vivi

[ The rules | Read the problems | Submit solutions | Results | Downloads ]

[ Problem 1 | Problem 2 | Problem 3 ]

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.

Write a program that finds a switch touch sequence that will turn on all the light bulbs, starting from a given state.

File name: X.IN

Line 1: N
  • an integer, the number of corners of the building, labelled from 1 to N;
    Lines 2..2xN - 2: I J
  • Two integers, separated by a blank, representing a wall between the corners I and J;
    Line 2xN - 1: S1 S2 ... SN
  • N integers (separated by blanks) whose values are 0's or 1's, corresponding to the state of the N light bulbs;
  • 0 means off; 1 means on.

    The input data are guaranteed to represent a building that can be constructed in the specified pattern.

    File name: X.OUT
    Line 1: L1 L2 ... LK
  • K integers, separated by blanks, represen-ting the list of the labels of the switches to be touched.
  • If there are several solutions, only one is required.
  • If there is no possible solution, you should write in the output file a single line containing the number 0.
  • 3 <= N <= 1000
    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 0
    In the figure below you can see a possible building steps for the example file; the labels for the bulbs initially illuminated are underlined.