WHAT: The USA 2001 Computer Olympiad Winter Contest is a computer programming contest open to all pre-college students throughout the world. Several problems are presented for solution in each of two divisions. 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 divisions will receive awards at the end of the season.

Solutions must be written in GNU C/C++ or FreePascal and must be returned via e-mail by the contest completion deadline. As soon as the grading machine receives your program, it will be compiled and run against a very simple test case. The results will be returned to you very quickly. This should enable you to fix incompatibilities, misspelled filenames, and the like. This means that the judges will rarely, if ever, make changes to your program during grading.
Be sure to send in questions if you think the
compilers are misbehaving.

WHO: All pre-college students are eligible. This is an individual contest, not a team contest.

WHERE: Students can work on problem solutions anywhere they wish.

WHEN: Problems will be posted to the mailing list between during the morning US Mountain Standard Time (0730-0800 or so) on Wednesday, Nov 8. All results are due one week later, Nov.15, by 0800 am US Mountain Standard Time (1400 GMT). There is a five hour time limit and a three session limit for working on problems during the week.

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

FEES: No entry fees are charged.


  1. Consultation with people other than the contest director is prohibited.
  2. Do not work in a team environment.
  3. Submit questions (one per email, please) to <> 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.
  4. Be sure to check your e-mail occasionally for contest updates, should there be any.
  5. Any amount of consultation with written materials (such as programming books) is allowed (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.
  6. 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).
  7. Spend no more than a total of five hours solving problems. Really.
  8. Submit source code for the problems to the contest coordinators via e-mail to <> (see below for format).
  9. For the final results, an automatic grading system will check your solutions for correctness grader 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.
  10. The grader runs your programs on UNIX, not DOS/Windows. This means that if you reference memory out of bounds, your program will terminate. Furthermore, it means that referencing uninitialized memory will yield different answers than running on DOS/Windows. If you choose to dispute the run of a program, make sure you have initialized all your variables and do not reference memory in a way different from your declarations.
  11. Unless otherwise stated, your program must run no longer than
    5 seconds for any test case on the judge's computer (approximately 400 MHz Pentium II).Because the FreePascal compiler generates slightly less efficient code, runtimes for Pascal programs will be scaled appropriately.
  12. Unless otherwise specified, it is NOT guaranteed that all possible legal datasets will be solvable within the time limit.
  13. The judges reserve the right to increase time limits during
  14. Decision of the judges is final.
  15. Do not cheat; it's no fun for anyone. Cheaters are often disqualified and banned.
  16. Do not use inline assembler statements.
  17. 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.
  18. Do not submit programs you wrote in collaboration with others.
  19. Do not use `temporary' data files.
  20. 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.
  21. Problems are intended to be algorithmic in nature, thus clever algorithms and/or data structures might be necessary to solve all test cases correctly and within the time limits.
  22. All problem statements are intended to be straightforward (yet challenging); no problems are intended to have `hidden tricks' in them.
  23. Legal but complex datasets are fair game for testing.
  24. 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.

  The registration information at the front of each solution should be in precisely the format as requested below.

  •  Be sure that each program you submit has identically the same registration information. Otherwise, you might be considered to be multiple contestants.
  •  Programs that consist of essentially nothing more than print statements will not be graded. Programs must compute the requested answers. Do not use precomputation to solve these problems.
  • The C/C++ compiler uses 32 bits for an int. Yay.
  • C/C++ programmers: Make sure you exit (0); at the end of your program.
  • The grading program wants your program to compile both error- and warning-free. You must remove all errors and warnings for your program to be graded.
  • Submitters of programs that attempt to thwart grading procedures will be forever disqualified from USACO contests. Do not join this elite club!
  • Rob Kolstad <> is this contest's director, question-answerer, and grader.
  • All programs read their input from a file named in the problem statement (e.g., `'). Do not specify a complete path name in your `open' statement, just `'. Note that filenames are case-sensitive. If the problem says `' then you must use `' since `CoW.In' will not work.
  • All programs write their output to a file named in the problem statement (e.g., `cow.out'); do not specify a path name in your `open' statement, just `cow.out'. Like the input filenames, output filenames are case-sensitive.
  • Small amounts of output you write to stdout or stderr is ignored by the judging procedure. They are returned to you during the initial compile/test phase, though, if errors occur.
  • Note that test data run by the judges for grading will surely be more challenging than the example data supplied with each problem and, similarly, the data used to check that your program is submitted correctly.
  • The scorer will assess scoring penalties when certain rules are abused.
  • Your programs will be limited to 16MB of total memory use: 15MB of global data plus 1MB of stack space. That means you can't put really large data structures on the stack, which is where all local variables are allocated.
  • Note that all the examples are intended to be correct and helpful. If you find an apparent error, please contact <> so he can correct the problem. Some of the examples have only been double-checked, not triple-checked.
  • The scorer will compile your program with optimization turned on. For C/C++ programmers, the #pragma -fhandle-exceptions is handled correctly.
  • C programmers: #include <math.h> if you use math functions
    <stdlib.h>  for srandom/random
    <sys/types.h> for srandom/random
    <unistd.h> for srandom/random

              which are called like this:
                        srandom(seed);   /* use getpid() for a random seed */
                        randominteger = random();
              where the randominteger will be between 0..2^31-1.  Note that
              random()%N will be a random integer in the range 0..N-1.
  • C++ programmers: advanced template features do not work correctly. Avoid them.
  • No additional 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 <>. 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. There is no penalty for re-submitting -- in fact, you can use the technique to make sure our compiler likes your program(s) or even to run timing tests. Try not to submit more than 25 solutions per day.

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

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!):


... [header comments -- see below for format] ...

... [text of program in C or Pascal] ...

### END


* 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 form.

* Do not add blanks or other characters to make the comments look nice. Use them just as they are shown.

* 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 the `### END' line are ignored (e.g., signatures)

* All registration lines (below) are required; your program won't be graded until they are filled in.

* If you insist on using them, put compiler directives just before the header (as shown below) but nevertheless after the `### PROGRAM' marker. Choose your directives based on your own experience. Almost every program will run perfectly well with no other directives. Optimization is already set for -O2 for both compilers.


Here is the standard C/C++ header filled in for a youthful Rob Kolstad (my explanatory comments on far right -- do not include them). You should include a header with your own data for each problem (save it in a file on your computer for easy inclusion on subsequent submissions):


/* (This goes on a separate line)

Problem: 1 (problem number)
Name: Rob Kolstad (First name then last name)
Email: (Email address)
School: Norman High School
Grade: 2002 (Year you will graduate from high school)
Age: 17
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)


Here is the PASCAL header filled in for a youthful Rob Kolstad (my
comments on far right -- do not include them). You should include a
header with your own data for each problem (save it in a file on your
computer for easy inclusion on subsequent submissions):


{ (on a line by itself, please)
Problem: 1 (problem number)
Name: Rob Kolstad (first name then last name)
Email: (email address)
School: Norman High School
Grade: 2002 (year you will graduate from high school) Age: 17
CityState: Norman, OK (Non-USA people might not have a `State') Country: USA (three letters: CAN, COL, DEU, ROM, USA, etc.)


If you live somewhere that has a city but no state, please omit the state (for example, CityState: Amsterdam).