Avito Code Challenge 2018


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

Examples
Input
mew
Output
3
Input
wuffuw
Output
5
Input
qqqqqqqq
Output
0
----------------------------------------------------------------------------------------------------
B. Businessmen Problems
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
1 2
7 2
3 10
4
1 4
2 4
3 4
4 4
Output
24
Input
1
1000000000 239
3
14 15
92 65
35 89
Output
408
----------------------------------------------------------------------------------------------------
C. Useful Decomposition
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

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

Examples
Input
10 4
9 14 28 1 7 13 15 29 2 31
Output
24
Input
7 3
3 14 15 92 65 35 89
Output
64
----------------------------------------------------------------------------------------------------
E. Addition on Segments
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 3
1 3 1
2 4 2
3 4 4
Output
4
1 2 3 4 
Input
7 2
1 5 1
3 7 2
Output
3
1 2 3 
Input
10 3
1 1 2
1 1 3
1 1 6
Output
6
2 3 5 6 8 9 
----------------------------------------------------------------------------------------------------
F. Round Marriage
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 4
0 1
2 3
Output
1
Input
10 100
3 14 15 92 65 35 89 79 32 38
2 71 82 81 82 84 5 90 45 23
Output
27
----------------------------------------------------------------------------------------------------
G. Magic multisets
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 4
1 1 2 1
1 1 2 2
1 1 4 1
2 1 4
Output
10
Input
3 7
1 1 1 3
1 1 1 3
1 1 1 2
1 1 1 1
2 1 1
1 1 1 2
2 1 1
Output
4
8
----------------------------------------------------------------------------------------------------
H. K Paths
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 2
1 2
2 3
Output
7
Input
5 1
4 1
2 3
4 5
2 1
Output
10
Input
29 29
1 2
1 3
1 4
1 5
5 6
5 7
5 8
8 9
8 10
8 11
11 12
11 13
11 14
14 15
14 16
14 17
17 18
17 19
17 20
20 21
20 22
20 23
23 24
23 25
23 26
26 27
26 28
26 29
Output
125580756
----------------------------------------------------------------------------------------------------
