ICPC WF Moscow Invitational Contest - Online Mirror (Unrated, ICPC Rules, Teams Preferred)


A. Anti-Tetris
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
3 2
aa
ab
aa
Output
2
2 DS
1 S
Input
5 6
....dd
.ccccd
.cbbdd
.aab.a
aabbaa
Output
5
2 DDDS
4 DDLS
6 DDDS
2 DS
5 S
Input
5 3
...
aab
abb
aab
.bb
Output
-1
----------------------------------------------------------------------------------------------------
B. Building Forest Trails
time limit per test: 3 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
6 9
1 1 3
1 4 6
2 3 4
1 2 4
2 1 2
2 1 3
2 1 4
2 6 1
2 5 3
Output
011110
Input
2 5
2 1 2
2 2 1
1 1 2
2 1 2
2 2 1
Output
0011
----------------------------------------------------------------------------------------------------
C. Cactus Lady and her Cing
time limit per test: 5 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
5
4 3
1 2
2 3
3 4
8 7
1 2
3 2
2 4
4 5
4 6
6 7
6 8
5 4
1 2
1 3
1 4
1 5
8 9
1 2
2 3
3 4
1 4
4 5
5 6
6 7
7 8
5 8
10 10
1 2
2 3
3 4
4 5
5 6
6 1
3 7
4 8
1 9
6 10
Output
Yes
0 0
0 1
1 1
1 2
Yes
0 3
1 3
1 4
1 2
0 2
1 1
0 1
1 0
No
Yes
0 0
1 0
1 1
0 1
0 2
0 3
1 3
1 2
Yes
1 1
1 2
1 3
0 3
0 2
0 1
1 4
0 4
1 0
0 0
----------------------------------------------------------------------------------------------------
D. Dragon Curve
time limit per test: 5 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
5
0 0
-2 0
-7 -7
5 -9
9 9
Output
1 1
2 2
3 189
4 186
2 68
----------------------------------------------------------------------------------------------------
E. Easy Scheduling
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
3
3 1
3 2
10 6
Output
7
4
173
----------------------------------------------------------------------------------------------------
F. Framing Pictures
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
4
0 0
10 0
10 10
0 10
Output
163.661977237
Input
5
0 0
10 0
15 8
5 20
-5 7
Output
365.666028588
----------------------------------------------------------------------------------------------------
G. Game of Chance
time limit per test: 6 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
5
1 4 1 1 4
Output
0.026 0.3584 0.0676 0.0616 0.4864
----------------------------------------------------------------------------------------------------
H. Higher Order Functions
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
()
Output
0
Input
()->()
Output
1
Input
()->()->()
Output
1
Input
(()->())->()
Output
2
Input
()->(((()->())->()->())->())
Output
3
----------------------------------------------------------------------------------------------------
I. Interactive Rays
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
? 0 -10
? 10 -10
? 10 0
? 10 10
? 10 20
? 10 30
! 20 10 10
Output
12.360679775
11.2132034356
0.0
0.0
3.416407865
5.8113883008
----------------------------------------------------------------------------------------------------
J. Just Kingdom
time limit per test: 5 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
5
0 2
1 2
0 1
1 1
0 5
Output
11
7
3
5
11
----------------------------------------------------------------------------------------------------
K. Kingdom of Islands
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

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

Examples
Input
3 3
1 2 3
1 2 4
1 3 4
2 3 6
Output
3
Input
2 1
1 1
1 2 1
Output
-1
----------------------------------------------------------------------------------------------------
M. The Mind
time limit per test: 2 seconds
memory limit per test: 1024 megabytes
input: standard input
output: standard output

Examples
Input
2
2 12 27 71 100
22 29 39 68 90
Output
0.8 0.2 0.0 0.0 0.0 
0.0 0.2 0.2 0.2 0.3 
----------------------------------------------------------------------------------------------------
