Technocup 2020 - Elimination Round 3


A. Math Problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
3
4 5
5 9
7 7
5
11 19
4 17
16 16
3 12
14 17
1
1 10
1
1 1
Output
2
4
0
0
----------------------------------------------------------------------------------------------------
B. Box
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
5
1 3 4 5 5
4
1 1 3 4
2
2 2
1
1
Output
1 3 4 5 2 
-1
2 1 
1 
----------------------------------------------------------------------------------------------------
C. Messy
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
8 2
()(())()
10 3
))()()()((
2 1
()
2 1
)(
Output
4
3 4
1 1
5 8
2 2
3
4 10
1 4
6 7
0
1
1 2
----------------------------------------------------------------------------------------------------
D1. Optimal Subsequences (Easy Version)
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3
Output
20
10
20
10
20
10
Input
7
1 2 1 3 1 2 1
9
2 1
2 2
3 1
3 2
3 3
1 1
7 1
7 7
7 4
Output
2
3
2
3
2
3
1
1
3
----------------------------------------------------------------------------------------------------
D2. Optimal Subsequences (Hard Version)
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
10 20 10
6
1 1
2 1
2 2
3 1
3 2
3 3
Output
20
10
20
10
20
10
Input
7
1 2 1 3 1 2 1
9
2 1
2 2
3 1
3 2
3 3
1 1
7 1
7 7
7 4
Output
2
3
2
3
2
3
1
1
3
----------------------------------------------------------------------------------------------------
E. Arson In Berland Forest
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 6
XXXXXX
XXXXXX
XXXXXX
Output
1
......
.X.XX.
......
Input
10 10
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXX...
.XXXXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
...XXXXXX.
..........
Output
2
..........
..........
...XX.....
..........
..........
..........
.....XX...
..........
..........
..........
Input
4 5
X....
..XXX
..XXX
..XXX
Output
0
X....
..XXX
..XXX
..XXX
----------------------------------------------------------------------------------------------------
F1. Wrong Answer on test 233 (Easy Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 3
1 3 1
Output
9
Input
5 5
1 1 4 2 2
Output
1000
----------------------------------------------------------------------------------------------------
F2. Wrong Answer on test 233 (Hard Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 3
1 3 1
Output
9
Input
5 5
1 1 4 2 2
Output
1000
Input
6 2
1 1 2 2 1 1
Output
16
----------------------------------------------------------------------------------------------------
G. Not Same
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
5 5 5 5 5
Output
6
11111
01111
10111
11011
11101
11110
Input
5
5 1 1 1 1
Output
5
11000
10000
10100
10010
10001
Input
5
4 1 5 3 4
Output
5
11111
10111
10101
00111
10100
----------------------------------------------------------------------------------------------------
