Usaco Feb10 Bronze

Part of USACO Feb10

**********************************************************************
                           BRONZE PROBLEMS
**********************************************************************
                  Three problems numbered 11 through 13
**********************************************************************

Problem 11: Scavenger Hunt [Damon Doucet, 2010]

Farmer John has scattered treats for Bessie at special places in
the pasture.  Since everyone knows that smart cows make tasty milk,
FJ has placed the treats at locations that require Bessie to think.
He has given her two numbers, P and Q (1 <= P <= 6,000; 1 <= Q <=
6,000), and she has to check every point in the pasture whose
x-coordinate is a factor of P and whose y-coordinate is a factor
of Q to find her treat.

Suppose FJ gives Bessie P = 24 and Q = 2. Here are all of their
respective factors:

P = 24 => 1, 2, 3, 4, 6, 8, 12, 24
Q = 2 => 1, 2

Bessie would thus check grid locations: (1, 1), (1, 2), (2, 1), (2,
2), (3, 1)...

Help Bessie by printing all of the points she ought to check.

PROBLEM NAME: scavhunt

INPUT FORMAT:

* Line 1: Two space separated integers: P and Q

SAMPLE INPUT (file scavhunt.in):

24 2

OUTPUT FORMAT:

* Lines 1..?: A complete list of unique pairs of space-separated
        integers sorted by the first number and, if tied, the second
        number: a factor of P followed by a factor of Q

SAMPLE OUTPUT (file scavhunt.out):

1 1
1 2
2 1
2 2
3 1
3 2
4 1
4 2
6 1
6 2
8 1
8 2
12 1
12 2
24 1
24 2

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

Problem 12: Feeding Time [Damon Doucet, 2010]

It's Bessie's feeding time, and Farmer John is trying to decide
where to put her. FJ has a farm that comprises W x H (1 <= W <=
750; 1 <= H <= 750) squares and is partitioned into one or more
separate pastures by rocks both large and small. Every pasture
contains some grass and some rocks.

Bessie is a hungry little cow and just loves to eat, eat, eat her
grass. She can move from any square to any other square that is
horizontally, vertically, or diagonally adjacent. Bessie can't cross
the rocks because they hurt her feet, and, of course, she can't
leave the farm. Bessie wants to know the maximum number of squares
of grass that she can eat.

FJ has a map of his farm, where a '.' represents a square of grass,
and a '*' represents a rock. Consider this 10x8 map and a detailed
breakdown of the extent of each of its three pastures:

      ...*....**  |  111*....**   ...*2222**    ...*....**
      ..**....**  |  11**....**   ..**2222**    ..**....**
      ...*....**  |  111*....**   ...*2222**    ...*....**
      ...**.*.**  |  111**.*.**   ...**2*2**    ...**.*.**
      ***.**.***  |  ***1**.***   ***.**2***    ***.**.***
      ...**.*.**  |  111**.*.**   ...**2*2**    ...**.*.**
      ...*.*****  |  111*.*****   ...*2*****    ...*.*****
      ...***..**  |  111***..**   ...***..**    ...***33**

Pasture 1 has 21 squares; pasture 2 has 18 squares; pasture 3 has
2 squares. Thus Bessie should choose pasture 1 with 21 squares to
maximize the grass she can eat.

PROBLEM NAME: feedtime

INPUT FORMAT:

* Line 1: Two space-separated integers: W and H

* Lines 2..H+1: Line i+1 describes field row i with W characters (and
        no spaces), each either '.' or '*'

SAMPLE INPUT (file feedtime.in):

10 8
...*....**
..**....**
...*....**
...**.*.**
***.**.***
...**.*.**
...*.*****
...***..**

OUTPUT FORMAT:

* Line 1: A single integer that represents the maximum number of
        squares of grass that Bessie can eat.

SAMPLE OUTPUT (file feedtime.out):

21

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

Problem 13: Toy Shopping [Damon Doucet, 2010]

Bessie wants some toys. She's been saving her allowance for years,
and has an incredibly huge stash. However, she is quite frugal and
wants to get the best value for her cash. In fact, she has decided
only to buy exactly three different toys of the N (3 <= N <= 25,000)
offered at the Bovine Plaything Palace.

Toy i brings Bessie J_i (0 <= J_i <= 1,000,000) microbundles of joy
and has price P_i (0 < P_i <= 100,000,000). Bessie has enough money
to buy any three toys that she chooses.

Bessie wants to maximize the sum of her happy-frugal metric (which
is calculated as J_i/P_i -- joy divided by price) for the three
toys she chooses. Help Bessie decide which toys she should buy.
The answer is guaranteed to be unique.

Assume that the Bovine Plaything Palace offers 6 different toys for
Bessie:

        i    Joy       Price       Happy-Frugal Metric
        -    ---       -----       -------------------
        1      0        521               0.00000
        2    442        210               2.10476...
        3    119        100               1.19000
        4    120        108               1.11111...
        5    619        744               0.83198...
        6     48         10               4.80000

Bessie would choose toy 6 (HFM = 4.80), toy 2 (HFM = 2.10), and toy
3 (HFM = 1.19).

PROBLEM NAME: toyshop

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: J_i
        and P_i

SAMPLE INPUT (file toyshop.in):

6
0 521
442 210
119 100
120 108
619 744
48 10

OUTPUT FORMAT:

* Line 1: The total price that Bessie will have to pay

* Lines 2..4: In descending order sorted by the happy-frugal metric,
        the 1-based index of the toys that Bessie should buy, one per
        line

SAMPLE OUTPUT (file toyshop.out):

320
6
2
3

**********************************************************************
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License