Usaco Oct07 Silver

Part of USACO Oct07

**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Two problems numbered 6 through 7
**********************************************************************

Problem 6: Bessie's Secret Pasture [Jeffrey Wang, 2007]

Farmer John has cut an almost unlimited number of square pieces of
sod (grass sections) of all integer side-lengths from the pasture
(sometimes FJ doesn't engage the blade properly and even makes a
0-sided sod squares). He has placed them in nicely organized piles
that Bessie spotted one afternoon.

Bessie, always hoping to put delicious grass in her secret pasture,
decided to carry precisely four of these sod sections over to her
pasture and carve them into 1x1 sections in order to tile its N (1
<= N <= 10,000) unit-square sections.

Bessie is interested in knowing how many different ways she can
choose four sod sections to tile her secret pasture. If she had a
pasture of size 4, she might haul sod squares in these five different
ways: (1,1,1,1), (2,0,0,0), (0,2,0,0), (0,0,2,0), (0,0,0,2).  Order
counts: (4,3,2,1) is a different way of choosing than (1,2,3,4).

PROBLEM NAME: secpas

INPUT FORMAT:

* Line 1: A single integer: N

SAMPLE INPUT (file secpas.in):

4

OUTPUT FORMAT:

* Line 1: A single integer that is the number of different ways Bessie
        can choose four sod sections for her pasture

SAMPLE OUTPUT (file secpas.out):

5

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

Problem 7: Obstacle Course [Paul Christiano, 2007]

Consider an N x N (1 <= N <= 100) square field composed of 1
by 1 tiles. Some of these tiles are impassible by cows and are
marked with an 'x' in this 5 by 5 field that is challenging to
navigate:

               . . B x .
               . x x A .
               . . . x .
               . x . . .
               . . x . .

Bessie finds herself in one such field at location A and wants to
move to location B in order to lick the salt block there.  Slow,
lumbering creatures like cows do not like to turn and, of course,
may only move parallel to the edges of the square field. For
a given field, determine the minimum number of ninety degree turns
in any path from A to B. The path may begin and end with Bessie
facing in any direction. Bessie knows she can get to the salt lick.

PROBLEM NAME: obstacle

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N + 1: Line i+1 represents row i of the field with N
        characters as above (i.e., '.', 'x', 'A', and 'B'); no spaces
        are present on a line

SAMPLE INPUT (file obstacle.in):

3
.xA
...
Bx.

INPUT DETAILS:

The cow needs to progress from the top right to the bottom left of
the field, without passing through the top center or bottom center
squares.

OUTPUT FORMAT:

* Line 1: A single integer, the minimum number of turns the cow must
        make in a traversal

SAMPLE OUTPUT (file obstacle.out):

2

OUTPUT DETAILS:

The cow must make at least 2 turns: For example, the cow may start
by facing south, move south, turn to face west, move west, move
west, then turn to face south, and finally move south into the B
square.

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