Codeforces Round 741 (Div. 2)


A. The Miracle and the Sleeper
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
1 1
999999999 1000000000
8 26
1 999999999
Output
0
1
12
499999999
----------------------------------------------------------------------------------------------------
B. Scenes From a Memory
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
3
237
5
44444
3
221
2
35
3
773
1
4
30
626221626221626221626221626221
Output
2
27
1
4
1
1
2
35
2
77
1
4
1
6
----------------------------------------------------------------------------------------------------
C. Rings
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
6
101111
9
111000111
8
10000000
5
11011
6
001111
3
101
30
100000000000000100000000000000
Output
3 6 1 3
1 9 4 9
5 8 1 4
1 5 3 5
1 6 2 4
1 2 2 3
1 15 16 30
----------------------------------------------------------------------------------------------------
D1. Two Hundred Twenty One (easy version)
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
14 1
+--++---++-++-
1 14
14 3
+--++---+++---
1 14
6 12
3 10
4 10
+-+-
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
Output
2
2
1
0
1
2
1
2
1
2
1
1
2
1
----------------------------------------------------------------------------------------------------
D2. Two Hundred Twenty One (hard version)
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
14 1
+--++---++-++-
1 14
14 3
+--++---+++---
1 14
6 12
3 10
4 10
+-+-
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4
Output
2
5 8
2
1 11
1
9
0
1
1
2
1 2
1
2
2
1 3
1
2
2
2 3
1
3
1
3
2
3 4
1
4
----------------------------------------------------------------------------------------------------
E. Rescue Niwen!
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
7
5
acbac
8
acabacba
12
aaaaaaaaaaaa
10
abacabadac
8
dcbaabcd
3
cba
6
sparky
Output
9
17
12
29
14
3
9
----------------------------------------------------------------------------------------------------
F. Tubular Bells
time limit per test: 5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
5
8 10 7 6 9
5
24 25 28 27 26
7
1 2 3 4 5 6 7
Output
? 1 2
40
? 2 5
90
? 3 1
56
? 4 5
18
! 8 10 7 6 9
? 1 5
312
? 2 4
675
! 24 25 28 27 26
? 1 4
4
? 2 5
10
? 3 7
21
? 6 2
6
? 2 5
10
? 1 2
2
? 1 2
2
? 1 2
2
? 1 2
2
? 1 2
2
! 1 2 3 4 5 6 7
----------------------------------------------------------------------------------------------------
