Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: IOI's 1993 Problems
发信站: 哈工大紫丁香 (2002年03月29日13:20:56 星期五), 站内信件

1993 International Olympiad In Informations Problems
　
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 a
nd 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 ma
rked 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 num
ber 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 configurati
on 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 co
nfiguration on
one line. Write this data into an ASCII output file, NECKLACE.SOL. An exampl
e of an
input file would be:
Example:
NECKLACE.DAT
brbrrrbbbrrrrrbrrbbrbbbbrrrrb
bbwbrrrwbrbrrrrrb
2. For each configuration, determine the maximum number, M, of beads collect
able, 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 circula
tion 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, some
one 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 pa
y 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 deb
ts 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 d
ata 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 sepa
rated 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 minima
l. 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 lis
t.
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 orde
r 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. E
ach 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 o
n 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 tic
ket that must be
paid to the Town Council for each trip. Separate the amounts for the trips w
ith 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) c
hosen out of six possible
colours. For convenience, let us use the numbers between 1 and 6 for denotin
g 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, us
ing 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 t
o 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 acqui
red 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 co
mpany 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 posi
tive 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, wit
h h different
from s. The pairs (h,s) must be written in consecutive records and in increa
sing 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 exi
sts 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 mini
mal 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 wil
l 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 condition
s:
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 o
n 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 configurat
ion for an nxn
chessboard, that is, n strings of 1's and 0's where 1 represents a white squ
are 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 tha
t the three
above conditions are satisfied.
c. Output to CHESS.SOL the total M of castles placed and the chessboard wher
e 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 dif
ferent 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 Makeu
p's next
shipment is on Saturday and, for economic reasons, the factory needs to maxi
mize the
shipment's value.
You have to give an answer to New Makeup's General Manager. For this, differ
ent data sets have
been written in an ASCII input file, MAKEUP.DAT. Each data set will look lik
e 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 shipm
ent 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 fi
gures of different colours
will be seen. Two regions of the same colour are considered to be part of th
e 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 in
tegers not greater than
30.
The coordinate system considered has origin at the sheet's center and the ax
es 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 ea
ch coloured
figure as shown in the example below. These records will be written in incre
asing order of
colour. The solutions to different data sets will be separated by a blank re
cord.
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 air
line, 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 o
ther means of
transportation. The problem to solve is: given a list of cities and a list o
f direct flights between
pairs of cities, find out an itinerary which visits as many cities as possib
le satisfying the above
conditions.
Different data sets are written in an ASCII input file, C:\IOI\ITIN.DAT. Eac
h data set consists of:
* in the first line: the number N of cities visited by the airline and the n
umber 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 s
tring 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 c
ities, 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 co
ntaining 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 nex
t line, the number M of
different cities visited in the itinerary, and in the next M+1 lines the nam
es of the cities, one by
line, in the order in which they will be visited. Note the first city visite
d 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 on
e 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 the
m.
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 triangl
e 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. E
ach 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 wi
ll be no empty record after
the last data set.
The solution to each data set must be written in an ASCII output file, C:\IO
I\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 C
1, 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 i
nvites 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 le
ast 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. Th
at means that if two
persons are sitting at the same table, but initially they do not know each o
ther, they do not know
each other afterwards either.
a) Determine how many tables are necessary and the persons sitting at each t
able.
At each table there is only one person who will talk to the waiter, he is ca
lled the leader of the
table. Each person relays his wishes concerning the menu to the persons he k
nows. The time
allotted to each person to relay his wishes to each person he knows is suppo
sed 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 tim
e; 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 tab
les, 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 tabl
es 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 co
ntaining 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

--
不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]