Codeforces Round 731 (Div. 3)


A. Shortest Path with Obstacle
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
7
1 1
3 3
2 2
2 5
2 1
2 3
1000 42
1000 1
1000 1000
1 10
3 10
2 10
3 8
7 8
3 7
2 1
4 1
1 1
1 344
1 10
1 1
Output
4
6
41
4
4
2
334
----------------------------------------------------------------------------------------------------
B. Alphabetical Strings
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
11
a
ba
ab
bac
ihfcbadeg
z
aa
ca
acb
xyz
ddcba
Output
YES
YES
YES
YES
YES
NO
NO
NO
NO
NO
NO
----------------------------------------------------------------------------------------------------
C. Pair Programming
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5
3 2 2
2 0
0 5
4 3 2
2 0 5
0 6
0 2 2
1 0
2 3
5 4 4
6 0 8 0
0 7 0 9
5 4 1
8 7 8 0
0
Output
2 0 0 5 
0 2 0 6 5 
-1
0 6 0 7 0 8 0 9
-1
----------------------------------------------------------------------------------------------------
D. Co-growing Sequence
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5
4
1 3 7 15
4
1 2 4 8
5
1 2 3 4 5
4
11 13 15 1
1
0
Output
0 0 0 0 
0 1 3 7 
0 1 0 3 2 
0 2 0 14 
0 
----------------------------------------------------------------------------------------------------
E. Air Conditioners
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5
6 2
2 5
14 16
10 1
7
30
5 5
3 1 4 2 5
3 1 4 2 5
7 1
1
1000000000
6 3
6 1 3
5 5 5
Output
15 14 15 16 16 17 
36 35 34 33 32 31 30 31 32 33 
1 2 3 4 5 
1000000000 1000000001 1000000002 1000000003 1000000004 1000000005 1000000006 
5 6 5 6 6 5 
----------------------------------------------------------------------------------------------------
F. Array Stabilization (GCD version)
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5
4
16 24 10 5
4
42 42 42 42
3
4 6 4
5
1 2 3 4 5
6
9 9 27 9 9 63
Output
3
0
2
1
1
----------------------------------------------------------------------------------------------------
G. How Many Paths?
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5
6 7
1 4
1 3
3 4
4 5
2 1
5 5
5 6
1 0
3 3
1 2
2 3
3 1
5 0
4 4
1 2
2 3
1 4
4 3
Output
1 0 1 2 -1 -1 
1 
-1 -1 -1 
1 0 0 0 0 
1 1 2 1 
----------------------------------------------------------------------------------------------------
