//
you're reading...
Dùng cho cấp THPT, Dùng cho thi học sinh giỏi, Đề thi Tin học quốc tế IOI

1993 – International Olympiad in Informatics

First Round Problems 
IOI V

PROBLEM 1
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 2
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		COMPANY.SOL
2	3	25		4	2
1	4	36		4	3
4	5	63		4	5
2	1	48
3	4	30
4	2	52
5	3	30

1	2	30		2	3
2	3	52		2	4
3	4	51		2	5
4	5	70		3	4
5	4	20		3	5
4	3	20		4	5


PROBLEM 3
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	RECTANG.SOL
20 12 5			1 172
-7 -5 -3 -1 4		2 47
-5 -3 5 3 2		4 12
-4 -2 -2 2 4		4 8
2 -2 3 -1 12		12 1
3 1 7 5 1

30 30 2			1 630	
0 0 5 14 2		2 70
-10 -7 0 13 15		15 200


You have won a contest sponsored by an airline. The prize is a ticket to travel 
around Canada, beginning in the most western point served by this airline, then 
traveling only from west to east until you reach the most eastern point served, 
and then coming back only from east to west until you reach the starting city.  
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 not 
allowed to use any other airline or any other means of transportation. Given a 
list of cities served by the airline, and a list of direct flights between pairs of 
cities, find an itinerary which visits as many cities as possible and satisfies the 
above conditions beginning with the first city and visiting the last city on the 
list and returning to the first city.

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 served 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 served by the airline.  The names are 
ordered from west to east in the input file. That is, the i-th city is west of the j-th 
city if and only if i < j (There are no 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
	(There are no spaces in the name of a city)
•	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				5  5
Vancouver			C1
Yellowknife			C2
Edmonton			C3
Calgary				C4	
Winnipeg			C5
Toronto				C5  C4
Montreal			C2  C3
Halifax				C3  C1
Vancouver Edmonton		C4  C1
Vancouver Calgary		C5  C2
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

The input may be assumed correct. 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 per line, in the order in which they are 
visited. Note the first city visited must be the same as the last.  Only one solution is 
required. 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				5
7				NO SOLUTION
Vancouver
Edmonton
Montreal
Halifax
Toronto
Winnipeg
Calgary
Vancouver

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.

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

Silver Fox Vixen Hunting

cold calm

Limenitis reducta - the Southern White Admiral

More Photos

Thống kê

  • 95,355 lượt xem

%d bloggers like this: