Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round)


A. Monsters (easy version)
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
2
3
3 1 2
6
4 1 5 4 1 1
Output
0
4
----------------------------------------------------------------------------------------------------
B. Letter Exchange
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
2
nwi
inw
3
inn
nww
wii
4
win
www
iii
nnn
Output
0
2
2 w 3 i
3 w 1 n
3
2 w 3 i
2 w 4 n
3 i 4 n
----------------------------------------------------------------------------------------------------
C. Monsters (hard version)
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
2
3
3 1 2
6
4 1 5 4 1 1
Output
2 1 0
3 2 4 4 4 4
----------------------------------------------------------------------------------------------------
D. Wooden Spoon
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
1
Output
0
2
Input
2
Output
0
0
8
16
Input
3
Output
0
0
0
1536
4224
7680
11520
15360
----------------------------------------------------------------------------------------------------
E. Infinite Game
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
??
Output
1
2
1
Input
?aa?b
Output
1
3
0
Input
a???ba
Output
4
3
1
Input
????????
Output
121
14
121
Input
ba????a?a???abbb?
Output
216
57
239
Input
a????a??????b??abbababbbb?a?aaa????bb
Output
97833
28387
135924
Input
??????????????a????????????????b?????
Output
484121060
448940322
484613337
----------------------------------------------------------------------------------------------------
F. Minimums or Medians
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 1
Output
2
Input
3 2
Output
3
Input
3 3
Output
1
Input
7 4
Output
11
Input
23 8
Output
88
Input
100 77
Output
825430474
----------------------------------------------------------------------------------------------------
