For this contest, all contestants will use the web-based submission
procedure.  It contains a built-in five hour time limit.

Contestants should devote FIVE hours in a row (no breaks) to the
contest.  Do not use another login id to read the problems and thus
cheat.  If you are caught cheating, you are banned for life.  Don't

If you use code from a book or other source during this contest,
insert a comment in the code telling the source or you will be DQ'd
and banned.

****************** SPECIFIC INFORMATION FOR THIS CONTEST ******************

NAME:          USACO DECEMBER 2002 Contest

DATES:         08h00 GMT Friday December 13 - 15h00 GMT Tuesday December 17, 2002
               01:00 MST Friday December 13 - 08:00 MST Tuesday December 17, 2002

TIMELIMIT:     Five consecutive hours to solve all problems.
STYLE:         Individuals; no team work.
DIRECTOR:      Rob Kolstad (
QUESTIONDUDE:  Rob Kolstad (
GRADER:        Rob Kolstad (
HOTLINE:       In the USA and Canada, call the USACO Contest Hotline at
               +1 877-753-3567 toll-free with problems during the
               contest (0700-2300 MST only, please).
COMPILELIMIT:  Your program must compile in 30 seconds or less
RUNTIMELIMIT:  1.000 second max per test case (unless otherwise stated)
JUDGECOMP:     700 MHz Duron (or maybe a similar processor)
COMPILERS:     gcc version 2.96 20000731 (Red Hat Linux 7.0)
               Free Pascal Compiler version 1.0.6-beta [2002/03/13] for i386
GRADING_OS:    Linux version 2.2.16-22smp
PROCTORING:    Not required for any division.
ASSISTANCE:    Books, websites, old files, and any other non-human
               assistance is OK.  Add an explanatory comment to any
       code that is copied from a book or from an old file
       (failure to do so will lead to disqualification).  Do
       not search for exact solutions on the web or use
       solutions posted at the USACO or similar sites.
DIVISIONS:     Participants in this contest choose one of two divisions:

               * A GREEN division for the experts and those vying for
                 participation at the USACO and IOI.

               * An ORANGE division for our newer members who are still
                 working their way up to more difficult problems.  You may
                 not enter the ORANGE division if you have completed
                 Section 1.2 of the USACO training pages (the training
                 pages are found at  The top few
                 placers in the ORANGE contest will be required to move up
                 in future contests to the GREEN division.

               Choose your division by submitting solutions for that
               division.  Do a good job picking your division.
               Challenge yourself!  You might be disqualified if you
               enter both divisions.

**************** GENERAL INFORMATION FOR ALL USACO CONTESTS ***************

WHAT:   This USA Computer Olympiad 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 USA delegates to the USA
        training camp and potentially to the IOI.  Winners in each
        division will receive certificates.

WHO:    All pre-college students, world-wide, are eligible to compete.
        This is an individual contest, not a team contest.
        Visitors/observers/"for fun" entries will be scored and
        reported separately.

WHEN:   See the schedule above for the contest dates.  All work must
        be performed in a single session.

WHERE:  For non-proctored contests:  Students can work on problem
        solutions anywhere they wish.  Proctored contests require
        supervision by the proctor, of course.

HOW:    Solutions must be written in GNU C, GNU C++, or FreePascal
        and must be submitted to the web before the contest completion
        deadline.  As soon as the grading machine receives your
        program, it will compile the program and run it against a
        small number of very simple test cases.  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.

PRIZES: Each North American winner will receive a handsome certificate
        and be immortalized on the USACO Web Pages.  The policy for
        more distant winners is not determined at this time.

FEES:   No entry fees are charged.

RULES:  Consultation with people other than the contest director is

        Work by yourself, not in a team environment.

        Submit questions (one question per email, please) to the
        QUESTIONDUDE (see above) who will try to fathom an appropriate
        answer for you (and post it to the hs-computing or the web
        page message-of-the-day if required).

        Unless otherwise stated, your program must run no longer than
        the default time limit for any test case on the judge's

        Unless otherwise specified, it is NOT guaranteed that all
        possible legal datasets will be solvable within the time
        limit.  Likewise, unless specified it is NOT guaranteed that
        answer will fit in traditional computer data type (i.e.,
        integer answers might require more than 32 bits to represent).

        The judges reserve the right to increase time limits during

        Decision of the judges is final.

        Do not cheat; it's no fun for anyone.  Cheaters are often
        disqualified and banned for life.

        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 submit programs longer than 1,000,000 bytes.

        Do not use `temporary' data files.

        Do not submit programs you wrote in the past in collaboration
        with others.

        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.

        Unless otherwise stated, programs must be deterministic in
        nature and produce identical answers each time they are run
        with identical input(s).  Programs which are not deterministic
        will be disqualified.  Note that random-number based programs
        can still be entered -- they should use a fixed seed so they
        get the same answer each time.

        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.

        All problem statements are intended to be straightforward (yet
        challenging); no problems are intended to have `hidden tricks'
        in the problem statement.

        Legal but complex datasets are fair game for testing.

        If you find a problem has poor wording or an ambiguity,
        document your assumptions carefully and move on.  Send e-mail;
        we'll reply if we can.

NOTES:  Submit your solutions via the web at the address listed above.
        Register for the contest at the website, as well.  If you have
        ever registered before, your registration should still be
        valid.  You can ask the web site to send you your old id and
        password to the email address with which you registered.
        Please use the same login for each contest so we can keep
        track of everyone's progress.

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

        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

        The C/C++ compiler uses 32 bits for an int.

        C/C++ programmers:  Make sure you exit (0); when your program
        has completed.

        The grading program wants your program to compile error-free.
        You must remove all errors for your program to be graded.
        You do not need to remove all compiler warnings.

        Submitters of programs that attempt to thwart grading
        procedures will be forever disqualified from USACO contests.
        Do not join this elite club!

        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' and '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.

        Virtually every program's output is in the form of "lines".
        A line ends with newline character ('\n' in C; use writeln in
        pascal).  If your output does not contain a newline at the
        end of every line, it will be graded as incorrect.

        Small amounts of output you write to stdout or stderr are
        ignored by the judging procedure.  They are returned to you
        during the initial compile/test phase, though, if errors

        Note that test data run by the judges for grading will surely
        be more challenging than both the example data supplied with
        each problem and 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.
        This encompasses a stack size limit of 1MB and a (global)
        datasize limit of about 15MB.  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 the
        `QUESTIONDUDE' 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
                       #include <stdlib.h> for srandom/random
                       #include <sys/types.h> for srandom/random
                       #include <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.

        If, over time, you submit more than one solution for a single
        problem, only the last one submitted 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 this way so the server is available to

        Every submission is acknowledged almost instantly by an
        automated grader.

        Measuring the Intermediate CPU Usage of a Program - Pascal Users
        The grading system will observe your program's execution time
        from outside. If you want to check intermediate execution
        times during test execution or submission execution, you may
        include this line in your code:
        to include the execution function called "exectime".  This
        function has no parameters and looks just like a scalar.  Its
        value is the number of milliseconds of execution used so far.
        Here's a sample program to demonstrate its use:
             program timetest;
             var i, j, k:longint;
                 for i := 1 to 100 do begin
                     for j:=1 to 1000000 do begin
                         k := i + j + k;
                 writeln (exectime);
        This facility is only available for test executions and
        submission executions.
        Measuring the Intermediate CPU Usage of a Program - C/C++ Users
        The grading system will observe your program's execution time
        from outside.  If you want to check intermediate execution
        times during test execution or submission execution, you may
        use the `exectime' function, which returns the number of
        milliseconds your program has used so far. Here is a sample
        program to demonstrate its use:
        int exectime();
        main() {
            long i, j, k;
            for (i = 0; i < 100; i++)
                for (j=0; j < 1000000; j++)
                    k = i + j + k;
            printf ("%d ms\n", exectime());
        This facility is only available for test executions and
        submission executions.

************************* HOW TO USE WEB SUBMISSION ********************

Add identification lines to beginning of your program's source file
(omit the explanations shown on the right in parentheses):

For C, C++:

PROG: cowfun         (whatever the problem name is)
LANG: C++            (Choose one: C, C++)

Don't use //-style comments in C++ for these headers; they won't work.

For Pascal:

PROG: cowfun         (whatever the problem name is)

Then, type the filename into the obvious browser form and click "Send
It In".  Your results will be displayed shortly thereafter.

You can submit solutions to a simple problem before starting the
contest timer in order to ensure that all mechanisms work.  The
program name is `test' and the files are `' and `test.out'.
The input file contains two integers on a single line.  Sum them and
print them to a single line in `test.out'.