Codeforces Round 919 (Div. 2)


A. Satisfying Constraints
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
4
1 3
2 10
3 1
3 5
2
1 5
2 4
10
3 6
3 7
1 2
1 7
3 100
3 44
2 100
2 98
1 3
3 99
6
1 5
2 10
1 9
2 2
3 2
3 9
5
1 1
2 2
3 1
3 2
3 3
6
1 10000
2 900000000
3 500000000
1 100000000
3 10000
3 900000001
Output
7
0
90
0
0
800000000
----------------------------------------------------------------------------------------------------
B. Summation Game
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
1 1 1
1
4 1 1
3 1 2 4
6 6 3
1 4 3 2 5 6
6 6 1
3 7 3 3 32 15
8 5 3
5 5 3 3 3 2 9 9
10 6 4
1 8 2 9 3 3 4 5 3 200
2 2 1
4 3
2 1 2
1 3
Output
0
2
0
3
-5
-9
0
-1
----------------------------------------------------------------------------------------------------
C. Partitioning the Array
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
4
1 2 1 4
3
1 2 3
5
1 1 1 1 1
6
1 3 1 1 3 1
6
6 2 6 2 2 2
6
2 6 3 6 6 6
10
1 7 5 1 4 3 1 3 1 4
1
1
Output
2
1
2
4
4
1
2
1
----------------------------------------------------------------------------------------------------
D. Array Repetition
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
5 10
1 1
1 2
2 1
1 3
2 3
1 2 3 4 5 6 14 15 16 20
10 10
1 3
1 8
2 15
1 6
1 9
1 1
2 6
1 1
2 12
2 10
32752 25178 3198 3199 2460 2461 31450 33260 9016 4996
12 5
1 6
1 11
2 392130334
1 4
2 744811750
1 10
1 5
2 209373780
2 178928984
1 3
2 658326464
2 1000000000
914576963034536490 640707385283752918 636773368365261971 584126563607944922 1000000000000000000
2 2
1 1
1 2
1 2
Output
1 2 1 2 3 1 2 3 1 3
9 8 1 3 1 3 6 3 8 8
11 11 11 10 11
1 2
----------------------------------------------------------------------------------------------------
E. Counting Binary Strings
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
6
1 1
3 2
4 2
5 4
6 2
2450 2391
Output
1
3
5
12
9
259280854
----------------------------------------------------------------------------------------------------
F1. Smooth Sailing (Easy Version)
time limit per test: 5 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7
Output
3
0
3
Input
3 3 5
..v
.#.
...
1 2
1 3
2 3
2 1
3 2
Output
0
0
0
0
0
Input
14 13 5
.............
.............
.............
...vvvvvvv...
...v.....v...
...v.###.v...
...v.#.#.v...
...v..v..v...
...v..v..v...
....v...v....
.....vvv.....
.............
.............
.............
1 1
7 7
5 6
4 10
13 6
Output
3
0
1
0
2
Input
10 11 4
...........
..#######..
..#..#..#..
..#.....#..
..#..v..#..
..#.###.#..
..#.#.#.#..
..#...#.#..
..#####.#..
...........
7 6
3 7
6 8
1 1
Output
1
2
3
4
----------------------------------------------------------------------------------------------------
F2. Smooth Sailing (Hard Version)
time limit per test: 5 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7
Output
3
0
3
Input
3 3 5
..v
.#.
...
1 2
1 3
2 3
2 1
3 2
Output
0
0
0
0
0
Input
14 13 5
.............
.............
.............
...vvvvvvv...
...v.....v...
...v.###.v...
...v.#.#.v...
...v..v..v...
...v..v..v...
....v...v....
.....vvv.....
.............
.............
.............
1 1
7 7
5 6
4 10
13 6
Output
3
0
1
0
2
Input
10 11 4
...........
..#######..
..#..#..#..
..#.....#..
..#..v..#..
..#.###.#..
..#.#.#.#..
..#...#.#..
..#####.#..
...........
7 6
3 7
6 8
1 1
Output
1
2
3
4
----------------------------------------------------------------------------------------------------
