Codeforces Round 351 (VK Cup 2016 Round 3, Div. 1 Edition)


A. Bear and Colors
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 2 1 2
Output
7 3 0 0 
Input
3
1 1 1
Output
6 0 0 
----------------------------------------------------------------------------------------------------
B. Bear and Two Paths
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7 11
2 4 7 3
Output
2 7 1 3 6 5 4
7 1 5 4 6 2 3
Input
1000 999
10 20 30 40
Output
-1
----------------------------------------------------------------------------------------------------
C. Levels and Regions
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 2
100 3 5 7
Output
5.7428571429
Input
6 2
1 2 4 8 16 32
Output
8.5000000000
----------------------------------------------------------------------------------------------------
D. Bearish Fanpages
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 12
10 20 30 40 50
2 3 4 5 2
2 1
2 2
2 3
2 4
2 5
1 4 2
2 1
2 2
2 3
2 4
2 5
3
Output
10
36
28
40
36
9
57
27
28
29
9 57
----------------------------------------------------------------------------------------------------
E. Bear and Destroying Subtrees
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
7
1 1
1 1
2 1
1 2
1 3
2 2
2 1
Output
0.7500000000
0.5000000000
1.1875000000
Input
8
2 1
1 1
1 2
1 3
1 4
2 1
1 4
2 1
Output
0.0000000000
0.9375000000
0.9687500000
----------------------------------------------------------------------------------------------------
F. Bears and Juice
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 1 3
Output
32
Input
1 100 4
Output
4
Input
3 2 1
Output
7
Input
100 100 100
Output
381863924
----------------------------------------------------------------------------------------------------
G. Choosing Ads
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 9 33
1 2 1 3 3
2 1 5
2 1 5
2 1 3
2 3 3
1 2 4 5
2 1 5
2 3 5
1 4 5 1
2 1 5
Output
3 1 2 3
2 1 3
2 2 1
3 1 1000 1000
1 5
2 5 3
2 1 5
----------------------------------------------------------------------------------------------------
