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 |
a^{2}b |
ab^{2} |
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 ab^{2}, wrote it in the third column and, finally, calculated ab^{2} 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 |
a^{2}b |
ab^{2} |
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, a^{2}b un ab^{2}. 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