CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)


A. Two 0-1 Sequences
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10
6 2
001001
11
6 2
110111
01
6 2
000001
11
6 2
111111
01
8 5
10000101
11010
7 4
1010001
1001
8 6
01010010
010010
8 4
01010101
1001
8 4
10101010
0110
7 5
1011100
11100
Output
YES
YES
NO
NO
NO
YES
YES
NO
NO
YES
----------------------------------------------------------------------------------------------------
B. Luke is a Foodie
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
5 3
3 8 5 6 7
5 3
3 10 9 8 7
12 8
25 3 3 17 8 6 1 16 15 25 17 23
10 2
1 2 3 4 5 6 7 8 9 10
8 2
2 4 6 8 6 4 12 14
8 2
2 7 8 9 6 13 21 28
15 5
11 4 13 23 7 10 5 21 20 11 17 5 29 16 11
Output
0
1
2
1
2
4
6
----------------------------------------------------------------------------------------------------
C. Virus
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
10 3
3 6 8
6 2
2 5
20 3
3 7 12
41 5
1 11 21 31 41
10 5
2 4 6 8 10
5 5
3 2 5 4 1
1000000000 1
1
1000000000 4
1 1000000000 10 16
Output
7
5
11
28
9
5
2
15
----------------------------------------------------------------------------------------------------
D. Magical Array
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
3 9
0 1 2 0 0 2 1 1 0
0 1 1 1 2 0 0 2 0
0 1 2 0 0 1 2 1 0
3 7
25 15 20 15 25 20 20
26 14 20 14 26 20 20
25 15 20 15 20 20 25
3 9
25 15 20 15 25 20 20 20 20
26 14 20 14 26 20 20 20 20
25 15 20 15 25 15 20 20 25
3 11
25 15 20 15 25 20 20 20 20 20 20
26 14 20 14 26 20 20 20 20 20 20
25 15 20 15 25 20 15 20 20 20 25
3 13
25 15 20 15 25 20 20 20 20 20 20 20 20
26 14 20 14 26 20 20 20 20 20 20 20 20
25 15 20 15 25 20 20 15 20 20 20 20 25
3 15
25 15 20 15 25 20 20 20 20 20 20 20 20 20 20
26 14 20 14 26 20 20 20 20 20 20 20 20 20 20
25 15 20 15 25 20 20 20 15 20 20 20 20 20 25
3 9
909459 479492 676924 224197 162866 164495 193268 742456 728277
948845 455424 731850 327890 304150 237351 251763 225845 798316
975446 401170 792914 272263 300770 242037 236619 334316 725899
Output
3 1
3 10
3 15
3 20
3 25
3 30
1 1378716
----------------------------------------------------------------------------------------------------
E. Count Seconds
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
3 2
1 1 1
1 2
2 3
5 5
1 0 0 0 0
1 2
2 3
3 4
4 5
1 5
10 11
998244353 0 0 0 998244353 0 0 0 0 0
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 3
7 9
5 6
1293 1145 9961 9961 1919
1 2
2 3
3 4
5 4
1 4
2 4
6 9
10 10 10 10 10 10
1 2
1 3
2 3
4 3
6 3
3 5
6 5
6 1
6 2
Output
3
5
4
28010
110
----------------------------------------------------------------------------------------------------
F. Colouring Game
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8
3
BRB
5
RRBBB
6
RBRBRB
8
BBRRBRRB
6
BRRBRB
12
RBRBRBRBRRBB
12
RBRBRBRBBBRR
4
RBBR
Output
Bob
Bob
Alice
Alice
Alice
Alice
Bob
Bob
----------------------------------------------------------------------------------------------------
G. Mio and Lucky Array
time limit per test: 5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
5
1 2 3 4 5
5
2 0 6 0 10
5
1 2 3 4 5
3
3 5 3
8
-3 2 -3 -4 4 0 1 -2
4
10 -6 7 -7
5
1 2 3 4 5
4
1 10 1 1
5
0 0 0 0 0
2
10 12
Output
1
1 
1
4 
5
1 3 4 6 8 
-1
-1
----------------------------------------------------------------------------------------------------
H1. Game of AI (easy version)
time limit per test: 2.5 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
1 998244353
Output
0
Input
2 998244353
Output
2
Input
3 998244353
Output
24
Input
8 998244353
Output
123391016
----------------------------------------------------------------------------------------------------
H2. Game of AI (hard version)
time limit per test: 12 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
8 998244353
Output
0
2
24
360
6800
153150
4057452
123391016
----------------------------------------------------------------------------------------------------
