Yandex.Algorithm 2011: Finals


A. Domino
time limit per test: 0.5 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
8 8
.aabbcc.
.defghi.
kdefghij
klmnopqj
.lmnopq.
.rstuvw.
xrstuvwy
xzzAABBy
Output
10080
.001122.
.001122.
33440055
33440055
.225566.
.225566.
66113344
66113344
----------------------------------------------------------------------------------------------------
B. Superset
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

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

Examples
Input
3
0.115590 0.384031 0.443128 0.562356
Output
0.4286122500
Input
3
1 1 1 1
Output
0.9999999999
----------------------------------------------------------------------------------------------------
D. Robot in Basement
time limit per test: 4 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 5 7
#####
#...#
#...#
#E..#
#####
UULLDDR
Output
6
Input
5 5 7
#####
#.#.#
#...#
#E..#
#####
UULLDDR
Output
-1
Input
5 3 2
###
#.#
#.#
#E#
###
DD
Output
2
----------------------------------------------------------------------------------------------------
E. Leaders
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
7 7
1 3
1 4
2 3
2 4
5 6
6 7
7 5
8
1 2
1 3
1 4
2 4
1 5
5 6
5 7
6 7
Output
No
Yes
Yes
Yes
No
Yes
Yes
Yes
----------------------------------------------------------------------------------------------------
