THE 13TH LATVIAN
OLYMPIAD IN INFORMATICS |
1. Number
Write a program that for the input natural numbers n and m finds the smallest possible natural number k, for which both of the following properties simultaneously apply:
Input data
The first line of the text file SKAITLIS.DAT contains two natural numbers n
(0 < n £ 32000) and m (0 < m £ 500),
separated by a space symbol.
Output data
The value of the number k must be output to the only line of the
file SKAITLIS.REZ.
Example
Input data (file SKAITLIS.DAT)
38 17
Output data (file SKAITLIS.REZ)
51
2. Circle
There are N small circles positioned in a large circle. There is a natural number written in each of the circles. Each of the numbers is in every move replaced using the following algorithm:
For each three numbers (the number in the current circle and each of the neighboring circles) three numbers are determined - the greatest, the smallest, and "the remaining one".
The value written in the new circle is equal to the greatest - the smallest+ the remaining one.
Thus, if the value written in the considered circle is 7, while the nearby numbers are 3 and 8, the greatest is 8, the smallest 3 and the remaining one is 7. In the next turn the number 12 is written in the circle (as 8-3+7=12).
One turn is shown in the picture below (note that the values in all the circles are changed simultaneously):
Your task is for the input numbers N and M, as well as the numbers positioned in the circle, to determine what numbers will be written in the circle after M moves.
Input data
The first line of the text file
APLIS.DAT contains two natural numbers N (N £1000) and M (M £10), separated by a space symbol. In each of the following N lines
there is given one number that is contained by the respective
circle. The numbers are given in clockwise direction. The values
do not exceed 100 in any of the small circles.
Output data
The text file APLIS.REZ must
contain exactly n lines - one number per line. These must be the numbers to be
written in the corrseponding small circles after M turns.
The numbers must be output exactly in the same order as
given in the input data (one after another in the clockwise
direction, starting with the same circle the input data started
with).
Example
Input data (file APLIS.DAT)
Output data (file APLIS.REZ)
7
2 16
1
9
2
7
3
8
4
9
5
13
6
12
7
3. Password
In computer systems passwords are used to protect data from unauthorized access - these passwords are specific strings of symbols. However, it sometimes happens that the person knows the real password but mistypes it. The following typing errors are the most common:
1) a symbol is missing;
2) an extra symbox is inserted;
3) two symbols next to each other are swapped;
4) instead of one symbol
another is entered. Thus, if the real password would be "SlePENs", the first
error type would be in the string
"SlePNs", second type "SlePiENs", third type "SelPENs",fourth type "SlEPENs".
The specialists of the firm "Suspicion" have determined that the presence of one of the above errors during the entering of the password does not present significant danger to the safety of the system and that these strings can too be accepted as correct.
Your task is to write a program that for an input real password and an input string determines, whether the string can be accepted.
Input data
The small and capital letters in the input data are different
symbols.
The first line of the PAROLE.DAT text file contains the real
password - a string
containing only letters of the latin alphabet. The length of this
string does not exceed 250 characters.
The second line of the file contains the string to be checked,
containing only latin letters. The length of the string does not
exceed 250 characters.
Output data
The first line of the text file PAROLE.REZ must contain the word NEDER if the input string is
unacceptable (the number of errors exceeds 1), or the word DER
if the string is acceptable (it either is equal to the password
or it contains exactly one error as described above. If the
string is acceptable, the second line of the file must contain
either 0 (if the password is the same as the string) or the
information about the error type in the form of a natural number
1 to 4 (according to the error list above).
Examples
Input data (file PAROLE.DAT)
Output data ( file PAROLE.REZ)
SlePENs
DER
SelPENs 3
Input data (file PAROLE.DAT)
Output data ( file PAROLE.REZ)
SlePENs
NEDER
SelPeNs
Input data (file PAROLE.DAT)
Output data ( file PAROLE.REZ)
SlePENs
NEDER
SPelENs
4. Numbers
In a valid example of addition of two numbers A+B=C all the letters x (if there were these) were changed to y and vice versa. It is given that neither x,
nor y are equal to zero and that x is not equal
to y. Therefore, instead of the number A the equation
contains the number A*, instead of B - B*, C - C*. Write a
program that for the given number A*, B*, and C* finds and
outputs the numbers A, B, and C.
Input data
The first line of the text file CIPARI.DAT contains the number A*, the second line - B*, the third - C*. The
numbers do not start with zero and the length of each of the
numbers does not exceed 20.
Output data
The first line of the CIPARI.REZ text file must contain the digits x and
y, separated by a space symbol.
The second line of the file must contain the number A, the
third - B, the fourth - number C.
If more than one solution is possible, you only need to output any one of them.
Examples
Input data (file CIPARI.DAT)
Output data ( file CIPARI.REZ)
923456781
1 9
2009
123456789
923458710
2001
123458790
Input data (file CIPARI.DAT)
Output data ( file CIPARI.REZ)
4242
4 2
2424
2424
6666
4242
6666
Input data (file CIPARI.DAT)
Output data ( file CIPARI.REZ)
53
8 9
17
53
70
17
70
5. Lift
A skyscraper has n stories. It also has a lift working using only two keys ( and ). Pressing the key the lift moves exactly a stories upwards, pressing the key - exactly b stories downwards. If a command ordering to move above the n-th floor or below the 1st floor is received, the lift does not move. The lift is on the k-th floor. How many times, at least, must the above buttons be pressed to move to the m-th floor ?
For the given natural numbers n,a,b,k,m the smallest number of times required to push the button must be input.
Input data
The first line of the text file LIFTS.DAT contains five natural numbers n,a,b,k,m (n
£ 10000; a<n; b<n; k
£ n; m £ n). There is a whitespace between
each two numbers.
Output data
The first line of the LIFTS.REZ text file must contain one integer - the least number of times
buttons must be pressed to move the lift to the m-th floor.
If it is not possible to move the lift to the m-th floor, only the word NEVAR must be output to the first line of the text file.
Examples
Input data (file LIFTS.DAT) Output data (file
LIFTS.REZ)
100 4 2 1 22 NEVAR
Input data (file
LIFTS.DAT) Output data (file LIFTS.REZ)
11 2 3 10 6 3
Comment: A possible order of presses of the
buttons is: