7th Round: 26th of February 1997

1st Problem
2nd Problem
1st Problem: Couples (45 points)

Find out all the couples of positive integer numbers (a, b) for which:
q * q + r = n
where q and r are the quotient respectively the rest of the division of a * a + b * b to a + b.
The input file 'pin' will have on each line a value <= 10.000 corresponding to a number 'n'.
The output file 'prez' will have the following structure:
n                  the number 'n' read from the file 'pin'
a1 b1
a2 b2
.....              the couples of positive integer numbers requested
ai bi
t                  the number of the couples found for a certain 'n'

Remark: in case for an 'n' there are no couples of numbers (a, b), in the file 'prez' will be written the message there are no (a, b) couples
Time for test: 30"/test (586 at 133MHz)
prof.Maria and Adrian Nita
"Emanuil Gojdu" Highschool

2nd Problem: Rectangles (30 points)

Having n rectangles, with their sides parallel with the coordinate axes, given the elements the upper left corner (xl, yl) and the lower right corner (xr, yr).
Enumerate the rectangles which intersect.
The informations are read from the file from , having the following structure:

1 xl1 yl1 xr1 yr1
2 xl2 yl2 xr2 yr2
n xln yln xrn yrn

1, 2, ..., n     represent the indeces of the rectangles
xli yli xri yri  represent the coordinates upper left corner,
lower right 
corner  of the rectangle i

print the results in the file drez which contains n lines like the following one:

i d1 d2 d3 ... dk

It means: the i rectangle intersect with the rectangles d1, d2, ..., dk
                 0 <= n <= 100
                 0 <= xli, yli, xri, yri <= 1000  (integers)
                 two rectangles intersect if:
                        - at least a side of each of them intersect;
                        - have at least a common vertex;
                        - have at least a common side;
                 in case a rectangle i does intersect none of the others, on
it's line will   
                 appear only i
Example: Having the file 'from':

1 1 6 10 1
2 2 9 4 5
3 8 11 13 6
4 13 4 15 2
5 5 9 17 3
6 4 16 5 14

The file 'drez' will be:

1 2 3 5
2 1
3 1 4 5
4 5
5 1 3 4

Time for test : 30"/test (586 at 133MHz)
prof.Maria and Adrian Nita
"Emanuil Gojdu" Highschool

[Index] [Important Informations] [Participants] [Final] [6th Round] [Final Problems]