Round 5: December 12th, 1997
Problem 1: The Law and the Cities
Problem 2: NIM
Problem 3: Santa Claus is Coming!...


A cycle, no matter how perfect might be, does have a way out.
Anonymous

Problem 1: The Law and the Cities (30 points)

The Parliament wants to adopt a very important law, but for this they have to get information about the cities of the country. Consequently, every mayor is asked for information about the city he's managing. The files received from the mayors are not at all easy to comprehend, so they have to be written so that everyone can understand them.
We know that every city consists of several quarters of houses. The quarters are limited by roads surrounding them, but there are no roads inside any of the quarters. There are for sure two types of rings (belts) in every city:
Remarks:
The Parliament wants to find out how many quarters exist in each city and which are the rings of the city and of its quarters.

Input Data:
The input file is called INPUT.TXT and has the following form:
      n m          - n is the number of the crossings and m, the number
                     of roads
      x1 y1        - the coordinates of the first crossing
      .......
      xn yn        - the coordinates of the crossing no. n
      q1 w1        - road between the crossings q1 and w1
      ........
      qm wm        - road between the crossings qm and wm

Output Data:
The output goes to the text file OUTPUT.TXT, having the following form:
The numbers of the crossroads will be separated by a space and the last crossing in the ring will also be the first.

Limits:
All the numbers that appear in the problem are natural numbers, smaller than 5001.

Example 1:
      INPUT.TXT
      6 7
      1 1
      2 1
      1 2
      2 2
      1 3
      2 3
      1 2
      3 4
      5 6
      1 3
      3 5
      2 4
      4 6

      OUTPUT.TXT
      2
      1 2 4 6 5 3 1
      1 3 4 2 1
      3 5 6 4 3

Example 2:
      INPUT.TXT
      4 4
      1 1
      2 1
      1 2
      2 2
      1 2
      3 4
      1 3
      2 4

      OUTPUT.TXT
      1
      1 2 4 3 1
      1 2 4 3 1

Execution time: 1 second/test on a Pentium/166 MHz.

Valentin Gheorghita,
Politehnica University,
Bucharest.


Problem 2: NIM (25 points)

The rules of the game:

Problem:

Input and Output Data:
Your program doesn't use any file for reading or writing; it will also neither read something from the keyboard, nor display anything on the screen. It will receive all the input data from the NimLib library.

Restrictions:
The Library:

Scoring:

Remarks:

Valentin Gheorghita,
Politehnica University,
Bucharest.


Problem 3: Santa Claus is Coming!... (20 points)

In the frozen land, the plans for Christmas' Eve are already made. Santa knows what gifts he will give to the children. And between his short trips and the number of the toys in his knap there's a very well-established relationship. To help him, Santa's counsellors made a rectangular board with 100 lines and 100 columns, including 10,000 pawns. These pawns have two sides, a black side and a red side. At first they are all with the black side up (that is you can only see their black side). Before Santa's departure, the counsellors turn the pawns so that, with a minimum number of turnings, a certain number of pawns with the red side up appear. The number of turnings represents the number of trips Santa makes in order to give as many toys as the number of the red pawns on the board.
A pawn cannot be turned upside down unless the whole line (horizontal or vertical) that includes that specific pawn is turned. We can turn any line we want and the number of times we want.
Find the minimum number of (horizontal or vertical) line turnings so that N red pawns appear on the board.

Input Data:
The file NOEL.IN has on each line an integer number:
      NOEL.IN:
      N1
      N2
      ...
      Nk
, where N1, N2, ... ,Nk are the numbers of red pawns (the number of toys).

Output Data:
The file NOEL.OUT has on each line a number:
      NOEL.OUT
      P1
      P2
      ....
      Pk
, where P1, P2, ... ,Pk are the minimum number of turnings so that N1, N2, ... ,Nk red pawns appear on the board; if there is no solution you will write NU.

Example Input and Output:
      NOEL.IN
      1990
      1970

      NOEL.OUT
      22
      NU

Execution Time: 1 second for every N on a 586/133 MHz.

Maria & Adrian Nita,
"Emanuil Gojdu" High School,
Oradea
.


[First Round] [Previous Round] [Next Round] [Last Round] [Romāna] [Go Back!]