Codeforces Round 844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round)


A. Parallel Projection
time limit per test: 1 second
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5
55 20 29
23 10 18 3
20 10 5
1 5 2 5
15 15 4
7 13 10 10
2 1000 2
1 1 1 999
10 4 10
7 1 2 1
Output
47
8
14
1002
17
----------------------------------------------------------------------------------------------------
B. Going to the Cinema
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
2
1 1
7
0 1 2 3 4 5 6
8
6 0 3 3 6 7 2 7
5
3 0 0 3 3
Output
2
1
3
2
----------------------------------------------------------------------------------------------------
C. Equal Frequencies
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
5
hello
10
codeforces
5
eevee
6
appall
Output
1
helno
2
codefofced
1
eeeee
0
appall
----------------------------------------------------------------------------------------------------
D. Many Perfect Squares
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
5
1 2 3 4 5
5
1 6 13 22 97
1
100
5
2 5 10 17 26
Output
2
5
1
2
----------------------------------------------------------------------------------------------------
E. Rectangle Shrinking
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
8
5
1 2 2 4
2 4 2 8
1 4 2 7
1 2 1 2
1 9 1 10
2
1 1 1 10
1 5 1 15
2
1 1 1 10
1 1 1 10
5
1 3 1 7
1 3 1 8
1 1 1 4
1 2 1 7
1 10 1 11
2
1 1 2 10
1 5 1 8
2
1 5 2 10
1 2 1 7
2
1 5 2 10
2 2 2 15
5
2 6 2 7
1 4 2 5
1 5 1 9
1 7 2 10
1 2 1 6
Output
15
1 2 2 4
2 5 2 8
1 5 1 7
0 0 0 0
1 9 1 10
15
1 1 1 10
1 11 1 15
10
1 1 1 10
0 0 0 0
10
0 0 0 0
1 8 1 8
1 1 1 4
1 5 1 7
1 10 1 11
20
1 1 2 10
0 0 0 0
15
1 5 2 10
1 2 1 4
20
1 5 1 10
2 2 2 15
16
2 6 2 6
2 4 2 5
0 0 0 0
1 7 2 10
1 2 1 6
----------------------------------------------------------------------------------------------------
F. Bracket Insertion
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
1 7500
Output
249561089
Input
2 6000
Output
519087064
Input
5 4000
Output
119387743
----------------------------------------------------------------------------------------------------
G. Diverse Coloring
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
2
7
1 2 2 1 5 5
8
1 2 3 4 5 6 7
Output
0
1
2
1
0
1
wbwwwbb
0
1
0
1
0
1
0
wbwbwbwb
----------------------------------------------------------------------------------------------------
H1. Window Signals (easy version)
time limit per test: 7 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
10
1 3 0
2 2 0
3 2 0
4 5 0
12 7 0
1 1 1
1 1
1 3 1
1 2
3 4 1
3 4
2 3 2
1 1
2 1
4 5 2
2 3
4 2
Output
4
10
44
954368
34903934
0
2
1696
10
253144
----------------------------------------------------------------------------------------------------
H2. Window Signals (hard version)
time limit per test: 7 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
10
1 3 0
2 2 0
3 2 0
4 5 0
12 7 0
1 1 1
1 1
1 3 1
1 2
3 4 1
3 4
2 3 2
1 1
2 1
4 5 2
2 3
4 2
Output
4
10
44
954368
34903934
0
2
1696
10
253144
----------------------------------------------------------------------------------------------------
