

        castle "Castles at the Beach" "Russ Cox"


The cows love to build castles at the beach. They construct a rock
foundation on which they subsequently pile sand.
The N (1 <= N <= 200) rocks on the beach are rectangular solids
with a width, breadth, and height (all positive signed 32 bit
integers). For construction, the rocks can be rotated (exchanging
their width and breadth, but they maintain the same height).
Given a list of the dimensions of available rocks and a desired height
H (1 <= H <= 5,000), find a way to build a structurally sound
pile with that height. For structurally sound foundations, a rock can
only be placed on another rock if the upper rock's bottom completely
fits on the lower rock's top. Rocks of the same size can be stacked
(i.e., a 3 x 4 rock can be stacked onto a 3 x 4 rock).

Input Format
Line 1: Two integers: N and H
Lines 2..N+1: Three integers: the width, breadth, and height of a rock.
The rocks are specified in order 1, 2, 3, ..., N.

Sample Input
5 20
1 1 10
3 7 3
2 4 3
1 8 7
5 2 4

Output Format
A set of lines, each with a single integer specifying a rock. The
set specifies any sequence of rocks that form a structurally sound
pile of exactly height H. The bottom rock is specified first; the top rock
is specified last. Output a single line with a 0 if no sequence can be
created.

Sample Output
2
5
3
1


         lifecow "Lifecows" "Russ Cox"


In addition to watching the cows that swim in the water, lifecows must
also watch the cows on the beach to ensure the cows use their sunscreen
appropriately.
Conceptually, the beach is a W*H

(1 <= W*H <= 70, cred, sau 1<=W,H<=70, ceea
ce ar complica problema)

grid of square beach units. A lifecow (whose ``direction'' is denoted
by a "W" , "A" , ">" , or "<" standing
in a given square can see the eight beach squares as shown in the
four patterns below in addition to the square in which the lifecow
stands (the ``*''s are guarded; the ``.''s are not):

         * * V * *        * . .       . . *       . . * . .
         . * * * .        * * .       . * *       . * * * .
         . . * . .        > * *       * * <       * * A * *
                          * * .       . * *
                          * . .       . . *

As it turns out, some beach squares are overgrown with dune grass
and seaweed; those don't need to be guarded, but they can be guarded
if things turn out that way. You can only place a lifecow on a
square that requires guarding.
Given a grid indicating which beach squares need guarding, determine
how to place the smallest number of lifecow stands so that each square
that needs guarding is guarded.

Input Format
Line 1: Two integers, W and H
Lines 2..H+1: Each line contains W integers, each 1 or 0. The squares
marked 1 must be guarded.

Sample Input
5 3
1 1 0 1 1
0 1 1 1 0
0 0 1 0 0

Output Format
H lines of W space-separated integers just as in the input but with
appropriate 1's replaced by one of characters {`V', 'A', `<', `>'} where
a lifecow is stationed.
The character chosen reflects the direction the lifecow faces.

Sample Output
1 V 0 V 1
0 1 1 1 0
0 0 A 0 0
[Other answers are possible.]




 invest "Investment Banking" "Brian Dean"


Since selling moo.com in March 2000 for record profits, the cows have
started dabbling in investment banking. They have D (1 <= D <= 400)
total dollars to invest into as many as N (1 <= N <= 400) different
companies for one year. They may choose to invest in any combination
of the available companies, or even not to invest at all (and just keep
their initial D dollars). They can invest no more than one time in
any company.
Given an N by D matrix of integers, A (0 <= A(i,j) <= 100,000), such
that A(i,j) gives the amount of value the cows get in return for
investing j dollars in the i'th company, what is the maximum amount of
money the cows can make?

Input Format
Line 1: Two integers, D and N
Lines 2..N+1: D integers 0...100,000 on each row, giving the
amount of money they get at the end of the year for investing
1, 2, ..., D dollars in a company.

Sample Input
5 3
0 3 5 7 0
0 1 3 0 0
1 0 4 8 0

Output Format
One line with a single integer that is the maximum amount of money the
cows have at the end of the year.

Sample Output
9

