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

1. “RECTANGLE”

Vilibald has decided to cut a right-angled checked page of size n×m cells into squares. First of all he cut off the largest possible square using a straight cut. Then he took away the square and repeated the action with the remaining rectangle. In this way (all the time cutting off the largest possible square) Vilibald continued cutting until the remaining rectangle was a square.

Your task is to write a program that for n and m values (n<10000, m<10000) given in the input data computes, how many squares Vilibalds obtained by cutting the rectangle in the way described above.

Examples

Input data     Output data    Comment

3   7             5               The rectangle was cut to squares with side length 3,3,1,1,1

Input data     Output data

9999 9999 1

 

2. “NUMBERS”

 

During a lesson of algebra Liene has written the following table on the board:

a

b

a2b

ab2

12

2

288

48

-1

-1

-1

-1

9

-3

-243

81

       

 

Liene chose integer numbers a un b, 0<|a|<1000, 0<|b|<1000, a³b, wrote these in the first and second column, then calculated the value ab2, wrote it in the third column and, finally, calculated ab2 and wrote it in the fourth column. You can assume that Liene did not make errors in her calculations.

Peter erased some of the numbers in the table and wrote 0 instead :

a

b

a2b

ab2

12

0

288

0

-1

-1

-1

-1

0

0

0

81

       

 

Your task is to write a program that from this type of a (Peter's modified) table finds and outputs the starting values of a, b, a2b un ab2. If more than one answer is possible, output the one with the smallest value of the leftmost repairable number.

Examples

Input data                    Output data

12 0 288 0    12 2 288 48

Input data                 Output data

0 0 0 81    1 -9 -9 81

3. “CIRCLE”

An endless checked page consists of square cells. The length of each side of the cell is k units. Smuidris drew a circle of radius r units on this page. The center of the circle was located on the intersection of two lines (in the middle of 4 cells). Then Smuidris painted all the cells that were crossed by the circle (that contained a part of the circle). (If the circle only touched a corner of the cell, Smuidris did not paint the cell).

You are to write a program that for given values of natural numbers k and r (k<30000, r<30000) computes un outputs the number of cells painted by Smuidris.

Examples.

Input data Output data

1 5 28

 

Input data Output data

3 7 20

 

 


 
 


To tests
Home