Instructions
 
For this contest, all contestants will use the web-based submission
procedure.  It contains a built-in four hour time limit.
 
Contestants should devote FOUR 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
cheat.
 
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.
 
Java is available!  It's GNU Java and relatively untested, but the
sample programs work.  Let us know if you have trouble with it.
 
****************** SPECIFIC INFORMATION FOR THIS CONTEST 
 
NAME:          USACO FALL 2003 Contest
 
DATES:         08h00 GMT Friday November 14 - 15h00 GMT Tuesday November 18, 2003
               01:00 MST Friday November 14 - 08:00 MST Tuesday November 18, 2003
 
TIMELIMIT:     Four consecutive hours to solve all problems.
 
STYLE:         Individuals; no team work.
 
SOLUTIONSTO:   http://ace.delos.com/contestgate
 
DIRECTOR:      Brian Dean (<bdean@mit.edu>)
 
QUESTIONDUDE:  <questions@ace.delos.com>
 
GRADER:        Rob Kolstad (<kolstad@ace.delos.com>)
 
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)
               NOTE: Java users get 5x the normal runtime limit, since
               Java code runs more slowly.  The judges reserve the right
               to change this constant at any time for any reason.
 
JUDGECOMP:     700 MHz Duron
 
COMPILERS:     gcc version 2.96 20000731 (Red Hat Linux 7.0)
               Free Pascal Compiler version 1.0.6-beta [2002/03/13] for i386
               gcj based upon gcc 3.3.2
 
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
                 http://train.usaco.org).  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 will 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++, FreePascal, or
        GNU JAVA 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 all winners 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
        prohibited.
 
        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
        computer.
 
        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
        answers will fit in a 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
        grading.
 
        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 access the contest
        using more than one signon.
 
        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 that 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
        problems.
 
        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., `cow.in').  Do not specify a complete path
        name in your `open' statement, just `cow.in'.  Note that
        filenames are case-sensitive.  If the problem says `cow.in'
        then you must use `cow.in' 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
        occur.
 
        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.
 
        Unless otherwise stated, 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);   
                  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.  It
        is unlikely you want to use a seed other than a constant as
        that would cause your program to produce results which
        potentially differ from run to run.
 
        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 will always
        available to everyone.
 
        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:
        
                     {$i extime.inc}
        
        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;
             {$i extime.inc}
             var i, j, k:longint;
             begin
                 for i := 1 to 100 do begin
                     for j:=1 to 1000000 do begin
                         k := i + j + k;
                     end;
                 end;
                 writeln (exectime);
             end.
        
        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.
 
        Measuring the Intermediate CPU Usage of a Program - Java Users
 
        Sorry, this facility is not available:
 
************************* HOW TO USE WEB SUBMISSION ********************
 
Add identification lines like these to the beginning of your program's
source file (omit the explanations shown on the right in parentheses):
 
For C, C++, JAVA:
 
/*
PROG: cowfun         (whatever the problem name is)
LANG: C++            (Choose one: C, C++, JAVA)
*/
 
Don't use //-style comments for these headers; they won't work.
 
For Pascal:
 
{
PROG: cowfun         (whatever the problem name is)
LANG: PASCAL
}
 
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 `test.in' and `test.out'.
The input file contains two integers on a single line.  Sum them and
print the sum to a single line in the file named `test.out'.