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


A. Indirect Sort
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
3
1 2 3
3
1 3 2
7
5 3 4 7 6 2 1
7
7 6 5 4 3 2 1
5
2 1 4 5 3
5
2 1 3 4 5
7
1 2 6 7 4 3 5
Output
Yes
Yes
No
No
No
No
Yes
----------------------------------------------------------------------------------------------------
B. Maximum Substring
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
5
11100
7
1100110
6
011110
7
1001010
4
1000
1
0
Output
9
12
16
12
9
1
----------------------------------------------------------------------------------------------------
C. Complementary XOR
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
3
010
101
2
11
10
4
1000
0011
2
10
10
3
111
111
Output
YES
1
2 2
NO
NO
YES
2
1 2
2 2
YES
2
1 1
2 3
----------------------------------------------------------------------------------------------------
D. Count GCD
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
3 5
4 2 1
2 1
1 1
5 50
2 3 5 2 3
4 1000000000
60 30 1 1
2 1000000000
1000000000 2
Output
3
1
0
595458194
200000000
----------------------------------------------------------------------------------------------------
E. Bracket Cost
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
1
)
4
)()(
3
())
5
(((((
10
)(())))())
Output
1
9
6
35
112
----------------------------------------------------------------------------------------------------
F. Majority
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
2 100
Output
1
Input
3 10
Output
2
Input
4 3271890
Output
4
Input
17 123456
Output
32347
----------------------------------------------------------------------------------------------------
G. Doping
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4 666012
1 3 4 2
Output
1 0 1 1 
Input
3 10
3 2 1
Output
1 2 2 
Input
7 1000000000
7 2 1 3 5 4 6
Output
1 6 40 201 705 1635 1854 
Input
10 11
10 9 8 7 6 5 4 3 2 1
Output
1 9 9 0 1 5 5 0 1 0 
----------------------------------------------------------------------------------------------------
H. BinaryStringForces
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
6
100011
3
101
5
11111
6
010101
Output
8
5
15
18
----------------------------------------------------------------------------------------------------
