
Bulgaria 2001 CONF POWER SQUARE	17-я Болгарская национальная олимпиада по информатике, 2001. Финальная часть. Первый день 17-th Bulgarian National Olympiad in Informatics, 2001. Final (3-th) Round. First Day. Problem 1. Conference An important meeting of two countries was attended by M representatives from the first country and by N representatives from the second (M and N are no greater than 1000; representatives are numbered by 1, 2, ... , M and by 1, 2, ... , N, respectively). Beforehand, it was selected K pairs of negotiators. In each pair, one person belongs to the first country, while the other person belongs to the second country. Every representative from each country was assigned to one such pair at least. The representatives were placed in different rooms in the building, where the meeting was held. The technical personnel had got an instruction to connect with direct telephone lines some pairs of room, so that any representative should be able to use a direct telephone connection to one, at least, representative that shares the same pairs for negotiation with him/her. The cost of telephone connection between any two rooms is a constant. The technical personnel should carry out their tasks with spending minimum resources. Write a program CONF.EXE that finds out the minimum number of direct telephone lines according to the above requirements. The input text file CONF.INP begins with a line containing numbers M, N and K, separated by a space. Every one from the next K lines contains one pair of negotiators P1–P2, where P1 is a representative from the first country and P2 is a representative from the second. The two numbers, P1 and P2, are separated by a space. The output should be written in a text file CONF.OUT. This file should contain only one line with the number found by your program. An Example: CONF.INP 3 2 4 1 1 2 1 3 1 3 2 CONF.OUT 3 Problem 2. Power Given integers N, M and Y (0<N<999, 1<M<999, 0<Y<999), write a program POWER.EXE, that finds out all the integers X (X=0, 1, ..., M-1), such that the division of M by the N-th power of X gives a remainder equal to Y, i.e. X^N mod M=Y. The input data are read from a text file POWER.INP. The file contains integers N, M and Y, written in one line and each two of them separated by a space. The output should be written as a sequence of one or several different integers each two of them separated by a space and placed in an incresing order in an output text file POWER.OUT. If such integers do not exist, your program should write in the file the number –1. An Example: POWER.INP 2 6 4 POWER.OUT 2 4 Allowed program run time: 5 seconds. Problem 3. Squares In the coordinate plane, N squares (0<N<100) and a point P are given. A distance between a point P and a square is defined as the smallest possible length of a straight line segment connecting the point P and some point (contour or internal) of the square. In the case, when the point P is internal for the square, then the distance is assumed to be equal to 0. Some given squares may overlap partially or completely each other. Also, some squares may have coincidental vertices as well as having all its vertices being on the same point. Write a program SQUARE.EXE, that sets in an increasing order all the given squares according to their distances from the point P. The input data must be read from the text file SQUARE.INP. The first line of the file contains the integer N. In every one of the next N lines a set of 4 integers is given. They belong to the interval (–9999, 9999). The first two of these integers are x- and y-coordinates of some vertex of the subsequent given square. The second two integers are x- and y-coordinates of the opposite vertex of the same square. At the end, the file contains one more line, in which the x- and y-coordinates of the point P are given. Anywhere, every two adjacent integers, that are in one line, are separated by a space. The output data should present a sequence of numbers of all the given squares in an order found by your program (Each square has received its number consequently according to its appearence in the input file). In the case, when two squares have the same distances to the point P, then their numbers must be written in the output sequence according to their actual increasing order. The name of the output text file should be SQUARE.OUT. The numbers in it should be written in one line and any two of them, that are adjancent, should be separated by a space. An Example: SQUARE.INP 2 0 0 1 1 0 3 1 4 0 0 SQUARE.OUT 1 2 Allowed program run time: 5 seconds

Bulgaria
2001

CONF
POWER
SQUARE

17-я Болгарская национальная олимпиада по информатике, 2001. Финальная часть. Первый день
17-th Bulgarian National Olympiad in Informatics, 2001. Final (3-th) Round. First Day.

Problem 1. Conference
An important meeting of two countries was attended by M representatives from the first country and by N representatives from the second (M and N are no greater than 1000; representatives are numbered by 1, 2, ... , M and by 1, 2, ... , N, respectively). Beforehand, it was selected K pairs of negotiators. In each pair, one person belongs to the first country, while the other person belongs to the second country. Every representative from each country was assigned to one such pair at least. The representatives were placed in different rooms in the building, where the meeting was held. The technical personnel had got an instruction to connect with direct telephone lines some pairs of room, so that any representative should be able to use a direct telephone connection to one, at least, representative that shares the same pairs for negotiation with him/her. The cost of telephone connection between any two rooms is a constant. The technical personnel should carry out their tasks with spending minimum resources.

Write a program CONF.EXE that finds out the minimum number of direct telephone lines according to the above requirements.

The input text file CONF.INP begins with a line containing numbers M, N and K, separated by a space. Every one from the next K lines contains one pair of negotiators P1–P2, where P1 is a representative from the first country and P2 is a representative from the second. The two numbers, P1 and P2, are separated by a space.

The output should be written in a text file CONF.OUT. This file should contain only one line with the number found by your program.

An Example:

CONF.INP
3 2 4
1 1
2 1
3 1
3 2

CONF.OUT
3

Problem 2. Power
Given integers N, M and Y (0<N<999, 1<M<999, 0<Y<999), write a program POWER.EXE, that finds out all the integers X (X=0, 1, ..., M-1), such that the division of M by the N-th power of X gives a remainder equal to Y, i.e. X^N mod M=Y.

The input data are read from a text file POWER.INP. The file contains integers N, M and Y, written in one line and each two of them separated by a space.

The output should be written as a sequence of one or several different integers each two of them separated by a space and placed in an incresing order in an output text file POWER.OUT. If such integers do not exist, your program should write in the file the number –1.

An Example:

POWER.INP
2 6 4

POWER.OUT
2 4

Allowed program run time: 5 seconds.

Problem 3. Squares
In the coordinate plane, N squares (0<N<100) and a point P are given. A distance between a point P and a square is defined as the smallest possible length of a straight line segment connecting the point P and some point (contour or internal) of the square. In the case, when the point P is internal for the square, then the distance is assumed to be equal to 0. Some given squares may overlap partially or completely each other. Also, some squares may have coincidental vertices as well as having all its vertices being on the same point. Write a program SQUARE.EXE, that sets in an increasing order all the given squares according to their distances from the point P.

The input data must be read from the text file SQUARE.INP. The first line of the file contains the integer N. In every one of the next N lines a set of 4 integers is given. They belong to the interval (–9999, 9999). The first two of these integers are x- and y-coordinates of some vertex of the subsequent given square. The second two integers are x- and y-coordinates of the opposite vertex of the same square. At the end, the file contains one more line, in which the x- and y-coordinates of the point P are given. Anywhere, every two adjacent integers, that are in one line, are separated by a space.

The output data should present a sequence of numbers of all the given squares in an order found by your program (Each square has received its number consequently according to its appearence in the input file). In the case, when two squares have the same distances to the point P, then their numbers must be written in the output sequence according to their actual increasing order. The name of the output text file should be SQUARE.OUT. The numbers in it should be written in one line and any two of them, that are adjancent, should be separated by a space.

An Example:

SQUARE.INP
2
0 0 1 1
0 3 1 4
0 0

SQUARE.OUT
1 2

Allowed program run time: 5 seconds