Instructions
 
		To Enter Contest Go To : http://ace.delos.com/contestgate
                  USACO NOVEMBER 2004 QUALIFYING CONTEST

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

FOUR DIVISIONS NOW, TWO BY INVITATION

     This contest enables participants to qualify for the GOLD and
     SILVER divisions.  The BRONZE division will be open to all
     comers.  Future contests will require an invitation for GOLD
     and SILVER contestants.

CONTEST LENGTH IS THREE HOURS

     Contestants should devote THREE hours in a row (no breaks) to
     the contest.  Do not use another login id to read the problems
     and thus cheat.  Do not collaborate with others. IF YOU ARE
     CAUGHT CHEATING, YOU ARE BANNED FOR LIFE FROM ALL USACO
     ACTIVITIES.  DON'T CHEAT.  THERE ARE NO SECOND CHANCES.

LOWER TIME LIMITS THIS YEAR

     Time limits are lower now: 0.3 seconds.

CONTACTING THE CONTEST ORGANIZERS

     MAIL: If you send contest email, please make sure the subject
     is just the word 'contest' so it shows up in the mailbox
     prominently.

USING CODE FROM OTHER SOURCES

     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 disqualified and banned.

JAVA

     Java is available!  It's GNU Java and relatively untested, but
     the sample programs work.  Let us know if you have trouble
     with it.  Note that Java might tell you it suffered a signal
     instead of a timeout.  In either case, the Java program is not
     correct. Note that you must put your entire Java program in a
     single file.

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

NAME:          USACO November 2004 Contest

DATES:         08h00 GMT Friday Nov 5 - 15h00 GMT Tuesday Nov 8
               01:00 MST Friday Nov 5 - 08:00 MST Tuesday Nov 8
               Note that you must start the contest hours before
               this end time if you wish to have enough time to
               solve the problems.

TIMELIMIT:     Three consecutive hours to solve all problems.

STYLE:         Individuals; no team work.

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

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

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:  0.300 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.  Java times are scaled and reported as
               0.. 0.3 seconds, though.

JUDGECOMP:     700 MHz Duron

COMPILERS:     gcc version 2.96 20000731 (Red Hat Linux 7.0)
               Free Pascal Compiler version 1.0.10 [2003/06/26] 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 problems to
               solve.  Each problem has a point value associated
               with it (50, 100, or 500).  Qualifying for the
               GOLD division will require somewhere between 500
               and 700 points.  Qualifying for the SILVER division
               will require somewhere between 200 and 300 points.
               Read the problems; choose those that you think you
               solve.  The time limit is three hours.

ANALYSIS MODE:  Starting with this contest, 'analysis mode' will be
               available when the contest ends.  You can re-test your
               programs to see how they would do with various changes.

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

These details have not changed since the first 2003-2004 contest.

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
        about 16MB of total memory use.  This encompasses a stack
        size limit of 2MB 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'.