Usaco Feb11 Silver

Part of USACO Feb11

**********************************************************************
                           SILVER PROBLEMS
**********************************************************************
                  Three problems numbered 6 through 8
**********************************************************************

Problem 6: Cow Line [Lewin Gan, 2011]

The N (1 <= N <= 20) cows conveniently numbered 1...N are playing
yet another one of their crazy games with Farmer John. The cows
will arrange themselves in a line and ask Farmer John what their
line number is. In return, Farmer John can give them a line number
and the cows must rearrange themselves into that line.

A line number is assigned by numbering all the permutations of the
line in lexicographic order.

Consider this example:
Farmer John has 5 cows and gives them the line number of 3.
The permutations of the line in ascending lexicographic order:
1st: 1 2 3 4 5
2nd: 1 2 3 5 4
3rd: 1 2 4 3 5
Therefore, the cows will line themselves in the cow line 1 2 4 3 5.

The cows, in return, line themselves in the configuration "1 2 5 3 4" and 
ask Farmer John what their line number is.

Continuing with the list:
4th : 1 2 4 5 3
5th : 1 2 5 3 4
Farmer John can see the answer here is 5

Farmer John and the cows would like your help to play their game.
They have K (1 <= K <= 10,000) queries that they need help with.
Query i has two parts: C_i will be the command, which is either 'P'
or 'Q'.

If C_i is 'P', then the second part of the query will be one integer
A_i (1 <= A_i <= N!), which is a line number. This is Farmer John
challenging the cows to line up in the correct cow line.

If C_i is 'Q', then the second part of the query will be N distinct 
integers B_ij (1 <= B_ij <= N). This will denote a cow line. These are the 
cows challenging Farmer John to find their line number.

PROBLEM NAME: line

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K

* Lines 2..2*K+1: Line 2*i and 2*i+1 will contain a single query.

Line 2*i will contain just one character: 'Q' if the cows are lining
up and asking Farmer John for their line number or 'P' if Farmer
John gives the cows a line number.

If the line 2*i is 'Q', then line 2*i+1 will contain N space-separated
integers B_ij which represent the cow line. If the line 2*i is 'P',
then line 2*i+1 will contain a single integer A_i which is the line
number to solve for.

SAMPLE INPUT (file line.in):

5 2
P
3
Q
1 2 5 3 4

OUTPUT FORMAT:

* Lines 1..K: Line i will contain the answer to query i.

If line 2*i of the input was 'Q', then this line will contain a
single integer, which is the line number of the cow line in line
2*i+1.

If line 2*i of the input was 'P', then this line will contain N
space separated integers giving the cow line of the number in line
2*i+1.

SAMPLE OUTPUT (file line.out):

1 2 4 3 5
5

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

Problem 7: Best Parenthesis [Jeffrey Wang, 2009]

Recently, the cows have been competing with strings of balanced
parentheses and comparing them with each other to see who has the
best one.

Such strings are scored as follows (all strings are balanced): the
string "()" has score 1; if "A" has score s(A) then "(A)" has score
2*s(A); and if "A" and "B" have scores s(A) and s(B), respectively,
then "AB" has score s(A)+s(B). For example, s("(())()") =
s("(())")+s("()") = 2*s("()")+1 = 2*1+1 = 3.

Bessie wants to beat all of her fellow cows, so she needs to calculate
the score of some strings. Given a string of balanced parentheses
of length N (2 <= N <= 100,000), help Bessie compute its score.

PROBLEM NAME: paren

INPUT FORMAT:

* Line 1: A single integer: N

* Lines 2..N + 1: Line i+1 will contain 1 integer: 0 if the ith
        character of the string is '(',  and 1 if the ith character of
        the string is ')'

SAMPLE INPUT (file paren.in):

6
0
0
1
1
0
1

INPUT DETAILS:

This corresponds to the string "(())()".

OUTPUT FORMAT:

* Line 1: The score of the string. Since this number can get quite
        large, output the  score modulo 12345678910.

SAMPLE OUTPUT (file paren.out):

3

OUTPUT DETAILS:

As discussed above.

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

Problem 8: The Triangle [Lewin Gan, 2011]

For her spectacular milk output for the previous month, Farmer John
has awarded Bessie a prize -- with a twist.  He has given her a
triangular grid with N (1 <= N <= 700) rows (whose lengths vary
from 1 through N, of course). Row i of the the grid has i values
labeled v_ij (-1,000,000,000 <= v_ij <= 1,000,000,000) where j is
in the range 1..i.

Bessie chooses a sub-triangle whose side length is at least K (1
<= K <= 20; 1 <= K <= N) within the triangular grid. The sub-triangle
is another triangular grid which might be oriented the same as the
original triangle or might be 'upside down' with its shorter rows
on the bottom instead of the top.

After she chooses her sub-triangle, Farmer John will take the average
of all the numbers in the sub-triangle, discarding the digits to
the right of the decimal point, and give her that many gold coins
(or take that many gold coins from her if the number is negative).
Naturally, Bessie would like to maximize her prize (or minimize her
loss). Help her solve this problem.

By way of example, Bessie is given this triangular grid with N = 3
rows and must choose a sub-triangle with a side length of at least
K = 2. A graphical representation of the triangle is shown below:

    / \
   / 5 \
  /-8  4\
 /2 -3  6\
 ---------

She could choose any of five valid sub-triangles (one of which is
the entire original triangle):
                                                   /\
    / \         / \        / \         / \        /5 \       
   / 5 \       / \5\      / 5 \       / 5/\      /----\    
  /-8  4\     /-8 \4\    /-8  4\     /-8/ 4\    /\-8 4/\ 
 /2 -3  6\   / 2 -3\6\  /-------\   / 2/-3 6\  / 2\-3/6 \ 
 ---------   ---------  -2  -3  6   ---------  ----------  
  entire      lower        top          lower     upside
 triangle     left                      right      down

The one that is lined below is the one with the highest average:

    / \
   / 5/\
  /-8/ 4\
 / 2/-3 6\
 ---------

The average of this sub-triangle is (4+6-3)/3, which is about
2.3333...; without the fraction, the answer is 2.

Help Bessie calculate the maximum amount of coins which she could
receive.

TIME LIMIT: 2 seconds

MEMORY LIMIT: 32 MB

PROBLEM NAME: tri

INPUT FORMAT:

* Line 1: Two space-separated integers: N and K

* Lines 2..N+1: Line i+1 will contain i space-separated integers: v_ij

SAMPLE INPUT (file tri.in):

3 2
5
-8 4
2 -3 6

OUTPUT FORMAT:

* Line 1: The maximum number of coins that Bessie can receive (or, if
        negative, the best she can do for her loss).

SAMPLE OUTPUT (file tri.out):

2

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