VK Cup 2016 - Finals


A. LRU
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 1
0.3 0.2 0.5
Output
0.3 0.2 0.5 
Input
2 1
0.0 1.0
Output
0.0 1.0 
Input
3 2
0.3 0.2 0.5
Output
0.675 0.4857142857142857 0.8392857142857143 
Input
3 3
0.2 0.3 0.5
Output
1.0 1.0 1.0 
----------------------------------------------------------------------------------------------------
B. Break Up
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 7
1 6
2 1 6
2 3 5
3 4 9
4 6 4
4 6 5
4 5 1
3 1 3
Output
8
2
2 7
Input
6 7
1 6
2 3 1
1 2 2
1 3 3
4 5 4
3 6 5
4 6 6
1 5 7
Output
9
2
4 5
Input
5 4
1 5
2 1 3
3 2 1
3 4 4
4 5 2
Output
1
1
2
Input
2 3
1 2
1 2 734458840
1 2 817380027
1 2 304764803
Output
-1
----------------------------------------------------------------------------------------------------
C. Limak and Shooting Points
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 4
-2 -1
4 5
4 2
2 1
4 -1
1 -1
Output
3
Input
3 8
10 20
0 0
20 40
300 600
30 60
170 340
50 100
28 56
90 180
-4 -8
-1 -2
Output
5
----------------------------------------------------------------------------------------------------
D. Cron
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
-1 59 23 -1 -1 -1
6
1467372658
1467417540
1467417541
1467417598
1467417599
1467417600
Output
1467417540
1467417541
1467417542
1467417599
1467503940
1467503940
Input
0 0 12 6 3 7
3
1467372658
1467460810
1467547200
Output
1467460800
1467547200
1468065600
----------------------------------------------------------------------------------------------------
E. Huffman Coding on Segment
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
1 2 1 3 1 2 1
5
1 7
1 3
3 5
2 4
4 4
Output
10
3
3
5
0
----------------------------------------------------------------------------------------------------
F. Coprime Permutation
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
0 0 0 0
Output
4
Input
5
0 0 1 2 0
Output
2
Input
6
0 0 1 2 0 0
Output
0
Input
5
5 3 4 2 1
Output
0
----------------------------------------------------------------------------------------------------
G. Cool Slogans
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
abc
Output
1
Input
5
ddddd
Output
5
Input
11
abracadabra
Output
3
----------------------------------------------------------------------------------------------------
