Codeforces Round 576 (Div. 2)


A. City Day
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10 2 2
10 9 6 7 8 3 2 1 4 5
Output
3
Input
10 2 3
10 9 6 7 8 3 2 1 4 5
Output
8
Input
5 5 5
100000 10000 1000 100 10
Output
5
----------------------------------------------------------------------------------------------------
B. Water Lily
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1 2
Output
1.5000000000000
Input
3 5
Output
2.6666666666667
----------------------------------------------------------------------------------------------------
C. MP3
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 1
2 1 2 3 4 3
Output
2
Input
6 2
2 1 2 3 4 3
Output
0
Input
6 1
1 1 2 2 3 3
Output
2
----------------------------------------------------------------------------------------------------
D. Welfare State
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 2 3 4
3
2 3
1 2 2
2 1
Output
3 2 3 4 
Input
5
3 50 2 1 10
3
1 2 0
2 8
1 3 20
Output
8 8 20 8 10 
----------------------------------------------------------------------------------------------------
E. Matching vs Independent Set
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 2
1 3
1 2
1 2
1 3
1 2
2 5
1 2
3 1
1 4
5 1
1 6
2 15
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
Output
Matching
2
IndSet
1
IndSet
2 4
Matching
1 15
----------------------------------------------------------------------------------------------------
F. Rectangle Painting 1
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
###
#.#
###
Output
3
Input
3
...
...
...
Output
0
Input
4
#...
....
....
#...
Output
2
Input
5
#...#
.#.#.
.....
.#...
#....
Output
5
----------------------------------------------------------------------------------------------------
