Codeforces Round 873 (Div. 2)


A. Divisible Array
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
1
2
3
4
5
6
7
Output
1
2 4
1 2 3
2 8 6 4
3 4 9 4 5
1 10 18 8 5 36
3 6 21 24 10 6 14
----------------------------------------------------------------------------------------------------
B. Permutation Swap
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
3
3 1 2
4
3 4 1 2
7
4 2 6 7 5 3 1
9
1 6 7 4 9 2 3 8 5
6
1 5 3 4 2 6
10
3 10 5 2 9 6 7 8 1 4
11
1 11 6 4 8 3 7 5 9 10 2
Output
1
2
3
4
3
2
3
----------------------------------------------------------------------------------------------------
C. Counting Orders
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
6
9 6 8 4 5 2
4 1 5 6 3 1
3
4 3 2
3 4 9
1
2
1
3
2 3 4
1 3 3
12
2 3 7 10 23 28 29 50 69 135 420 1000
1 1 2 3 5 8 13 21 34 55 89 144
Output
32
0
1
0
13824
----------------------------------------------------------------------------------------------------
D1. Range Sorting (Easy Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
Output
1
2
8
16
232
----------------------------------------------------------------------------------------------------
D2. Range Sorting (Hard Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
6 4
3
3 10 6
4
4 8 7 2
5
9 8 2 4 6
12
2 6 13 3 15 5 10 8 16 9 11 18
Output
1
2
8
16
232
----------------------------------------------------------------------------------------------------
E. Palindrome Partition
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
6
abaaba
1
a
2
aa
6
abcdef
12
accabccbacca
6
abbaaa
Output
3
0
1
0
14
6
----------------------------------------------------------------------------------------------------
F. Two Centroids
time limit per test: 1.5 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
5
2
1
3
1 1
4
1 2 3
7
1 2 3 2 5 2
10
1 2 2 4 5 5 7 8 9
Output
0
0 1
0 1 0
0 1 0 1 2 3
0 1 2 1 0 1 0 1 2
----------------------------------------------------------------------------------------------------
