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.
Second Day.
Problem 1. Game.
The following game is considered: Given are an even number of stiff paper cards. On each of them an integer is written. All the cards are placed in a line. The game is played by two players with alternating turns. At his turn, the player takes away one card that is standing in the endmost left or in the endmost right place in the line. The game is over when there is no card to be taken. At the end of the game, the winner is that player who has collected cards with a greater total sum of integers. The game is finish with neither side winning, when the sums of the two players are equal.
Your task is to write a program GAME.EXE, that will play against a program, supplied by the jury. Your program begins the first move of the game and your goal is to win. The game should be fulfilled in the following way: At the beginning, your program should read all the data from the input file and close it.After that, your program should call several times jury's function oppo in a way you have decided. The function oppo has one input parameter, that should be assigned with a value 1 or 2 each time your program calls this function. The value 1 of that parameter means that you play a move, corresponding to taking a card from the endmost left-hand side of the line, while the value 2 means that you play by taking a card from the endmost right-hand side. The function oppo returns a value equal to 1 or 2. This value shows how jury's program replies to your move. The value 1 means that jury's program takes a card from the endmost left-hand side, while the value 2 means that a card has been taken by jury's program from the endmost right-hand side.
When your program calls the function oppo for the last time, i.e. when the game is over, the function oppo stops the run of your program.
The input data should be read from the text file GAME.INP. This file has two lines. The first line contains an integer N (1 < N < 100), that is equal to the number of the given cards. The second line contains N integers, ordered in the same way as the cards are arranged from left to right. These integers are positives in the range from 1 to 99. Any two of them, which are adjacent in the input file, are separated by a space.
Your program should not write any output files.
Allowed run time for your program is 5 seconds.
Remark for Turbo C/C++ programmers: You have given two files: OPPO.H and OPPO.OBJ. Include the directive #include “OPPO.H” in your program. Use a project file with included GAME.CPP and OPPO.OBJ. Apply the following compiler options: Model Small, Calling Convention C, C++ Compiler always.
Remark for Turbo Pascal programmers: You have given a file U_OPPO.TPU. The function oppo has the following definition: function oppo(p:integer):integer; You should include in your program the statement: uses u_oppo;
Remark for C/C++ programmers: You have given two files: OPPO.H and OPPO.OBJ. Include the directive #include “OPPO.H” in your program. Compile your program using the command line: gpp <your source> game.obj.
Renark for Free Pascal programmers: You have given two files: U_OPPO.PPU and U_OPPO.O. The function oppo has the following definition: function oppo(p:integer):integer; You should include in your program the statement: uses u_oppo;
You can download jury's program files from here.
Problem 2. Covering.
Given N (0 < N < 100) segments on a straight line. Each segment is defined by coordinates of its two endpoints a_i and b_i, i = 1, ..., N. These coordinates are integers within the range (-999, 999). Some segments might overlap partially or entirely each other. Write a program COVER.EXE, that finds out what is the minimal number of the given segments which should be removed, so that any two of the remaining segments would not have any inner common point, i.e. a point that belongs to both segments and that is inner for one of the segments at least.
The input data should be read from the text file COVER.INP. The first line of the file contains the integer N. It follows N lines. Each one of them contains two integers, separated by a space. Every such pair defines coordinates of both endpoints of the subsequent given segment.
The output of your program should be written in a text file COVER.OUT. In the first line of the file, an integer equal to the number of the remaining segments should be written. It should follow so many lines in the output file. In any one of them, the coordinates of the left-hand and the right-hand endpoints of a subsequent remaining segment should be written. These coordinates should be separated by a space. The coordinates of the left-hand endpoints should be arranged according to their increasing order. In the case, when the problem has more than one solution, your program should output only one of them, no matter which.
An Example:
COVER.INP
3
6 3
1 3
2 5
COVER.OUT
2
1 3
3 6
Allowed program run time: 5 seconds.
Problem 3. Jeep.
A jeep in a desert region should reach a point located N km away. The fuel consumption is 1 liter per km. The jeep has a fuel tank containing M liters. There is an unlimited amount of fuel at the starting point. Anywhere along the route to the final point there is an unlimited number of unbounded empty fuel tanks. Anytime, the jeep can store some amount of its fuel in any route fuel tank or can take fuel previousely stored by it during its travel. Write a program JEEP.EXE, that computes the minimum amount of fuel (measured in liters) necessary to reach the final point.
The input data should be read from the text file JEEP.INP. The file contains a line with two integers N and M, separated by a space. The following restrictions applied: N < 32000, 0 < N < 5M, M < N.
The output of your program should be written as an integer (amount of the fuel rounded to the nearest whole number above) in the text file JEEP.OUT.
An Example:
JEEP.INP
1000 500
JEEP.OUT
3838
Allowed program run time: 5 seconds.
© The text is translated from Bulgarian by Emil
Kelevedzhiev (keleved@math.bas.bg)
Return to the
Home Page of Bulgarian Mathematics and Informatics Competitions.