2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules)


A. LaIS
time limit per test: 3 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
8
1 2 7 3 2 1 2 3
2
2 1
7
4 1 5 2 6 3 7
Output
6
2
7
----------------------------------------------------------------------------------------------------
B. Bakery
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 4
5 2 1 3 7
1 3 4 10
Output
4 2 1 0 
Input
8 9
3 1 4 1 5 9 2 6
1 2 3 4 5 6 7 8 9
Output
7 5 3 3 2 1 1 1 0 
----------------------------------------------------------------------------------------------------
C. Berpizza
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
8
1 8
1 10
1 6
3
2
1 9
2
3
Output
2 1 3 4 
Input
6
1 8
1 10
1 8
3
3
3
Output
2 1 3 
Input
8
1 103913
3
1 103913
1 103913
3
1 103913
1 103913
2
Output
1 2 3 
----------------------------------------------------------------------------------------------------
D. Firecrackers
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
7 2 3 6
1 4
7 2 3 6
5 1
7 2 3 6
4 4
Output
2
1
1
----------------------------------------------------------------------------------------------------
E. Four Segments
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
1 2 3 4
5 5 5 5
3 1 4 1
100 20 20 100
Output
3
25
3
2000
----------------------------------------------------------------------------------------------------
F. Full Turn
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
2
0 0 0 1
1 0 2 0
3
0 0 1 1
1 1 0 0
1 0 2 0
6
0 0 0 1
1 0 1 2
2 0 2 3
3 0 3 -5
4 0 4 -5
5 0 5 -5
Output
0
1
9
----------------------------------------------------------------------------------------------------
G. Hobbits
time limit per test: 1 second
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
6 10
10 40
20 10
25 30
30 15
50 15
65 30
Output
70.4034587602
Input
9 5
0 0
5 10
15 10
20 0
25 11
30 0
35 10
50 10
60 5
Output
27.2787986124
Input
2 10000
0 10000
400000 0
Output
400124.9804748512
----------------------------------------------------------------------------------------------------
H. K and Medians
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
3 3 1
1
7 3 3
1 5 7
10 5 3
4 5 6
13 7 7
1 3 5 7 9 11 12
Output
NO
YES
NO
YES
----------------------------------------------------------------------------------------------------
I. Plane Tiling
time limit per test: 1 second
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
2 0
0 2
Output
YES
0 0
0 1
1 0
1 1
Input
5
2 6
1 5
Output
NO
Input
2
3 4
1 2
Output
YES
0 0
0 1
----------------------------------------------------------------------------------------------------
J. Road Reform
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
4 5 7
4 1 3
1 2 5
2 3 8
2 4 1
3 4 4
4 6 5
1 2 1
1 3 1
1 4 2
2 4 1
4 3 1
3 2 1
3 2 10
1 2 8
1 3 10
5 5 15
1 2 17
3 1 15
2 3 10
1 4 14
2 5 8
Output
1
3
0
0
----------------------------------------------------------------------------------------------------
K. The Robot
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4
L
RUUDL
LLUU
DDDUUUUU
Output
-1 0
1 2
0 0
0 1
----------------------------------------------------------------------------------------------------
L. Prime Divisors Selection
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 3
2 4 6
Output
0
Input
3 3
2 4 16
Output
2 4 16 
Input
4 3
2 4 6 16
Output
2 4 16 
----------------------------------------------------------------------------------------------------
M. Similar Sets
time limit per test: 1 second
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
4
2 1 10
3 1 3 5
5 5 4 3 2 1
3 10 20 30
3
4 1 2 3 4
4 2 3 4 5
4 3 4 5 6
2
3 1 3 5
3 4 3 2
Output
2 3 
1 2 
-1
----------------------------------------------------------------------------------------------------
N. Waste Sorting
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
7
1 2 3
1 2 3 0 0
2 2 3
1 2 3 1 0
2 2 3
1 2 3 0 1
1 2 5
1 2 3 1 1
0 0 0
0 0 0 0 0
0 0 4
1 0 0 0 0
13 37 42
0 0 0 40 47
Output
YES
YES
NO
YES
YES
NO
YES
----------------------------------------------------------------------------------------------------
