1994 USACO Qualifying Round 
Problems

Here is a set of four problems which compose the Qualifying Round 
of the 1994 USACO. If you are a student, your mission, if you choose 
to accept it, is to solve as many of these problems as possible. If you 
are a local coordinator, you should distribute these problems to all 
students who wish to participate. They may begin working on them 
right away. During the week of February 14-18, students must bring 
their solutions on a disk to a local contest director to be tested against 
the TEST.DAT provided with each problem. To be judged correct, all 
programs must give, within a time limit of two minutes, the results as 
shown in the TEST.SOL.  All judgments in the Qualifying Round are 
left up to the local coordinator, but he/she should submit a  copy of 
the source code created by  each student.

Reaching any of the following three levels qualifies a student for the 
Competition Round.

Bronze Level - Two problems solved	
Silver Level -  Three problems solved.
Gold Level -    Four problems solved.

Please have each qualified student fill out and return the entry form 
for the competition round found in this brochure. Results on the 
qualifying round may be used to decide who comes to the final round 
in the event of ties near the cut-off point of 16 students. 

What languages may be used?
The official languages that will be used at IOI '94 in Sweden are 
Turbo Pascal, v6.0; Borland Turbo C++; MicroSoft Quick BASIC 
v4.5; and Logo. However, those who program in BASIC or Logo have 
never been very successful at IOI. Thus, the languages that will be 
used at the USACO training camp at the University of Wisconsin-
Parkside will be Pascal or C/C++.

What is the age limit?
In accordance with IOI rules, all students must be in secondary school 
and be 19 years of age or younger on July 3, 1994. Graduating seniors 
are considered to be in secondary school. 



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 Figure 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 color from one end until you reach a bead of 
a different color, and do the same for the other end (which may not be 
of the same color 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 Figure 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 color.  
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:

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

4. 	Run your program with the data file NECKLACE.DAT given in 
1.

Put your program solution into an ASCII file named PROB1.xxx. 
Extension .xxx is .BAS for QBasic, .LCN for LOGO, .C for C, .PAS 
for PASCAL.

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.

4. 	Run your program with the data file COMPANY.DAT.
	
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

Put your program solution into an ASCII file named PROB2.xxx. 
Extension .xxx is .BAS for QBasic, .LCN for LOGO, .C for C, .PAS 
for PASCAL.


PROBLEM 3
N rectangles of different colors 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 a result, different 
figures of different colors will be seen.  Two regions of the same color 
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 its 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:
o	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:
o	the integer coordinates of the position where the left lower 
vertex of the rectangle was placed;
o	followed by the integer coordinates of the position where the 
upper right vertex of the rectangle was placed;
o	and, then, the rectangle's color represented by an integer 
between 1 and 64.  White color 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 colored figure.
3.	Write in an ASCII output file, RECTANG.SOL,  the color and 
the area of each colored figure as shown in the example below.  
These records will be written in increasing order of color.  The 
solutions to different data sets will be separated by a blank 
record.

4. 	Test your program with the data file RECTANG.DAT.

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

Put your program solution into an ASCII file named PROB3.xxx. 
Extension .xxx is .BAS for QBasic, .LCN for LOGO, .C for C, .PAS 
for PASCAL.


PROBLEM 4
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, ITIN.DAT.  
Each data set consists of:

o	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.
o	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.)
o	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 
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, 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 PROB4.xxx. 
Extension .xxx is .BAS for QBasic, .LCN for LOGO, .C for C, .PAS 
for PASCAL.



Competition Round Registration 
Form

LocalCoordinator________________________________________
School___________________________________________________
Address__________________________________________________
City_____________     State____________ 
Zip______________________
Phone______________________e-mail address__________
QualifiedStudent ________________________________________
	
Home Address     _________________________________________

City ______________	State _____________  Zip ____________

Home Phone ___________________ e-mail address______________

Birthdate _______________________   Age_____________ Grade __

Language used ______________ Disk Format  IBM ___  MAC___

Number of Qualifying Round problems solved _______.

What to mail:
Submit with this form a disk containing your solutions to the problems 
you solved in the Qualifying Round of the USACO. On the outside of 
this disk write:	USACO Qualifying Round
		Your Name	
		Your Address
		Your City , State -  Zip 

We will return your disk filled with sample solutions to the 1994 
Qualifying Round problems along with the text of all previous 
problems used at the USACO and at IOI from its beginning in 1989 to 
1993. We will also include as many sample solutions as we have 
available. 

Please submit an entry fee of $20 payable to USACO. Mail the form, 
disk and check to: Dr. Donald T. Piele, USACO, University of 
Wisconsin-Parkside, 900 Wood Rd, Kenosha, WI  53141-2000. e-mail 
piele@cs.uwp.edu