PROBLEMS FROM THE 3RD STAGE OF THE 10TH LATVIAN OLYMPIAD IN INFORMATICS

1. "THE VALUE OF AN EXPRESSION"

The operation # is defined for any two positive integers.
If x and y are positive integers, then
  (x#y) = sum_of_digits_in_x_decimal_notation × greatest_digit_in_y_decimal_notation +
       least_digit_in_y_decimal_notation

For example, (9#30) = 9×3+0 = 27, but (30#9) = 3×9+9 = 36.

Let us say that this problem's expression is such an expression which is either the single variable a (whose value is positive integer), or it can be written in the form
(this problem's expression # this problem's expression).

For example, the following expressions are this problem's expressions:

a
(a#a)
((a#a)#a)
(a#((a#a)#((a#a)#a)))

You are to write a program, which for the given value of a determines what is the least possible number of operations # with which this problem's expression with given value K (K - positive integer) can be written.

Input data

From the keyboard two positive integer values are input - the value of integer variable a (1 £ a £ 999999999) and the value of the expression K (1 £ K £ 999999999) .

Output data

On the screen the least necessary number of operations # must be written. If for the given value of a it is impossible to obtain K as a value of this problem's expression , then the word 'NEVAR' must be written

Examples

Input data Output data Comment
718 81 3 The corresponding this problem's expression is ((a#(a#a))#a), because its value is ((718#(718#718))#718)=((718#129)#718)=(145#718)=81
Input data Output data
999 333 NEVAR  

2. "THE FOLDED SHEET"

Edges of a rectangular sheet of paper are marked by letters A,R,Z,D. The length of the edges Z and D is a , while that of edges A and R - b centimeters.

On the side Z, x centimetrs from the side R, the point P is dotted, but on the side D, y centimeters from the side R, the point Q is dotted (see Figure 1)

The sheet is folded so that the folding line coincides with the segment PQ (see Figure 2).

You are to calculate the area covered by the folded sheet.

Input data

Integers a (0<a£1000), b (0<b£1000),

x (0£x£a), y (0£y£a) are inputed from the keyboard.

Output data

On the screen the area covered by the folded sheet (in square centimeters) with at least 6 significant digits must be written.

Examples

Input data Output data
7 100 1 1 600.000
Input data Output data
13 5 10 3 51.7857

Figure 1
Figure 2


3. "THE STRANGE SEQUENCE"

There is a sequence of positive integers {ai}. For each i (i>1) ai is the least possible integer with the following features:
1) ai > ai-1,
2) the sum of ai digits equals the sum of 4* ai-1 digits.

For the given values of the first sequence member a1 and the index n, you must find and output the value of the an .

Input data

The values of integers a1 (0< a1<20) and n (0<n<10000) are input from the keyboard.

Output data

You must write one integer on the screen - the value of the an . For the testing, only data where the corresponding an value does not increase 109 are to be used.

Example

Input data   Output data   Comment
4 5   79    The first five members of the sequence are : 4,7,19,49,79

4. "CUTTING OUT OF FACTORIALS"

A factorial of a positive integer n (which is noted as n!) is multiplication of all integers from 1 till n: n!=1×2×3×...×n. What is the least number of factorials to be cut out of multiplication of the first k factorials 1!×2!×3!×...×k! so that the multiplication of remaining factorials will be the square of a some integer ?

Input data

From the keyboard the value of k(2 £ k £ 500) is input.

Output data

You must output in the increasing order the values of the numbers whose factorials have to be be cut out. If there are several solutions, you must output just one of them.

Examples

Input data   Output data   Comment
4   2   4!×3!×1!=24×6×1=144=122  
Input data   Output data   Comment
6   2 3   6!×5!×4!×1!=720×120×24×1=2073600=14402
    or  
    2 4   6!×5!×3!×1!=720×120×6×1=518400=7202

To tests

Home To problem and test archive