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: 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