Round 8: January 23rd, 1998
Problem 1: Policemen at Work
Problem 2: Languages
Problem 3: Polygons


You must judge a person as capable of doing great things by the attention he gives to the little ones.

Problem 1: Policemen at Work (30 points)

In a metropolis, the new chief of the Circulation Service of the Police Department is trying to reduce the number of employees who stay at their desks with no work to do.With this purpose, he wants to send "on the field" as many policemen as possible, to watch certain streets of the city. To control them easier, each policeman will be given a route. By route, the chief means a sequence of streets, each one of them being identified by the two crossings (de)limiting it.
When making the route for each policeman separately, the following requests are taken into consideration:
Determin the maximum number of policemen who can be sent "on the field", as well as the route distributed to each of them (every route is written in the order of its patrolling).

Input Data:
The input file INPUT.TXT has the following structure:
      n m    // in the first line two numbers are written:
	        n (n <= 1500),representing the number of crossings in the city;
	        m (m <= 5000), representing the number of streets;
      i11 i12  // the next m lines contain pairs of two 
                numbers, representing the identifiers of the crossings to which
		each street is connected.
      i21 i22
      ...
      im1 im2

Output Data:
The output file OUTPUT.TXT has the following structure:
      p             // on the first line the maximum number of policemen that
                       can be sent "on the field"
      t11 t12 ... t1k1
      t21 t22 ... t2k2
                    // in the next p lines, the routes given to the policemen 
		       will be written and for each route the crossings on it
      ...              will be mentioned; the data in each line will be
		       separated by a space.
      tp1 tp2 ... tpkp

Example Input and Output:
      INPUT.TXT
      7 10
      1 2
      1 6
      2 6
      2 3
      3 4
      3 5
      3 6
      4 5
      5 6
      5 7

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

Maximum execution time: 30 seconds/test for a 586/133MHz.

Daniela Lica,
"Ion Luca Caragiale" High School,
Ploiesti.


Problem 2: Languages (30 points)

A new language is being made and it has the following elements:
A string forms a word of the language described above if, starting from the initial stage, following the evolution function, it gets to a final stage.

Input Data:
The input data is read from:
Output Data:
The output data will be written in the file LIMBAJ.TXT, which has the following structure:

Example Input and Output:
      DICTION.TXT: CUVINTE.TXT:
      4            abb
      a b          aabaa
      1            aaab
      3 4          bbb
      2 3 4        abaa
      0
      4
      3
      1 3
      2 4
      0
      1

      LIMBAJ.TXT:
      YES
      YES
      NO
      YES
      YES

Maximum execution time: 10 seconds per test on a 586/133 MHz.

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


Problem 3: Polygons (20 points)

An n-sided convex polygon is considered, n <= 100,000,000. In how many points do its diagonals cross, knowing that there is no group of three crossing diagonals?

Input Data:
The data is read from the file DIAG.IN, having the structure:
      n1
      n2
      ...    // ni is the number of sides of the polygon
      nk

Output Data:
The results are written in the file DIAG.OUT, with the following structure:
      p1
      p2 
      ...   // pi is the number of crossings corresponding to the 
               ni-sided polygon.
      pk
Execution Time: 0.5 seconds per test 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!]