Codeforces Global Round 24


A. Doremy's Paint
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7
5
1 3 2 2 4
5
1 2 3 4 5
4
2 1 2 1
3
2 3 3
2
2 2
1
1
9
9 8 5 2 1 1 2 3 3
Output
2 4
1 5
1 4
2 3
1 2
1 1
3 9
----------------------------------------------------------------------------------------------------
B. Doremy's Perfect Math Class
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2
2
1 2
3
5 10 25
Output
2
5
----------------------------------------------------------------------------------------------------
C. Doremy's City Construction
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4
4
2 2 3 1
6
5 2 3 1 5 2
12
7 2 4 9 1 4 6 3 7 4 2 3
4
1000000 1000000 1000000 1000000
Output
3
9
35
2
----------------------------------------------------------------------------------------------------
D. Doremy's Pegging Game
time limit per test: 1.5 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
4 100000007
Output
16
Input
1145 141919831
Output
105242108
----------------------------------------------------------------------------------------------------
E. Doremy's Number Line
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
4 16
5 3
8 12
10 7
15 1
4 16
8 12
10 7
15 1
5 3
4 16
10 7
15 1
5 3
8 12
4 16
15 1
5 3
8 12
10 7
1 1000000000
500000000 500000000
2 1000000000
1 999999999
1 1
Output
NO
YES
YES
YES
NO
YES
----------------------------------------------------------------------------------------------------
F. Doremy's Experimental Tree
time limit per test: 2.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
7
3 5
0 2 8
Output
2 3 3
1 2 2
Input
9
8081910646
8081902766 8081903751
8081902555 8081903540 8081905228
3090681001 3090681986 3090681775 7083659398
7083657913 7083658898 7083658687 2092437133 15069617722
1748216295 1748217280 1748217069 5741194692 749972427 10439821163
2377558289 2377559274 2377559063 6370536686 1379314421 5028071980 8866466178
1746983932 1746984917 1746984706 5739962329 748740064 10438588800 5026839617 10448447704
2341942133 2341943118 2341942907 6334920530 1343698265 4992455824 8830850022 4991223461 9115779270
Output
1 2 985
2 3 211
2 4 998244353
2 5 998244853
4 6 671232353
6 8 1232363
4 7 356561356
7 9 35616156
----------------------------------------------------------------------------------------------------
G1. Doremy's Perfect DS Class (Easy Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
2
1
3
Output
? 1 3 4
? 3 5 3
? 3 4 5
? 3 5 2
! 4
----------------------------------------------------------------------------------------------------
G2. Doremy's Perfect DS Class (Medium Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
2
1
3
Output
? 1 3 4
? 3 5 3
? 3 4 5
? 3 5 2
! 4
----------------------------------------------------------------------------------------------------
G3. Doremy's Perfect DS Class (Hard Version)
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
2
2
1
3
Output
? 1 3 4
? 3 5 3
? 3 4 5
? 3 5 2
! 4
----------------------------------------------------------------------------------------------------
H. Doremy's Paint 2
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

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