VK Cup 2012 Finals


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

Examples
Input
3 5 8 2
1 4
1 3
3 3
1 2
1 1
2 1
1 5
2 2
Output
4
2 1 2 1 2 1 2 2 
----------------------------------------------------------------------------------------------------
B. Polycarpus is Looking for Good Substrings
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
aaaaa
2
a
a
Output
1
1
Input
abacaba
3
ac
ba
a
Output
1
2
4
----------------------------------------------------------------------------------------------------
C. Cowboys
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
BABBBABBA
Output
2
Input
ABABB
Output
2
Input
ABABAB
Output
4
----------------------------------------------------------------------------------------------------
D. Cutting a Fence
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
3 2 1
3
1 2 3
Output
2.000000000000000
1.500000000000000
1.000000000000000
Input
2
1 1
3
1 2 1
Output
1.000000000000000
1.000000000000000
1.000000000000000
----------------------------------------------------------------------------------------------------
E. IT Restaurants
time limit per test: 1.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
1 2
2 3
3 4
4 5
Output
3
1 3
2 2
3 1
Input
10
1 2
2 3
3 4
5 6
6 7
7 4
8 9
9 10
10 4
Output
6
1 8
2 7
3 6
6 3
7 2
8 1
----------------------------------------------------------------------------------------------------
