Educational Codeforces Round 45 (Rated for Div. 2)


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

Examples
Input
9 7 3 8
Output
15
Input
2 7 3 7
Output
14
Input
30 6 17 19
Output
0
----------------------------------------------------------------------------------------------------
B. Micro-World
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7 1
101 53 42 102 101 55 54
Output
3
Input
6 5
20 15 10 15 20 25
Output
1
Input
7 1000000
1 1 1 1 1 1 1
Output
7
----------------------------------------------------------------------------------------------------
C. Bracket Sequences Concatenation Problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
)
()
(
Output
2
Input
2
()
()
Output
4
----------------------------------------------------------------------------------------------------
D. Graph And Its Complement
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 1 2
Output
YES
001
001
110
Input
3 3 3
Output
NO
----------------------------------------------------------------------------------------------------
E. Post Lamps
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6 2 3
1 3
1 2 3
Output
6
Input
4 3 4
1 2 3
1 10 100 1000
Output
1000
Input
5 1 5
0
3 3 3 3 3
Output
-1
Input
7 4 3
2 4 5 6
3 14 15
Output
-1
----------------------------------------------------------------------------------------------------
F. Flow Control
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
3 -10 6 1
5
1 2
3 2
2 4
3 4
3 1
Output
Possible
4
-6
8
-7
7
Input
4
3 -10 6 4
5
1 2
3 2
2 4
3 4
3 1
Output
Impossible
----------------------------------------------------------------------------------------------------
G. GCD Counting
time limit per test: 4.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
1 2 3
1 2
2 3
Output
1 4
2 1
3 1
Input
6
1 2 4 8 16 32
1 6
6 3
3 4
4 2
6 5
Output
1 6
2 5
4 6
8 1
16 2
32 1
Input
4
9 16 144 6
1 3
2 3
4 3
Output
1 1
2 1
3 1
6 2
9 2
16 2
144 1
----------------------------------------------------------------------------------------------------
