Codeforces Round 505 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)


A. Doggo Recoloring
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
aabddc
Output
Yes
Input
3
abc
Output
No
Input
3
jjj
Output
Yes
----------------------------------------------------------------------------------------------------
B. Weakened Common Divisor
time limit per test: 1.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
17 18
15 24
12 15
Output
6
Input
2
10 16
7 17
Output
-1
Input
5
90 108
45 105
75 40
165 175
33 30
Output
5
----------------------------------------------------------------------------------------------------
C. Plasticine zebra
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
bwwwbwwbw
Output
5
Input
bwwbwwb
Output
3
----------------------------------------------------------------------------------------------------
D. Recovering BST
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
3 6 9 18 36 108
Output
Yes
Input
2
7 17
Output
No
Input
9
4 8 10 12 15 18 33 44 81
Output
Yes
----------------------------------------------------------------------------------------------------
E. Colored Cubes
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 1
1 1
2 2
Output
2
1 1 1 2
1 2 2 2
Input
2 2
1 1
2 2
1 2
2 1
Output
2
2 2 2 1
1 1 1 2
Input
2 2
2 1
2 2
2 2
2 1
Output
4
2 1 1 1
2 2 2 1
1 1 1 2
1 2 2 2
Input
4 3
2 2
2 3
3 3
3 2
2 2
2 3
Output
9
2 2 1 2
1 2 1 1
2 3 2 2
3 3 2 3
2 2 1 2
1 1 2 1
2 1 3 1
3 1 3 2
1 2 2 2
----------------------------------------------------------------------------------------------------
F. Disjoint Triangles
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
1 1
2 2
4 6
4 5
7 2
5 3
Output
6
Input
7
0 -1000000000
-5 -5
5 -5
-5 0
5 0
-2 2
2 2
Output
21
----------------------------------------------------------------------------------------------------
G. Company Acquisitions
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
-1 -1 -1
Output
3
Input
2
2 -1
Output
0
Input
40
3 3 -1 -1 4 4 -1 -1 -1 -1 -1 10 10 10 10 10 10 4 20 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 3 3 3 3 3 3 3 3
Output
755808950
----------------------------------------------------------------------------------------------------
