Codeforces Round 952 (Div. 4)


A. Creating Words
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
bit set
cat dog
hot dog
uwu owo
cat cat
zzz zzz
Output
sit bet
dat cog
dot hog
owu uwo
cat cat
zzz zzz
----------------------------------------------------------------------------------------------------
B. Maximum Multiple Sum
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
3
15
Output
3
2
----------------------------------------------------------------------------------------------------
C. Good Prefixes
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
1
0
1
1
4
1 1 2 0
5
0 1 2 1 4
7
1 1 0 3 5 2 12
7
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 294967296
10
0 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 589934592
Output
1
0
3
3
4
1
2
----------------------------------------------------------------------------------------------------
D. Manhattan Circle
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
5 5
.....
.....
..#..
.....
.....
5 5
..#..
.###.
#####
.###.
..#..
5 6
......
......
.#....
###...
.#....
1 1
#
5 6
...#..
..###.
.#####
..###.
...#..
2 10
..........
...#......
Output
3 3
3 3
4 2
1 1
3 4
2 4
----------------------------------------------------------------------------------------------------
E. Secret Box
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
3 3 3 8
3 3 3 18
5 1 1 1
2 2 2 7
3 4 2 12
4 3 1 6
1800 1800 1800 4913000000
Output
8
2
5
0
4
4
1030301
----------------------------------------------------------------------------------------------------
F. Final Boss
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
3 2
2 1
2 1
5 2
2 1
2 1
50 3
5 6 7
5 6 7
50 3
2 2 2
3 3 3
90000 2
200000 200000
1 1
100000 1
1
200000
6 7
3 2 3 2 3 1 2
6 5 9 5 10 7 7
21 6
1 1 1 1 1 1
5 5 8 10 7 6
Output
1
3
15
25
1
19999800001
1
21
----------------------------------------------------------------------------------------------------
G. D-Function
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
0 1 4
0 2 7
1 2 1
1 2 3
582 74663 3
0 3 1
Output
2
3
90
12
974995667
999
----------------------------------------------------------------------------------------------------
H1. Maximize the Largest Component (Easy Version)
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.
Output
1
6
9
11
15
30
----------------------------------------------------------------------------------------------------
H2. Maximize the Largest Component (Hard Version)
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.
Output
1
7
11
16
22
36
----------------------------------------------------------------------------------------------------
