Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)


A. Colour the Flag
time limit per test: 1.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
4 6
.R....
......
......
.W....
4 4
.R.W
....
....
....
5 1
R
W
R
W
R
Output
YES
WRWRWR
RWRWRW
WRWRWR
RWRWRW
NO
YES
R
W
R
W
R
----------------------------------------------------------------------------------------------------
B. Histogram Ugliness
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
4
4 8 9 6
6
2 1 7 4 0 0
Output
17
12
----------------------------------------------------------------------------------------------------
C. Little Alawn's Puzzle
time limit per test: 2.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

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

Examples
Input
4
0 1 2 2
1 0 1 1
Output
? 1
? 2
!
4 2
1 2
2 3
Input
5
2 2 1 1 0
Output
? 5
!
4 5
3 5
2 4
1 3
----------------------------------------------------------------------------------------------------
E. Lost Array
time limit per test: 1.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 3
4
0
1
Output
? 1 2 3
? 2 3 5
? 4 1 5
! 7
Input
3 2
Output
-1
----------------------------------------------------------------------------------------------------
F1. Falling Sand (Easy Version)
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 7
#....#.
.#.#...
#....#.
#....##
#.#....
4 1 1 1 0 3 1
Output
3
Input
3 3
#.#
#..
##.
3 1 1
Output
1
----------------------------------------------------------------------------------------------------
F2. Falling Sand (Hard Version)
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 7
#....#.
.#.#...
#....#.
#....##
#.#....
4 1 1 1 0 3 1
Output
3
Input
3 3
#.#
#..
##.
3 1 1
Output
1
Input
7 5
.#..#
#....
..##.
..##.
..###
..#..
#.##.
0 0 2 4 2
Output
1
----------------------------------------------------------------------------------------------------
G. A New Beginning
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
1 1
2 2
Output
0
Input
2
1 1
2 0
Output
1
Input
3
5 5
7 7
4 9
Output
2
Input
10
5 1
4 0
9 6
0 2
10 1
9 10
3 10
0 10
8 9
1 5
Output
19
Input
10
1 1
2 2
2 0
4 2
4 0
2 0
0 2
4 0
4 2
5 1
Output
6
----------------------------------------------------------------------------------------------------
H. Lost Nodes
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
3 2
2 1
2 4
1
1
2
2
Output
3
? 1
? 2
? 3
! 4 1
Input
5
3 1
1 4
4 5
4 2
1
4
1
4
Output
3
? 4
? 1
? 5
! 1 4
----------------------------------------------------------------------------------------------------
