PROBLEMS FROM THE 2ND STAGE OF THE 10TH LATVIAN OLYMPIAD IN INFORMATICS

1. "WONDERFUL FOURS" (Maximal running time of one test - 2 minutes* )

  Let us name a set of five decimal digits K5. (Note that numbers may be repeated within this set).
  We can say that a natural five-digit number is properly formed from K5 if it is formed by sequentially writing all the digits of K5 in a row in any order (taking each of them exactly once) and this number does not start with zero.
  In this way, for example, if K5 contains four digits 1,1,7,0 and 4, then numbers 17140 and 47011 are properly formed from K5, while 17740 is not.
  Let us call four natural five-digit numbers s1,s2,s3,s4 a K5 wonderful four, if the following properties are true for them :
1) s1 is properly formed from K5;
2) s2 is properly formed from K5;
3) s3 is properly formed from K5;
4) s4 is properly formed from K5;
5) s1, s2, s3 un s4 are all different numbers;
6) s1+ s2 + s3 = s4

  The task is to compute how many different K5 wonderful fours can be formed from the five digits contained by the set K5 given in the input data. (Change of order of numbers within a wonderful four does not form a new wonderful four).

Examples

Input data Output data     Comments
0 2 6 2 8     4 26028+26208+28026=80262
26082+26280+28260=80622
26028+28026+28206=82260
26280+28062+28260=82602
Input data Output data
9 2 3 3 9 0

2. "JOURNEY OF A KNIGHT" (Maximal running time of one test -10 seconds* )

  The size of a right-angled cell board is n*m cells. The chess knight is located in the left bottom cell of the board (coordinates 1;1), as shown in pic.1.

  The chess knight can move according to the chess rules - during each turn it can move according to the chess rules- either one cell in the vertical direction and one in horizontal or vice versa.
  Thus, for example, if n=4 and m=3 and the knight is located in the cell (2;1) (see pic.2), then with the next turn it can move in any of the following cells : (1;3),(3;3) or (4;2).
  For the given natural numbers n,m,i,j (n<=100,m<=100,i<=n,j<=m) given in the input your task is to determine and output, which is the least possible number of moves for the knight to reach the cell (i;j), starting from the cell (1;1).
  If it is not possible to reach this cell, output one single word "NEVAR".

Examples

Input data Output data
100 2 2 2 NEVAR
Input data Output data
5 3 1 2 3
Pic.1

Pic.2


3. "BILLIARDS" (Maximal running time of one test -10 seconds* )

The sides of a right-angled field of size 47*73 centimeters are labeled using letters A,R,Z,D. A small ball B (its size can be ignored) is placed inside this field 13 centimeters away from the side R and 29 centimeters from the side D (see pic.3). A player places his cue on the side R at a point that is located k centimeters from the side D and straightly hits the ball B. The ball continues its movements in a straight line and, if necessary, hits the sides of the field. The deflection occurs according to the laws of physics, that is, in directions making equal angles with a line perpendicular to the reflecting side. The starting fragment of the movement of the ball is shown in pic.4.

Your task is to write a program that for the given integer numbers k(0<=k<=73) un n(0<=n<109) would output the distance of the ball to the side R(BR) and side D (BD) after the ball has moved exactly n centimeters. The values BR and BD must be output as real numbers rounded to the nearest one thousandth of a centimeter.

Examples.

Input data Output data
29 100 19.000 29.000
Input data Output data
16 20 27.142 43.142
Pic.3

Pic.4


* - the time allowed for one test is measured using a PC with IBM PC 386 processor with frequency 20 MHz .


To tests

Home