Rockethon 2015


A. Game
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 2 1 2
Output
Second
Input
2 1 1 1
Output
First
----------------------------------------------------------------------------------------------------
B1. Permutations
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 2
Output
2 1 
Input
3 2
Output
1 3 2 
----------------------------------------------------------------------------------------------------
B2. Permutations
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 2
Output
2 1 
Input
3 2
Output
1 3 2 
----------------------------------------------------------------------------------------------------
C. Second price auction
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
4 7
8 10
5 5
Output
5.7500000000
Input
3
2 5
3 4
1 6
Output
3.5000000000
----------------------------------------------------------------------------------------------------
D1. Constrained Tree
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 2
1 2 LEFT
1 3 RIGHT
Output
2 1 3
Input
3 2
1 2 RIGHT
1 3 LEFT
Output
IMPOSSIBLE
----------------------------------------------------------------------------------------------------
D2. Constrained Tree
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 2
1 2 LEFT
1 3 RIGHT
Output
2 1 3
Input
3 2
1 2 RIGHT
1 3 LEFT
Output
IMPOSSIBLE
----------------------------------------------------------------------------------------------------
E1. Subarray Cuts
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 3
5 2 4 3 1
Output
12
Input
4 2
7 4 3 7
Output
8
----------------------------------------------------------------------------------------------------
E2. Subarray Cuts
time limit per test: 2 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
5 3
5 2 4 3 1
Output
12
Input
4 2
7 4 3 7
Output
8
----------------------------------------------------------------------------------------------------
F1. Scaygerboss
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 4 2 3
....
.###
####
####
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
1 1 2
Output
2
Input
2 4 2 2
....
.###
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
Output
-1
----------------------------------------------------------------------------------------------------
F2. Scaygerboss
time limit per test: 3 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
4 4 2 3
....
.###
####
####
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
1 1 2
Output
2
Input
2 4 2 2
....
.###
2 1 1
2 1 2
2 1 2
2 1 2
2 1 2
Output
-1
----------------------------------------------------------------------------------------------------
G1. Inversions problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 1
1 2 3
Output
0.833333333333333
Input
3 4
1 3 2
Output
1.458333333333334
----------------------------------------------------------------------------------------------------
G2. Inversions problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 1
1 2 3
Output
0.833333333333333
Input
3 4
1 3 2
Output
1.458333333333334
----------------------------------------------------------------------------------------------------
G3. Inversions problem
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 1
1 2 3
Output
0.833333333333333
Input
3 4
1 3 2
Output
1.458333333333334
----------------------------------------------------------------------------------------------------
