Codeforces Round 869 (Div. 1)


A. Almost Increasing Subsequence
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
9 8
1 2 4 3 3 5 6 2 1
1 3
1 4
2 5
6 6
3 7
7 8
1 8
8 8
Output
3
4
3
1
4
2
7
1
----------------------------------------------------------------------------------------------------
B. Fish Graph
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
7 8
1 2
2 3
3 4
4 1
4 5
4 6
4 2
6 7
7 7
6 7
1 2
2 3
3 4
4 1
1 3
3 5
4 4
1 3
3 4
4 1
1 2
Output
YES
6
5 4
6 4
4 3
1 4
2 1
3 2
YES
5
5 3
2 3
3 1
4 3
1 4
NO
----------------------------------------------------------------------------------------------------
C. Similar Polynomials
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
1
1000000006 0
2 3
Output
3
Input
2
1 4 9
100 121 144
Output
9
----------------------------------------------------------------------------------------------------
D. Toy Machine
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 1
Output
RDL
Input
7 2
Output
RDL
----------------------------------------------------------------------------------------------------
E. Half-sum
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
7 3
4
1 2 10 11
3
1 2 3
6
64 32 64 16 64 0
4
1 1 1 1
Output
4
9
500000005
59
0
----------------------------------------------------------------------------------------------------
F. Entangled Substrings
time limit per test: 2 seconds
memory limit per test: 256 mebibytes
input: standard input
output: standard output

Examples
Input
abba
Output
1
Input
abacaba
Output
0
Input
abcabcabcabc
Output
5
Input
adamant
Output
82
----------------------------------------------------------------------------------------------------
