USACO FALL 2001 PROGRAMMING CONTEST

*********************************** NEWS **********************************

For this contest, all contestants will use the web-based submission
procedure.

The "window" for the contest has been reduced to four days.  Few people
used the other days.

Contestants should devote three hours in a row (no breaks) to the contest.

If you haven't read the rules below completely, you should!  They are
almost as brief as possible.

Don't read the problems (after the rules, below) until you are ready to
start your three hour contest/coding time.

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

NAME:          USACO FALL 2001 Contest

DATES:         0800 MT Friday November 2 - 0800 MT Tuesday November 6, 2001

TIMELIMIT:     Three hours in a row to solve all problems.

SOLUTIONSTO:   http://ace.delos.com/contestgate

DIRECTOR:      Rob Kolstad (<kolstad@ace.delos.com>)

QUESTIONDUDE:  Rob Kolstad (<kolstad@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).  This service will
               not be available during mid-day Friday.

RUNTIMELIMIT:  1.000 second max per test case (unless otherwise stated)

JUDGECOMP:     700 MHz Duron

COMPILERS:     gcc version 2.96 20000731 (Red Hat Linux 7.0)
               Free Pascal Compiler version 1.0.4 [2001/01/22] 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.

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 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 are eligible.  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 returned submitted 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 winner will receive a handsome certificate and be immortalized
        on the USACO Web Pages.

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.

        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.

        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.

        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.

        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.

        The registration 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.

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

        Pascal programmers:  there is no way to find out the program's
        ongoing execution time for this contest.  Happily, you won't
        need it.

        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 everyone.

        Every submission is acknowledged almost instantly by an automated
        grader.

************************* NOTES ON 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)
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 before the contest 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 them to a single line in `test.out'.