THE 12TH LATVIAN OLYMPIAD IN INFORMATICS
2ND STAGE PROBLEMS

1. “STRING”

    It sometimes happens that a button on the computer keyboard sticks and then in the printed text there are more than one identical letters. For example, the word "piano" can change into "ppppppiaanooooo".
    Your task is to write a program that corrects these errors: finds all the places within the given string, where identical letters follow each other and replaces them with one letter- that is, erases all the other identical letters and adds the remaining part of the string onto the end of the one remaining letter.

Input data
The first line of the text file VIRKNE.DAT is a string containing only lowercase latin letters. The string is at most 250 symbols in length.

Output data
Output the corrected string in the first line of the text file VIRKNE.REZ.

Example
Input data (VIRKNE.DAT)                             Output data (VIRKNE.REZ)
ppppppiaanooooo             piano


2. “PENCIL FACTORY”

In a pencil factory every uncompleted pencil is processed in the following way - at first it is painted in the painting machine an immediately afterwards handed over to the varnishing machine. However neither of the machines is properly tuned. The painting machine does not paint an uncompleted pencil after painting n pencils. In addition, the varnishing machine does not varnish a pencil after varnishing m pencils. Thus the factory produces three types of incomplete pencils: a completely unprocessed pencil, painted, but not varnished and varnished, but not painted pencils.

Your task is to write a program that for the given numbers n, m and k (the number of uncompleted pencils to be processed) computes the number of fully processed pencils and the number of each type of incomplete pencils. It is known that the uncompleted pencil before processing the pencils that interest us was neither painted, nor varnished.

Thus, for example, if n=3, m=5 and k=17, then the pencil processing can be illustrated by the following table (? means that the current operation has been performed, l - that it has not been performed):

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Painting ? ? ? l ? ? ? l ? ? ? l ? ? ? l ?
Varnishing ? ? ? ? ? l ? ? ? ? ? l ? ? ? ? ?

As is shown in the picture, only 12 out of the 17 pencils are fully processed. One (12th) has been left completely unprocessed. One pencil (6th) has been painted, but not varnished. Three pencils (4th, 8th and 16th) have been varnished, but not painted.

Input data
The first line of the text file FABRIKA.DAT contains values of three natural numbers n, m and k.

It is known that 0<n<106, 0<m<106, 0<k<109. The values of these numbers are separated by space symbols.

Output data

Output four integer numbers into the first line of the text file FABRIKA.REZ:
a) The number of pencils that have been both painted and varnished;
b) the number of pencils neither painted nor varnished;
c) the number of painted but not varnished pencils;
d) the number of varnished but not painted pencils.
The numbers must appear in the output in the above order. There must be a space between any two numbers next to each other.

Piemçri
Input data (FABRIKA.DAT)                         Output data (FABRIKA.REZ)
3 5 17                      12 1 1 3

Input data (FABRIKA.DAT)                         Output data (FABRIKA.REZ)
999999 999999 999999999     999999000 999 0 0


3. “HEATING MAIN”
 

A heating main must connect the upper side of the leftmost and uppermost cell (1;1) with the right side of the rightmost and lowermost cell (n;m) within a given rectangle-shaped area of size n×m cells. Four types of pipes can be used in building the heating main, of which each connects two sides of one cell.  
Pic.1.  Types of pipes.
The pipes in the heating main can be built only as shown in the picture, that is, without rotating. Thus none of the pipes can connect the left side of a cell with the upper side or the right with the lower side. The pipes of the built heating main must be connected, that is, if cells next to each other belong to the heating main, one of the ends of pipes in both these cells must touch the side common to both these cells. The whole heating main must within the given rectangle-shaped area - none of its pipes can be outside it.

In the beginning any cell of the area can be either empty (and then a new pipe can be built in it), or contain one of the following objects:
a) an earlier built pipe that can be used as a link within the heating main, but cannot be replaced by a different pipe;
b) a garden. The heating main must not use this cell..

Example of an area (n=4, m=5) with earlier built pipes and gardens is given in pic.2. The cell (4;2) contains a garden.


Pic.2.  Example of an area.

It is possible to build the heating main in three different ways, as shown in pic.3..


        Pic.3. The possible ways of building the heating main.

Yout task is to write a program that computes in how many different ways it is possible to build a heating main.

Input data
The first line of the text file TRASE.DAT contains the values of two natural numbers n (n£10) and m (m£10), separated by a space symbol. The following m lines of the file contain n numbers each. The j-th number of the i+1-st line reflects the cell in the i-th row and j-th column of the area. 0 means the cell is empty, numbers from 1 to 4 mean a built-in pipe in the corresponding cell, as shown in pic.1, while 5 means the cell contains a garden. There is a space between any two numbers next to each other in the same line.

Output data
One number must be output into the first line of the text file TRASE.REZ - the number of different possible ways of building the heating main.

Example
Input data (TRASE.DAT)                     Output data (TRASE.REZ)
4 5                     3
0 0 3 2
0 4 0 5
4 0 0 0
4 0 1 0
0 3 0 0


Home