Twelve problems were presented to the jury of IOI.
Nine problems for the first day.
Three problems for the second day.
The IOI jury selected three problems for the first day:
1. The necklace of beads.
2. The companies's shares.
3. Rectangles of different colours.
And one problem for the second day:
1. The travel around Canada.
For further information
FIRST DAY
Problem 1.1.a:
You have a necklace of n beads (n <100) some of which are red, others blue and others white,
arranged at random. Let's see two examples for n = 29:
1 2 1 2
o x x o x o o x
o x x x
o o x o
o o @ o
x o @ @
x x o o
x x x x
x x o x
o o x o
x o o o
x o o o
o o o x
o x o o o @
Figure a Figure b
o red bead
x blue bead
@ white bead
(The beads considered first and second in the text that follows have been marked in the picture).
The configuration in Fig. a) may be represented as a string of b's and r's, where b represents a
blue bead and r a red one, as follows:
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
Suppose you are to break the necklace, lay it out straight, and then collect beads of the same
colour from one end until you reach a bead of a different colour, and do the same for the other
end (which may not be of the same colour as the beads collected before this).
Determine the point where the necklace should be broken so that the most number of beads can
be collected.
For example, for the necklace in Fig. a), 8 beads can be collected, with the breaking point either
between bead 9 and bead 10, or between bead 24 and bead 25.
In some necklaces, white beads had been included as shown in Figure b) above. When
collecting beads, a white bead that is encountered may be treated as either red or blue, and
painted with the desired colour. The string that represents this configuration will include the
symbols: r, b and w.
Write a program to do the following:
1. Read a configuration from an ASCII input file, NECKLACE.DAT, with each configuration on
one line. Write this data into an ASCII output file, NECKLACE.SOL. An example of an
input file would be:
Example:
NECKLACE.DAT
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrrb
2. For each configuration, determine the maximum number, M, of beads collectable, along
with a breaking point.
3. Write to the outfile, NECKLACE.SOL, the number M and the breaking point. The solutions
for different configurations should be separated with a blank record.
Example of a possible solution:
NECKLACE.SOL
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
8 between 9 and 10
bbwbrrrwbrbrrrrrb
10 between 16 and 17
Problem 1.2.a:
The economic situation has turned bad. Due to a shortage of money in circulation and lack of
credit, many factories have contracted debts that they cannot pay. There are, at most, 1000
factories.
All factories act as sellers (they sell their production) as well as buyers (they buy raw materials
and component parts). So they contract debts among themselves. Finally, someone has had the
idea of paying debts with ... debts.
Say factory A owes $100 to factory B, factory B owes $50 to factory C, and C owes $75 to A. The
sum of all the debts is $225. Factory A uses its credit with factory C to pay part of its debt to
factory B. So,
A to B $25
B to C $50
C to B $75
This way, the total debt may be reduced to a minimal sum and the list of debts becomes:
A to B $25
C to B $25
The problem is to write a program for paying debts with debts.
1. Read a list of debts from an ASCII input file, DEBT.DAT, and write this data to an ASCII
output file, DEBT.SOL. Each record in the list consists of three items: two factory codes
and the amount owed by the first to the second. Different lists will be separated by a blank
record as shown in the example below.
Calculate and output to DEBT.SOL the total amount of debts.
2. Reconstruct the list of debts so that the total amount of debts is minimal. Write to
DEBT.SOL the new list of debts in the same form as the input list.
3. Calculate and output to DEBT.SOL the total amount of debts in the new list.
Example:
DEBT.DAT
A B 100.00
B C 50.00
C A 75.00
A B 1500.00
B C 1100.00
D A 1400.00
Example of a possible solution:
DEBT.SOL
A B 100.00
B C 50.00
C A 75.00
Total = $225.00
A B 25.00
C B 25.00
Total = $50.00
A B 1500.00
B C 1100.00
D A 1400.00
Total = $4000.00
A B 100.00
D B 300.00
D C 1100.00
Total = $1500.00
Problem 1.3.a:
In the city of Sinistra, the Town Council has forbidden right turns. In order to enforce this rule, all
car drivers are required by the Town Council to install a computer in their vehicles. This computer
records the vehicle coordinates every time the vehicle turns right or left. At the end of each trip, a
sequence of positions is transmitted to a Council computer, which calculates the amount of the
traffic ticket by charging a fine of $50 for each right turn. The problem to solve is: given the
sequence of positions of a car, calculate the amount of the traffic ticket.
Details:
A trip is represented by a sequence of 2 or more points: p1, p2, ...., pN. Each point is a pair of
numbers (i, j), where i and j are the coordinates of the position of the car in a coordinate system
with origin at the Town Hall.
p1 is the position where the trip began, pN is the position where it ended, and the other points
are the corners where the car turned left or right. The streets are straight lines of arbitrary
direction.
The problem is to write a program to:
1. Read from the input ASCII file, SINISTRA.DAT, and write in an output file, SINISTRA.SOL,
the number N of points in the trip on one line and each point in the trip on the next N lines.
Each data set will be separated from the next by a blank line. Each point in the input
sequence is a pair of numbers separated by a blank with consecutive points on consecutive
lines, appearing in the order p1, ..., pN.
2. Compute the traffic ticket for the given trip.
3. Write in the output ASCII file SINISTRA.SOL the amount of the traffic ticket that must be
paid to the Town Council for each trip. Separate the amounts for the trips with a blank
record.
Example:
SINISTRA.DAT
3
4 1
5.5 4
5 2
4
0 1
-1 0
0 -1
1 0
SINISTRA.SOL
3
4 1
5.5 4
5 2
Traffic ticket: $50
4
0 1
-1 0
0 -1
1 0
Traffic ticket: $0
Problem 1.1.b:
The computer and a child are playing in the following way:
The child thinks of a sequence of four colours (not necessarily different) chosen out of six possible
colours. For convenience, let us use the numbers between 1 and 6 for denoting the six colours.
The computer (your program) must find this sequence using the information it obtains from the
child's answers.
The computer displays a sequence on the screen and the child must answer, using the keyboard
to enter the answers, the following two questions:
a) How many colours are right but not in the right positions?
b) How many right colours are in the right positions?
Example: Suppose the child has chosen the sequence: 4655. One possible way to find this
sequence may be:
COMPUTER YOUR ANSWER
1234 a) 1 b) 0
5156 a) 2 b) 1
6165 a) 1 b) 1
5625 a) 1 b) 2
5653 a) 1 b) 2
4655 a) 0 b) 4
Write a program that will always find the sequence chosen by the child in at most 6 steps. If you
cannot do this, write a program to find the sequence chosen by the child in at most 10 steps.
Problem 1.2.b:
Some companies are partial owners of other companies because they have acquired part of their
total shares. For example, Ford owns 12% of Mazda. It is said that a company A controls
company B if, at least, one of the following conditions is satisfied:
a) A = B
b) A owns more than 50% of B
c) A controls k (k > 1) companies,
C(1), ..., C(k), so that:
C(i) owns x(i)% of B for 1 < i < k and
x(1) + .... + x(k) > 50.
The problem to solve is:
Given a list of triples (i,j,p) which means that the company i owns p% of company j, calculate all
the pairs (h,s) so that company h controls company s. There are at most 100 companies.
Write a program to:
1 Read from an ASCII input file, COMPANY.DAT, the list of triples, (i,j,p), to be
considered for each case (that is, each data set), where i, j and p are positive integers.
Different cases (data sets) will be separated with a blank record.
2 Find all the pairs (h,s) so that company h controls company s.
3 Write to an ASCII output file, COMPANY.SOL, all the pairs (h,s) found, with h different
from s. The pairs (h,s) must be written in consecutive records and in increasing order of
h. The solutions for different cases must be separated with a blank record.
Example:
COMPANY.DAT
2 3 25
1 4 36
4 5 63
2 1 48
3 4 30
4 2 52
5 3 30
1 2 30
2 3 52
3 4 51
4 5 70
5 4 20
4 3 20
COMPANY.SOL
4 2
4 3
4 5
2 3
2 4
2 5
3 4
3 5
4 5
Problem 1.2.c:
A sequence of positive integers
a1,.... aN
is called an additive chain of length N if for every k, 1 < k < N, there exists indices i and j,
1< i < j < N, so that:
ak = ai + aj
For example:
1 2 3 5
1 2 3 4 5
1 2 4 5
are additive chains.
The problem is, given a positive integer a, find an additive chain with minimal length N that has
a1 = 1 and aN = a.
Write a program to:
1 Read from an ASCII input file, CHAIN.DAT the number a. Different cases will be separated
with a blank record.
2 Find an additive chain of minimal length which starts with 1 and ends with a.
3 Write to an ASCII output file, CHAIN.SOL, the additive chain obtained. The solutions for
different cases must be separated with a blank record.
Example:
CHAIN.DAT
3
5
Example of a possible solution:
CHAIN.SOL
1 2 3
1 2 3 5
Problem 1.1.c:
You are given a general chessboard of nxn squares, n < 10. White squares and black squares of
the chessboard are arbitrarily arranged, but satisfy the following conditions:
i) Each column contains at least one white square.
ii) There is at least one column that contains only white squares.
You are requested to place castles into squares of the chessboard so that:
1) castles are only placed on white squares.
2) on every row and every column there is at most one castle.
3) each white square not containing a castle that is dominated by a castle on the same row
must also be dominated by another castle on the same column.
Write a program that does the following tasks:
a. Read from an ASCII input file, CHESS.DAT, the number n and the configuration for an nxn
chessboard, that is, n strings of 1's and 0's where 1 represents a white square and 0
represents a black square.
Write this data to an ASCII output file, CHESS.SOL.
b. Place as many castles as possible on the squares of the chessboard so that the three
above conditions are satisfied.
c. Output to CHESS.SOL the total M of castles placed and the chessboard where the white
squares have been replaced by the character "X" if you have placed a castle there.
Example:
CHESS.DAT
3
010
110
011
4
1111
0001
0001
0001
CHESS.SOL
3
010
110
011
3
0X0
X10
01X
4
1111
0001
0001
0001
1
1111
000X
0001
0001
Problem 1.2.c:
New Makeup Ltd. is an important factory which produces N different cosmetics. Every month,
New Makeup sends a shipment to its branch in Mallorca. Each cosmetic has different price and
volume.
This week the longshoremen of Buenos Aires Port have announced they will go on strike starting
next Monday. Nobody knows when port activities will be normalized. New Makeup's next
shipment is on Saturday and, for economic reasons, the factory needs to maximize the
shipment's value.
You have to give an answer to New Makeup's General Manager. For this, different data sets have
been written in an ASCII input file, MAKEUP.DAT. Each data set will look like this:
N (the total number of different products)
M (ship hold's capacity)
P1 V1 (price and volume of each unit of product 1)
P2 V2 (price and volume of each unit of product 2)
.........
PN VN (price and volume of each unit of product N)
where the numbers N, M, Pi, Vi (1 < i < N) are positive integers.
Write a program to:
1. Read the next data set from MAKEUP.DAT.
2. Determine how many units of each product have to be included in the shipment so that:
* the shipment's volume doesn't exceed the ship hold's capacity
* the shipment's value is maximum.
3. Write into the ASCII output file, MAKEUP.SOL:
* the quantity of units of each product included in the shipment
* the shipment's value
* the shipment's volume
The solutions to different data sets must be separated by a blank record.
Example:
MAKEUP.DAT
2
6
4 3
7 4
5
20
2 3
3 4
12 10
17 11
7 6
MAKEUP.SOL
Prod. 1 = 2
Prod. 2 = 0
Value = $8
Volume = 6
Prod. 1 = 1
Prod. 2 = 0
Prod. 3 = 0
Prod. 4 = 1
Prod. 5 = 1
Value = $26
Volume = 20
Problem 1.3.c:
N rectangles of different colours are superposed on a white sheet of paper. The sheet's sizes are:
a cm wide and b cm long. The rectangles are put with their sides parallel to the sheet's borders.
All rectangles fall within the borders of the sheet. As result, different figures of different colours
will be seen. Two regions of the same colour are considered to be part of the same figure if they
have at least one point in common; otherwise, they are considered different figures. The problem
is to calculate the area of each of these figures. a, b are even positive integers not greater than
30.
The coordinate system considered has origin at the sheet's center and the axes parallel to the
sheet's borders:
Different data sets are written in an ASCII input file, RECTANG.DAT:
a, b and N will be in the first line of each data set, separated by a blank space.
* In each of the next N lines you will find:
* the integer coordinates of the position where the left lower vertex of the rectangle was
put.
* followed by the integer coordinates of the position where the upper right vertex of the
rectangle was put
* and, then, the rectangle's colour represented by an integer between 1 and 64. White
colour will be represented by 1.
The order of the records corresponds to the order used to put the rectangles on the sheet.
Different data sets will be separated with a blank record.
Write a program to:
1. Read the next data set from RECTANG.DAT
2. Calculate the area of each coloured figure
3. Write in an ASCII output file, RECTANG.SOL, the colour and the area of each coloured
figure as shown in the example below. These records will be written in increasing order of
colour. The solutions to different data sets will be separated by a blank record.
Example:
RECTANG.DAT
20 12 5
-7 -5 -3 -1 4
-5 -3 5 3 2
-4 -2 -2 2 4
2 -2 3 -1 12
3 1 7 5 1
30 30 2
0 0 5 14 2
-10 -7 0 13 15
RECTANG.SOL
1 172
2 47
4 12
4 8
12 1
1 630
2 70
15 200
SECOND DAY
Problem 2.1:
You have won a contest organized by a Canadian airline. The prize is a free ticket to travel
around Canada, beginning in the most western point visited by this airline, then traveling only
from West to East until you reach the most eastern point visited by this airline, and then coming
back only from East to West until you reach the starting point. No city may be visited more than
once, except for the starting city, which must be visited exactly twice (at the beginning and the
end of the trip). You are also not allowed to use any other airline or any other means of
transportation. The problem to solve is: given a list of cities and a list of direct flights between
pairs of cities, find out an itinerary which visits as many cities as possible satisfying the above
conditions.
Different data sets are written in an ASCII input file, C:\IOI\ITIN.DAT. Each data set consists of:
* in the first line: the number N of cities visited by the airline and the number V of direct flights
that will be listed. N will be a positive integer not larger than 100. V is any positive integer.
* in each of the next N lines: a name of a city visited by the airline. The names are ordered
from West to East in the input file. That is, the i-th city is East of the j-th city if and only if i > j
(There aren't two cities in the same meridian). The name of each city is a string of, at most, 15
digits and/or characters of the Latin alphabet, for example:
AGR34 or BEL4
* in each of the next V lines: two names of cities, taken from the list of cities, separated by a
blank space. If the pair
city1 city2
appears in a line, it indicates that there exists a direct flight from city1 to city2 and also a direct
flight from city2 to city1.
Different data sets will be separated by an empty record (that is, a line containing only the end of
line character). There will be no empty record after the last data set. The following example is
stored in file C:\IOI\ITIN.DAT.
8 9
Vancouver
Yellowknife
Edmonton
Calgary
Winnipeg
Toronto
Montreal
Halifax
Vancouver Edmonton
Vancouver Calgary
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary
5 5
C1
C2
C3
C4
C5
C5 C4
C2 C3
C3 C1
C4 C1
C5 C2
The input may be assumed correct and no checking is necessary.
The solution found for each data set must be written to an ASCII output file, C:\IOI\ITIN.SOL: in
the first line, the total number of cities in the input data set; in the next line, the number M of
different cities visited in the itinerary, and in the next M+1 lines the names of the cities, one by
line, in the order in which they will be visited. Note the first city visited must be the same as the
last. If no solution is found for a data set, only two records for this data set must be written in
ITIN.SOL, the first one giving the total number of cities, and the second one saying: "NO
SOLUTION". A possible solution for the above example:
ITIN.SOL
8
7
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver
5
NO SOLUTION
Put your program solution into an ASCII file named C:\IOI\DDD.xxx. Extension .xxx is .BAS for
Qbasic, .LCN for LOGO, .C for C, .PAS for PASCAL.
Problem 2.2:
Once upon a time there was a gardener whose works were easy to recognize: he divided the
garden in triangles and he planted flowers of the same colour in each of them.
A millionaire called the gardener to design his garden so that:
* each of the N beautiful fountains of his garden, numbered from 1 to N, had to be a vertex of
at least one of the triangles. No fountain could be on the side of a triangle of which it was not a
vertex.
* a bee could fly in a straight line from any fountain to any other fountain flying continuously over
flowers or fountains.
* two adjacent triangles (those with a common side) always had to be planted with different
colours.
* once he had chosen the triangles, he had to use flowers of as few colours as possible.
Write a program to solve the gardener's problem.
Different data sets are written in an ASCII input file, C:\IOI\GARDEN.DAT. Each data set will look
like this:
N (the number of fountains)
x1 y1 (coordinates of fountain 1)
......
xN yN (coordinates of fountain N)
where N, xi, yi , 1 < i < N < 100, are integers. Different data sets will be separated by an empty
record (that is, a line containing only the end of line character). There will be no empty record after
the last data set.
The solution to each data set must be written in an ASCII output file, C:\IOI\GARDEN.SOL, as
follows:
N (the number of fountains in the input)
m (the number of triangles drawn)
p (the number of colours used)
r1 s1 t1 C1 (r1,s1,t1 are the fountains at the vertices of triangle 1, and C1, a number
between 1 and p, is the colour of triangle 1)
....................
rm sm tm Cm (rm,sm,tm are the fountains at the vertices of triangle m and Cm, a number
between 1 and p, is the colour of triangle m)
The input may be assumed correct, no checking is necessary.
The solutions to different data sets must be separated by an empty record.
The following example is stored in file C:\IOI\GARDEN.DAT.
7
-2 2
2 2
-2 -2
2 -2
0 1
1 0
-1 0
9
-1 1
0 1
1 1
-1 0
0 0
1 0
-1 -1
0 -1
1 -1
A possible solution appears below.
7
8
3
1 3 7 1
1 7 5 2
1 5 2 1
2 5 6 2
2 6 4 1
4 6 3 2
3 6 7 3
7 5 6 1
9
8
2
5 1 2 2
5 2 3 1
5 3 6 2
5 6 9 1
5 9 8 2
5 8 7 1
5 7 4 2
5 4 1 1
Put your program solution into an ASCII file named C:\IOI\DDD.xxx. Extension .xxx is .BAS for
Qbasic, .LCN for LOGO, .C for C, .PAS for PASCAL.
Problem 2.3:
Imagine you are at a social get-together with at most 500 guests. The host invites you all to have
dinner. There are several tables in the dining-room. The way the guests sit down at the tables is
the following: each one sitting not alone at a certain table must know at least one person sitting
at the same table and no one else sitting at other tables.
It is supposed that if a person knows a second person, the second one knows the first person too.
No one introduces himself to the other persons sitting in the same table. That means that if two
persons are sitting at the same table, but initially they do not know each other, they do not know
each other afterwards either.
a) Determine how many tables are necessary and the persons sitting at each table.
At each table there is only one person who will talk to the waiter, he is called the leader of the
table. Each person relays his wishes concerning the menu to the persons he knows. The time
allotted to each person to relay his wishes to each person he knows is supposed to be the same
for each person.
b) Find the most suitable person as leader of each table in order to receive information from all
the persons sitting at the same table in the shortest possible period of time; produce at
output the leader of each table.
Afterwards, the host wishes to unify the tables. For this purpose, he calls some friends. Each of
them, when coming, is introduced to the leaders of two tables, links the tables, sits down at the
new formed table and becomes the leader of this table.
c) What is the order of linking the tables in this way, so that at last all tables are unified into a
single one and the conditions of point b) are satisfied? Specify the minimum necessary
period of time for the leader to get information from all the other persons.
After the complete linking, the friends of the host are leaving and the tables get their initial
structure until the end of the dinner.
When dinner is over, the persons start leaving the tables.
d) Determine, for each table, the minimum number of persons and the order in which they are
leaving the table, until the persons who are still at the table do not know each other.
Different data sets will be separated by an empty record (that is, a line containing only the end of
line character). There will be no empty record after the last data set.
The following example is stored in file C:\IOI\MEETING.DAT.
8
1 2
1 3
2 4
7 6
4 3
5 6
7
1 2
1 3
2 3
4 5
5 6
6 7
C:\IOI\MEETING.SOL
Table 1: 1 2 3 4
Table 2: 5 6 7
Table 3: 8
Leader table 1: 2
Leader table 2: 6
Leader table 3: 8
6 8 New leader: 9
2 9 New leader: 10
Period of time: 3
Persons leaving table 1: 2 3
Persons leaving table 2: 6
Persons leaving table 3:
Table 1: 1 2 3
Table 2: 4 5 6 7
Leader table 1: 1
Leader table 2: 5
1 5 New leader: 8
Period of time: 3
Persons leaving table 1: 1 2
Persons leaving table 2: 5 6
Put your program solution into an ASCII file named C:\IOI\DDD.xxx. Extension .xxx is .BAS for
Qbasic, .LCN for LOGO, .C for C, .PAS for PASCAL.
Amalia B. de Capatto
e-mail: ab@berma.org.ar
Home: Naon 3099
(1430) Buenos Aires ARGENTINA
TE: +54-1-5430274