Instructions

WHAT: The USA Computer Olympiad Fall 2000 Contest is a computer programming contest open to all pre-college students throughout the world who have access to the hs-computing@delos.com mailing list.  Several problems are presented for solution.  Results of this contest and other contests will be among the data used to choose delegates to the USA training camp and potentially to the IOI.  Winners of both the domestic and international divisions will receive awards at the end of the season.

HOW: Problems and rules will be posted to the hs-computing mailing list. Solutions must be written in Borland C/C++ or Turbo Pascal and must be returned via e-mail by the contest completion deadline. Choosing a non-Borland Pascal compiler will potentially cause a solution to not compile on the judges' machines. After you have completed the contest, feel free to take your final solution to a Borland Pascal equipped machine to ensure it will work. Do not charge this `repair' time against your coding time limit. Choosing a non-Borland C/C++ compiler has a greater chance of working out okay: make sure you use no library functions other than those provided by the following header files (i.e., don't #include anything but these files -- not all of which are usually needed, of course): assert.h io.h mem.h string.h ctype.h iostream.h stdio.h values.h fstream.h math.h stdlib.h If you use an ANSI compiler and use (at most) only these headers, your program should compile fine under our compilers. Remember that we are running the judging under MS-DOS and are thus subject to its memory requirements. The specific compilers used are as follows.
 * Turbo Pascal 7.0 
 * Borland C/C++ 3.1
This restriction reflects the current IOI rules, not a philosophy
of the USACO.

WHO: All pre-college students who have access to the hs-computing mailing list are eligible. This is an individual contest, not a team contest.

WHERE: Students can work on problem solutions anywhere they wish, including school and home.

WHEN: Problems for the international division will be posted to the mailing list between during the morning US Mountain Standard Time (0730-0800 or so) on Tuesday, November 16, 1999. All results are due by 0800 am US Mountain Standard Time (1400? GMT) Tuesday, November 23, 1999. Late solutions will not be accepted.

PRIZES: Winners will receive a handsome plaque or certificate and have their names immortalized on the USACO Web Pages

FEES: No entry fees are charged.

No special registration form is required. Each problem solution has, withinits submission, an entry form (see below). You enter when you send inyour solution.

RULES:
* Consultation with people other than the contest director is prohibited.
* Do not work in a team environment.
* Submit questions to <hburch@cs.cmu.edu <mailto:hburch@cs.cmu.edu>> who will try to fathom
an appropriate answer for you (and post it to the hs-computing
list, if appropriate). Many times, the reply will often be
a suggestion to read the problem more carefully.
* Any amount of consultation with written materials (such as programming books) is allowed (but this doesn't mean you can ask
someone to write an article on how to solve a problem, of course). Do not ask someone where to look up an answer though, that counts as `consultation with people.'
* Spend no more than three sessions solving problems (i.e., if
you work one hour in a session, take a one hour break, and then work another hour, you have worked for two sessions).
* Spend no more than a total of five hours solving problems. Really.
* Submit source code for the problems to the contest coordinators via e-mail to fall99@delos.com <mailto:fall99@delos.com> (see below for format).
* Solutions will be judged for correctness by running them against
several (usually 5-15) different sets of input data. Points are accrued for correct solutions. Some datasets for a problem will be worth more points than others. Solutions to some problems will be worth more points. Judging will be performed expeditiously but could take two weeks to complete.
* Unless otherwise stated, your program must run no longer than
5 seconds for any test case on the judge's computer (approximately 200 MHz PentiumII).
* Unless otherwise specified, it is NOT guaranteed that all possible legal datasets will be solvable within the time limit.
* The judges reserve the right to increase time limits during grading.
* Judges will not test all datasets against a program that crashes the computer for initial datasets.
* Decision of the judges is final.
* Do not cheat; it's no fun for anyone. Cheaters are often disqualified and banned.
* Do not use inline assembler statements.
* Do not submit programs that use data files that aren't supplied by the contest coordinators. Read only the specified input files and write only the specified output files.
* Do not use `temporary' data files.
* Keep in mind that this is neither a `tricky input' nor a `tricky output' contest, in general. Input and output formats are straightforward, though the input values may cause your
program difficulty.
* Problems are intended to be algorithmic in nature, meaning clever algorithms and/or data structures may be needed to score full marks.
* All problems are intended to be straightforward (yet challenging); no problems are intended to have `hidden tricks' in them.
* Nevertheless, legal but complex datasets are fair game for testing.
* If you find a problem with poor wording or an ambiguity, document your assumptions carefully and move on. Send e-mail; we'll reply if we can.
 NOTES: 
* We will be using automated grading procedures.
* The registration information at the front of each solutionshould be in precisely the same format as requested below. Otherwise, your solution could be lost. Be sure that each program has identically the same registration information.
* Programs that consist of essentially nothing more than print statements will not be graded. Programs must compute the requested answers.
* Submitters of programs that attempt to thwart grading procedures will be forever disqualified from USACO contests. Do not join this elite club!
* Rob Kolstad <kolstad@delos.com <mailto:kolstad@delos.com>> is this contest's director.
* Russ Cox is this contest's grader.
* During the contest, feel free to send questions (one per e-mail please!) to <hburch@cs.cmu.edu <mailto:hburch@cs.cmu.edu>>. He will reply by e-mail when he is available. Questions judged to be germane to the entire hs-computing list will be summarized and posted there, also. Be sure to check your e-mail occasionally for contest updates, should there be any.
For fairness, sometimes your question will be answered with a null answer (`Sorry, I can't elaborate on that').
* All programs read their input from file INPUT.TXT; do not specify a complete path name in your `open' statement, just
`INPUT.TXT'.
* All programs write their output to file OUTPUT.TXT; do not specify a path name in your `open' statement, just `OUTPUT.TXT'.
* Remember that your output should be written only to the file OUTPUT.TXT. Do not clear the screen or print anything to the screen.
* Note that test data run by the judges will surely be more challenging than the example data supplied with each problem.
* We will assess scoring penalties when certain rules are abused.
* Don't use any of C++'s Standard Template Library (STL) or any classes other than those provided by iostream.h and fstream.h. We're using a very old C++ compiler: it probably doesn't know about the special classes you want to use.
* If your source code does not compile without changes, your program will not be graded. The only exception to this is: we will sometimes fix source codes mangled by mail agents' treatment of line wraps and the like.
* Don't use C's ``bool'' type. That is specific to Borland C/C++ 5.0. If you can compile your code under ANSI C, you're probably safe.
* Pascal users must not use the CRT runtime library. That is, do not include `uses crt;' in your program.
* Your programs should neither expect nor depend on having any more than about 500 kilobytes of free conventional memory (as reported by DOS's mem command).
* Note that all the examples are intended to be correct and helpful. If you find an apparent error, please contact <kolstad@delos.com <mailto:kolstad@delos.com>> so he can correct the problem. Some of the examples have only been double-checked, not triple-checked. 
* The scorer will compile with exactly the command-line compiler options you specify in your '#pragma options' line. You must set any relevant options using the appropriate method in the source file. (Of course, if you don't wish to specify any, you can omit the #pragma line.) Note that not all command-line options are valid in the "#pragma". In particular, don't bother specifying "-P" or "-P-" on the "#pragma option" line, as the compiler will not accept it.



NEW 
* If you come upon a particularly good test case, please share it with <kolstad@delos.com <mailto:kolstad@delos.com>> so it can be included in the test cases. For each test case you submit that we use, we will increase your final score. Please include an explanation of why the test case is good and what it tests for. It's great if you include a correct answer but that's not required.

No special registration form is required. Each problem solution has, within its submission, an entry form (see below). You enter when you send in your solution.

Submit your answers to problems via e-mail to fall99@delos.com <mailto:fall99@delos.com>. Please send precisely one problem's solution program per e-mail (i.e., send three separate e-mails for three problems, etc.). If you send in more than one solution for a single problem (e.g., on subsequent e-mails), only the last one RECEIVED by our automatic mail reader will be graded.That means if you find a bug after your submission, you can re-submit. This is dangerous ground, of course, since your newer program might, in fact, be worse than the previous one. Furthermore, your newer program might arrive before your older program -- this really does seem to happen occasionally.

Every e-mail is acknowledged almost instantly by an automated mail reader. If you do not receive an acknowledgment, double-check the address. Note that some networks connect to the Internet only occasionally.

Each solution e-mail submission should have the format below for the e-mail message. SEND ASCII MESSAGES. DO NOT USE ATTACHMENTS or MIME ENCODING, fancy mail options, or anything else. The programs that read the mail are looking for just plain old ASCII (just like this message).
Submissions that use some format other than ASCII might not be graded. If you submit MIME attachments, your submission will be ignored.

Submissions must have special comments separating sections of the mail; you must insert the three `#'s and the word that follows them. Here is the exact format for submitting solutions so the grading programs can read them (be sure you note that those ### things are important -- they are actual text that belongs in your file!):

### Program
... [any compiler options you use] ...
... [header comments -- see below for format] ...
... [text of program in C or Pascal] ...
### End

NOTES: * Put comments precisely like the ones below at the front of each and every solution (after the `### Program' marker).
* These messages are read by a program; do not change the format.
* Be sure your email address and name are always spelled precisely
the same way. We use the combination of email address and name as a unique identifier for you. Capitalization counts!
* Data after `### End' are ignored (e.g., signatures)
* All registration lines (below) are required; your program won't be graded until they are filled in.
* Do not insert any extra blanks, please.
* Put compiler directives just before the header (as shown below) but nevertheless after the `### Program' marker. Choose your directives based on your own experience.

Here is the C/C++ header (with some compiler options) filled out for a youthful Rob Kolstad (my explanatory comments on far right -- do not include them). Do not remove any blank lines -- the automatic grader uses them. You should fill out a header out for each problem with your own data (save it in a file on your computer for easy inclusion on later submissions):

### Program
#pragma option -O2
/* (This goes on a separate line)
Problem: 1 (problem number)
Name: Rob Kolstad (First name then last name)
Email: kolstad@delos.com <mailto:kolstad@delos.com> (Email address)
School: Norman High School
Grade: 12 (Grade in school, numerical: 7, 8, 9, ..., 13)
Age: 18
CityState: Norman, OK (Non-USA people might not have a `State')
Country: USA (Three letters: CAN, COL, DEU, ROM, USA, etc.)

*/ (This goes on a separate line)

If you live somewhere that has a city but no state, please omit the state. If your school system uses a notation like `Form 6' for older students, please pro-rate your `Grade' by calculating the equivalent
USA school grade. In the USA: grade 10 students begin around age 15; grade 11 students begin around age 16; grade 12 students begin around
age 17.

Here is the PASCAL header (with compiler options) filled out for a youthful Rob Kolstad (my comments on far right -- do not include them). Do not remove any blank lines -- the automatic grader uses them. You
should fill out a header for each problem with your own data (why not save it in a file on your computer for easy inclusion on later submissions):

### Program

{$G+,N+}

{ (on a line by itself, please)

Problem: 1 (problem number)
Name: Rob Kolstad (first name then last name)
Email: kolstad@delos.com <mailto:kolstad@delos.com> (email address)
School: Norman High School
Grade: 12 (grade in school, numerical: 7, 8, 9, ..., 13)
Age: 18
CityState: Norman, OK (Non-USA people might not have a `State')
Country: USA (three letters: CAN, COL, DEU, ROM, USA, etc.)

}

Watch your mailbox for a quick (automatically-generated) reply. If you don't see one fairly soon (i.e., 15 minutes) after sending in your
solution, send another e-mail to kolstad@delos.com <mailto:kolstad@delos.com> explaining the situation (including which problem you submitted, when you sent it).


 
SPECIAL COMPILER NOTES FROM RUSS COX 

A couple themes recur over and over in the mistakes that people make as far as non-portabilities between the compilers we use (Borland C/C++ 3.1 and Turbo Pascal 7.0) and the compilers you might be using. Note that we have to use these compilers because they are what is used at the IOI. Rob Kolstad and others are working hard to change this, but until then we have to make do. If you have any questions about what I've written here, please feel free to email me (Russ Cox,
<rsc@plan9.bell-labs.com <mailto:rsc@plan9.bell-labs.com>>).

PASCAL
 I/O -

By far the biggest difference among the Pascal compilers is file input/output. The following is correct code for reading from and writing to files, as far as Turbo Pascal is concerned. If your compiler accepts it, please use it as your file I/O code. If your compiler does not, that's okay: I'll continue to rewrite them when they get submitted. But please use it if you can.

var
fin, fout: text;

begin
{ open input.txt for reading }
assign(fin, 'input.txt');
reset(fin);
{ read or readln from fin (i.e. readln(fin, foo); or the like) }
close(fin);

{ output output.txt for writing }
assign(fout, 'output.txt');
rewrite(fout);
{ write or writeln to fout (i.e. writeln(fout, foo); or the like }
close(fout);
end.

C/C++

The C++ language has evolved quite a bit since Borland produced the compiler we use. Many features are absent. The safest bet is to avoid
most of the class- and template-related features. Templates are not supported at all.

- for loops and declarations -

The biggest area where C++ has undergone serious change is the semantics of declarations within for loops. In particular, many people like to write loops like

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
some statement
for(int i=0; i<n; i++)
for(int j=0; j<n; i++)
some statement

This is correct by the latest C++ standard, but WRONG by our compilers, which implement an older standard (that's the nice thing about standards, there's so many to choose from). For us, variables declared within a for loop are active in the scope in which the for loop was declared, so the second "int i" attempts to declare a variable i when there is already a variable "i" left over from the first loop. But that's not to say that you should write

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
some statement

for(i=0; i<n; i++)
for(j=0; j<n; j++)
some statement

because now the usage of "j" in the second set of loops caused an "undeclared variable" error. The "j" in the first loop set is declared only within the "for i" loop. So once we get to the next set, there is no "j" anymore. What you really want is

for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
some statement
for(i=0; i<n; i++)
for(int j=0; j<n; j++)
some statement

but it's likely your own compiler won't accept this, since it is implement a different standard. The best solution to this is to declare all your variables outside the for loops: there is no ambiguity about what this means:

int i, j;
for(i=0; i<n; i++)
for(j=0; j<n; j++)
some statement

for(i=0; i<n; i++)
for(j=0; j<n; j++)
some statement

and it compiles no matter which standard of C++ is being used.

- Structure Definitions -

The latest version of C++ says that if you do

struct Mytype {
int foo;
};

then you can refer to "Mytype" as a type just like "int" or "long".
Unfortunately, our compiler was written before this feature was added.
If you use such structure declarations and want to refer to it in this manner, you must include a typedef as in C, i.e.:

typedef struct Mytype Mytype;
struct Mytype {
int foo;
};

and then you can refer to "Mytype" as you want to.

- #include -

Many programmers who learned C in the days before ANSI have a habit of not #including <stdio.h> or <stdlib.h>, due to a combination of implicit
function declaration at use and the fact that compilers like gcc include them automatically by default. Our compiler (and most other compilers)
do not. If you want to use FILE* operations, you *must* #include <stdio.h>. Similarly, if you want things like malloc or qsort, you *must* #include <stdlib.h>.

- type matching -

If you use C++, then you must be a lot more careful about type casting than your friends using C. In particular, be careful about the parameters to qsort. The comparison function must take two const void*'s as arguments, not const anythingelse*'s.

- DOSisms -

If you want to allocate a very large array (bigger than 64k), you must declare it huge, as in

int huge bigarray[100000];

and then any pointers you use to refer to it must be declared huge as well:

int huge *ip;

This is due to the brain deadness of DOS's memory models. It can be much slower in execution sometimes, too.

- Line Length -

Many mailers wrap lines at around 70 or 80 characters. Even if your mailer doesn't, some mailer between yours and delos.com might. This usually doesn't cause problems except in a few cases. One is when a variable name gets chopped in half. For example,

foobar[baz]

might become

foo bar[baz]

which doesn't parse the same (if at all). Another big problem with line wrap is C++ style // comments. Many people write comments that go off the end of the line boundary and are then "fixed" by mailers:

// this is a really long comment that get chopped into pieces

To fix problems like these, just don't have lines in your program longer than about 70 characters. It will make things easier for you during the contest as well, since you'll actually be able to read your whole
program.