Codeforces Round 496 (Div. 3)


A. Tanya and Stairways
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
1 2 3 1 2 3 4
Output
2
3 4 
Input
4
1 1 1 1
Output
4
1 1 1 1 
Input
5
1 2 3 4 5
Output
1
5 
Input
5
1 2 1 2 1
Output
3
2 2 1 
----------------------------------------------------------------------------------------------------
B. Delete from the Left
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
test
west
Output
2
Input
codeforces
yes
Output
9
Input
test
yes
Output
7
Input
b
ab
Output
1
----------------------------------------------------------------------------------------------------
C. Summarize to the Power of Two
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
4 7 1 5 4 9
Output
1
Input
5
1 2 3 4 5
Output
2
Input
1
16
Output
1
Input
4
1 1 1 1023
Output
0
----------------------------------------------------------------------------------------------------
D. Polycarp and Div 3
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3121
Output
2
Input
6
Output
1
Input
1000000000000000000000000000000000
Output
33
Input
201920181
Output
4
----------------------------------------------------------------------------------------------------
E1. Median on Segments (Permutations Edition)
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 4
2 4 5 3 1
Output
4
Input
5 5
1 2 3 4 5
Output
1
Input
15 8
1 15 2 14 3 13 4 8 12 5 11 6 10 7 9
Output
48
----------------------------------------------------------------------------------------------------
E2. Median on Segments (General Case Edition)
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 4
1 4 5 60 4
Output
8
Input
3 1
1 1 1
Output
6
Input
15 2
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
Output
97
----------------------------------------------------------------------------------------------------
F. Berland and the Shortest Paths
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 4 3
1 2
2 3
1 4
4 3
Output
2
1110
1011
Input
4 6 3
1 2
2 3
1 4
4 3
2 4
1 3
Output
1
101001
Input
5 6 2
1 2
1 3
2 4
2 5
3 4
3 5
Output
2
111100
110110
----------------------------------------------------------------------------------------------------
