Codeforces Global Round 16


A. Median Maximization
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
1 5
2 5
3 5
2 1
7 17
4 14
1 1000000000
1000000000 1
Output
5
2
2
0
4
4
1000000000
0
----------------------------------------------------------------------------------------------------
B. MIN-MEX Cut
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
01
1111
01100
101
0000
01010
Output
1
0
2
1
1
2
----------------------------------------------------------------------------------------------------
C. MAX-MEX Cut
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
7
0101000
1101100
5
01100
10101
2
01
01
6
000000
111111
Output
8
8
2
12
----------------------------------------------------------------------------------------------------
D1. Seating Arrangements (easy version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 3
1 2 3
1 5
2 1 5 3 3
1 2
2 1
1 6
2 3 2 1 1 1
Output
3
6
0
1
----------------------------------------------------------------------------------------------------
D2. Seating Arrangements (hard version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
1 2
1 2
3 2
1 1 2 2 3 3
3 3
3 4 4 1 1 1 1 1 2
2 2
1 1 2 1
4 2
50 50 50 50 3 50 50 50
4 2
6 6 6 6 2 2 9 6
2 9
1 3 3 3 3 3 1 1 3 1 3 1 1 3 3 1 1 3
Output
1
0
4
0
0
0
1
----------------------------------------------------------------------------------------------------
E. Buds Re-hanging
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
7
1 2
1 3
1 4
2 5
2 6
4 7
6
1 2
1 3
2 4
2 5
3 6
2
1 2
7
7 3
1 5
1 3
4 6
4 7
2 1
6
2 1
2 3
4 5
3 4
3 6
Output
2
2
1
2
1
----------------------------------------------------------------------------------------------------
F. Points Movement
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
4 11
2 6 14 18
0 3
4 5
11 15
3 5
10 13
16 16
1 4
8 12
17 19
7 13
14 19
4 12
-9 -16 12 3
-20 -18
-14 -13
-10 -7
-3 -1
0 4
6 11
7 9
8 10
13 15
14 18
16 17
18 19
Output
5
22
----------------------------------------------------------------------------------------------------
G. Four Vertices
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 6
1 3 6
4 3 1
1 4 1
2 6 4
2 4 2
5 4 3
4
1 2 5 2
0 1 4
0 3 4
1 6 1 3
Output
4
3
3
7
5
----------------------------------------------------------------------------------------------------
H. Xor-quiz
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

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