## A. Maximum in Table

Simulation.

```n = int(raw_input())
g = [[1 for i in xrange(n)] for j in xrange(n)]

for i in xrange(1, n):
for j in xrange(1, n):
g[i][j] = g[i - 1][j] + g[i][j - 1]

print g[n - 1][n - 1]
```

## B. Painting Pebbles

The key point of this problem is `abs(b(i, c) - b(j, c)) <= 1`.

First of all, it's safe to paint k pebbles of every pile with the same color, when `k = min(piles)`. At this moment, every `b(i, c) - b(j, c) == 0`.

And then, we paint 1 pebbles of every pile with color `C[i]` at a time (if possible). That is, for every pile, the number of pebbles with color `C[i]` is zero or one.

If you can't paint all the pebbles with proper color, just print a "NO" here.

```(n, k) = map(int, raw_input().split())
ps = map(int, raw_input().split())

(mini, maxi) = min(ps), max(ps)

if maxi - mini > k:
print 'NO'
exit(0)

print 'YES'
for p in ps:
r = [1 for i in xrange(mini)] + [i + 1 for i in xrange(p - mini)]
print ' '.join(map(str, r))
```

## C. Sums of Digits

Brute force & Constructive

After reading this problem, there is one thing that we could NEVER miss is the scope of number n: `1 <= n <= 300`, which means that the max number here is no more than 40 digits and we can solve the problem with brute force.

As we know, the number in the array must be incremental, and every number should be the minimum.

Assuming we have got an array which is incremental, the last number is K. Such as:

```K = d3 ++ d2 ++ d1 ++ d0
```

Our mission is to find a way to generate the smallest number which follow the rules:

1. the number here is greater than the previous one
2. the digit sum

Rule No.1 is not hard as it seems, if we increase any digit of the number K, the new number is of course greater. But how to satisfy the digit sum?

For example, we got a new number `K1`:

```K1 = d3 ++ (d2 + 1) ++ d1 ++ d0
```

Here, of course, `K1 > K`. But the number `K2`:

```K2= d3 ++ (d2 + 1) ++ 0 ++ 0
```

is smaller then `K1`, and also greater than the number `K`.

And then, we fill the lower digits with number to make the sum of the digits equal to the given one. If failed, keep on trying, such as:

```K3 = d3 ++ (d2 + 2) ++ 0 ++ 0
```

or

```K4 = (d3 + 1) ++ 0 ++ 0 ++ 0
```

or even

```K5 = 1 ++ 0 ++ 0 ++ 0 ++ 0
```
```import sys

def do_fill(num, ptr, delta):
for i in xrange(ptr):
num[i] = min(9, delta)
delta -= num[i]
return delta == 0

def solve(num, pre):
l = len(pre)
i = 0

while True:
t = pre + [0 for j in xrange(i - l + 1)]
while t[i] + 1 < 10:
t[i] += 1
for j in xrange(i):
t[j] = 0
delta = num - sum(t)
if delta < 0:
break
if do_fill(t, i, delta):
return t
i += 1

if __name__ == '__main__':
ns = map(int, sys.stdin)[1:]
ans = [[0]]

for num in ns:
ans.append(solve(num, ans[-1]))

for item in ans[1:]:
print ''.join(map(str, item[::-1]))
```

## D. Restoring Numbers

Math

Each number of the input matrix is `(A[i] + B[i]) % MOD`. And we can get `(A[i] - A[j]) % MOD` by subtract the number on the same line.

Sometimes, the `(A[i] - A[j]) % MOD` can be both positive and negetive. And we can get the value of `MOD` here.

As a result, we can get the value of every `A[i] - A[0]`. We set A[0] to the number '0', and get the values of array A.

```(n, m) = map(int, raw_input().split())

mat = [map(int, raw_input().split()) for i in xrange(n)]

mod = -1
diffs = [0 for i in xrange(m)]

for i in xrange(1, m):
diff = set([
mat[j][i] - mat[j][0] for j in xrange(n)
])

if len(diff) == 1:
diffs[i] = list(diff)[0]
continue

if len(diff) != 2:
print 'NO'
exit(0)

a, b = diff

if mod == -1:
mod = abs(a - b)
elif mod != abs(a -b):
print 'NO'
exit(0)

diffs[i] = max(a, b)

As = [0 for i in xrange(n)]
Bs = [0] + diffs[1:]

Bs = map(lambda x: x - min(Bs), Bs)

for i in xrange(n):
As[i] = mat[i][0] - Bs[0]

if mod == -1:
mod = (10 ** 18) - 1

for i in xrange(n):
for j in xrange(m):
if mat[i][j] != (As[i] + Bs[j]) % mod:
print 'NO'
exit(0)

print 'YES'
print mod
print ' '.join(map(str, As))
print ' '.join(map(str, Bs))
```

## E. Pretty Song

Math & Thinkin' in reverse

It's hard to get the answer by brute force because the scope of this problem is too large.

Try to think in reverse. It's hard to calculate all the value of the substrings, but why don't we find a way to get the value that every vowel contributes to the final result?

For example, string "AAA". The first "A" will add `1 + 1/2 + 1/3` to the final result. And the second "A", `1 + 1/2 + 1/2 + 1/3`. And the last "A", `1 + 1/2 + 1/3`.

We can make a table here for a 4-length string.

We can easily find the pattern here. (Of course we can prove it.) And the code is right here.

(But you can always find a harder way to sovle it. LOL. But I have to say that pypy is awesome!)

```# pypy: 171ms
# python2: 467ms
VOWELS = list('AEIOUY')
N = 500010

ds = [0 for i in xrange(N)]

for i in xrange(1, N):
ds[i] = ds[i - 1] + 1.0 / i

S = raw_input()
n = len(S)
d = 0
ans = 0

for i, c in enumerate(S):
d += ds[n - i] - ds[i]
if c in VOWELS:
ans += d

print ans
```

pypy is about 3~5 times faster than the original python interpreter, and this is the very useful tool to help us with the algorithm problems.

## F. Progress Monitoring

DP

This problem is about the pre-order traversal with a tree. There are multiple situations of the output string given in the problem.

```  a    | b c d |         | e f g h i j |
^        ^                    ^
father  children   siblings & siblings children
```

or

```  a    | b c d e f |         | g h i j |
^          ^                    ^
father   children    siblings & siblings children
```

But be aware, if `x < a`, `a` and `x` can't be siblings.

`dp[i][j]` stands for the number of permutations of the subtree. whose pre-order traversal is right match the `s[i...j]`, the substring of the given traversal path.

```#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define print(x) cout << x << endl
#define input(x) cin >> x

typedef long long llint;

const llint MOD = 1000000000 + 7;
const int SIZE = 555;

llint dp[SIZE][SIZE];
int n;
vector<int> outvec;

void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j + i < n; j++) {
int l = j, r = j + i;
if (l == r) {
dp[l][r] = 1;
continue;
}
if (outvec[l + 1] > outvec[l]) {
dp[l][r] += dp[l + 1][r]; // <l + 1 ... r> are siblings
dp[l][r] %= MOD;
}
dp[l][r] += dp[l + 1][r]; // <l + 1 .. r> are child nodes
dp[l][r] %= MOD;

for (int k = l + 2; k <= r; k++) {
if (outvec[k] > outvec[l]) {
llint child   = dp[l + 1][k - 1];
llint sibling = dp[k][r];
dp[l][r] = (dp[l][r] + child * sibling) % MOD;
}
}
}
}
}

int main() {
int x;
input(n);
if (n == 1) {
print(1);
exit(0);
}
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) {
input(x);
outvec.push_back(x);
}
solve();
print(dp[1][n - 1] % MOD);
return 0;
}
```