PROBLEMS FROM THE 3RD STAGE OF THE 11TH LATVIAN OLYMPIAD IN INFORMATICS
1. Series
All the natural numbers from n to m (inclusively) are written in a row without separating symbols, thus creating a series of decimal digits.
For example, if n=98 and m=102, this series is 9899100101102.
Then all the digits are sorted in a non-increasing order - first the greatest digits, then the next greatest, etc.
For the example above this sorted series is 9998211110000.
For the values of natural numbers n,m and k given in the input your task is to compute, which digit will be in the k-th position of the sorted series.
Input data
The values of three natural numbers n (0<n<109) , m (0<m<109,m³n) and k (0<k<109) are input from the keyboard.
Output data
The digit at the k-th position of the sorted series must be output on the screen. If length of the series is less than k, a single word NAV must be output on the screen.
Examples
Input data Output data
98 102 4 8
Input data Output data
9999 9999 5 NAV
2. Sevens, twos and zeros
The task is to write a program that outputs the smallest possible number s for an input natural number n. The number s must have the following properties:
Input data
A value of natural number n (0 < n < 500000) is input from the keyboard.
Output data
The number s as described above must be output on the screen. If it is not possible to find the corresponding value of s to the given value of n, output one word "NAV".
Examples
Input data Output data
3 27
Input data Output data
61 70272
3. Ones
The form of a natural number a in a number system with base p contains of n ones (digts "1") in a row.
Your task is to write a program that computes the greatest values of exponents of numbers 2 and 3 such that the remainder of a divided by both these values the remainder is 0.
Input data
Two values of natural numbers p (1 < p < 109) and n (n < 109) are input from the keyboard.
Output data
Two non-negative integer numbers must be output on the screen : the values of the greatest exponents of two and three.
Examples
Input data Output data Notes
17 2 1 2 a=1117=1810
The greatest exponents of two and three, such that remainder of a divided by any of these numbers is 0, are 2 (21) and 9 (32)
Input data Output data
10 4 0 0
4. The magician
The circus magician Tālrīts Vakars shows magic tricks. In his demonstrations he uses only :
baloons ( | ), doves ( | ), rabbits ( | ) and poodels ( | ). |
Tālrīts can carry out only the following tricks: (baloons and animals in the direction shown by the arrow are converted to different animals):
+ | + |
+ | + |
+ | + |
Your task is to write a program that for the input number of baloons, doves, rabbits and poodels computes the maximum possible number of rabbits that Tālrīts can obtain and the least number of tricks required to do this.
Input data
The values of non-negative integer numbers b (number of baloons, b£150), d (number of doves, d£150),
t (number of rabbits, t£150) and p (number of poodels, p£150) are input from the keyboard. It is also known that b + d + t + p £ 250.
Output data
The maximum possible number of rabbits that Tālrīts can obtain must be displayed on the screen, as well as (separated by a space symbol) the minimal number of tricks that is required to obtain this number of rabbits.
Examples
Input data Output data
9 17 1 3 10 3
Input data Output data
3 0 2 2 4 2