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
Reading comperhension & Constructive.
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:
- the number here is greater than the previous one
- 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;
}
Comments
comments powered by Disqus