Courses‎ > ‎APCS - Term 1‎ > ‎Konstantinovich‎ > ‎

2019-03-05

posted Mar 5, 2019, 5:48 AM by Konstantinovich Samuel   [ updated Mar 5, 2019, 8:29 AM ]
Goal:
USACO competition problems

Today:

-Go Over Knights optimization

-Discuss USACO problems

-Read USACO bronze.

-Maybe code something.


On git have the repo:

MKS22X-USACO


    USACO.java

    in the file have the 2 public methods:

    public static int bronze(String filename);

    public static int silver(String filename);

    I will only test on valid files. Please make sure you test accordingly.


For BOTH problems the input should READ from a file according to the problem description, but you are NOT writing to a file. (Just return an int)
Some test files are attached to the post as a zip file.

March 2008
BRONZE Problem 12: Lake Making [Rob Kolstad, 2008]

Farmer John wants his cows to help him make a lake. He has mapped
the pasture where he wants to build the lake by creating a R (3 <=
R <= 100) row by C (3 <= C <= 100) column grid of six foot by six
foot squares and then by determining the average elevation (10 <=
elev_rc <= 5000) in inches for each square.

Additionally, he has trained the cows in "stomp digging". The burly
bovines travel in a herd that just exactly covers a 3x3 grid of
squares to a grid whose upper left coordinate is R_s,C_s (1 <= R_s
<= R-2; 1 <= C_s <= C-2). The cows then stomp the ground to push
it down D_s (1 <= D_s <= 40) inches. The cows are quite meticulous;
the cows at lower elevations will not commence stomping until the
rest of the herd has joined them. Thus, not all the 3x3 grid is
necessarily stomped (or perhaps some part is stomped less than some
other part).

Given an initial set of elevations, an ordered set of N (1 <= N <=
20000) stomp digging instructions, and an elevation E (0 <= E <=
5000) for the lake's final water level, determine the volume of
water (in cubic inches) that the lake will hold. It is guaranteed
that the answer will not exceed 2,000,000,000.  Presume that the
edge of the lake contains barriers so that water can not spill over
the border.

Consider a small 4 x 6 pasture to be turned into a lake. Its initial
elevations (annotated with row/column numbers) are:

                      column
                  1  2  3  4  5  6
         row 1:  28 25 20 32 34 36
         row 2:  27 25 20 20 30 34
         row 3:  24 20 20 20 20 30
         row 4:  20 20 14 14 20 20

Interpreting the map, we see a hill in the upper right corner that
rises to elevation 36; a small hill also rises to elevation 28 in
the upper left corner. The middle of row 4 has a slight depression.
After the cow-stomping instruction "1 4 4", the pasture has these
elevations:
                  1  2  3  4  5  6
         row 1:  28 25 20 32 32 32
         row 2:  27 25 20 20 30 32
         row 3:  24 20 20 20 20 30
         row 4:  20 20 14 14 20 20

Note that only three squares were stomped down. The other six sets
of cows were waiting for the stompers to get to their level, which
never happened.  After stomping down the upper left corner with
this instruction "1 1 10", the pasture looks like this:

                  1  2  3  4  5  6
         row 1:  18 18 18 32 32 32
         row 2:  18 18 18 20 30 32
         row 3:  18 18 18 20 20 30
         row 4:  20 20 14 14 20 20

If the final elevation of the lake is to be 22 inches, the pasture
has these depths:
                  1  2  3  4  5  6
         row 1:   4  4  4 -- -- --
         row 2:   4  4  4  2 -- --
         row 3:   4  4  4  2  2 --
         row 4:   2  2  8  8  2  2

for a total aggregated depth of 66. Calculate the volume by multiplying
by 6 feet x 6 feet = 66 x 72 inches x 72 inches = 342,144 cubic
inches.

Write a program to automate this calculation.

PROBLEM NAME: makelake

INPUT FORMAT:

* Line 1: Four space-separated integers: R, C, E, N

* Lines 2..R+1: Line i+1 describes row of squares i with C
        space-separated integers

* Lines R+2..R+N+1: Line i+R+1 describes stomp-digging instruction i
        with three integers: R_s, C_s, and D_s

SAMPLE INPUT (file makelake.in):

4 6 22 2
28 25 20 32 34 36
27 25 20 20 30 34
24 20 20 20 20 30
20 20 14 14 20 20
1 4 4
1 1 10

INPUT DETAILS:

As per the example from the text.

OUTPUT FORMAT:

* Line 1: A single integer that is the volume of the new lake in cubic
        inches

SAMPLE OUTPUT (file makelake.out):

342144


**********************************************************


**********************************************************

SILVER Problem 7: Cow Travelling [Aram Shatakhtsyan, 2007] Searching for the very best grass, the cows are travelling about the pasture which is represented as a grid with N rows and M columns (2 <= N <= 100; 2 <= M <= 100). Keen observer Farmer John has recorded Bessie's position as (R1, C1) at a certain time and then as (R2, C2) exactly T (0 < T <= 15) seconds later. He's not sure if she passed through (R2, C2) before T seconds, but he knows she is there at time T. FJ wants a program that uses this information to calculate an integer S that is the number of ways a cow can go from (R1, C1) to (R2, C2) exactly in T seconds. Every second, a cow can travel from any position to a vertically or horizontally neighboring position in the pasture each second (no resting for the cows). Of course, the pasture has trees through which no cow can travel. Given a map with '.'s for open pasture space and '*' for trees, calculate the number of possible ways to travel from (R1, C1) to (R2, C2) in T seconds. PROBLEM NAME: ctravel INPUT FORMAT: * Line 1: Three space-separated integers: N, M, and T * Lines 2..N+1: Line i+1 describes row i of the pasture with exactly M characters that are each '.' or '*' * Line N+2: Four space-separated integers: R1, C1, R2, and C2. SAMPLE INPUT (file ctravel.in): 4 5 6 ...*. ...*. ..... ..... 1 3 1 5 INPUT DETAILS: The pasture is 4 rows by 5 colum. The cow travels from row 1, column 3 to row 1, column 5, which takes exactly 6 seconds. OUTPUT FORMAT: * Line 1: A single line with the integer S described above. SAMPLE OUTPUT (file ctravel.out): 1 OUTPUT DETAILS: There is only one way from (1,3) to (1,5) in exactly 6 seconds (and it is the obvious one that travels around the two trees).
ċ
testCases.zip
(13k)
Konstantinovich Samuel,
Mar 5, 2019, 5:48 AM
Comments