Bubble Cup 11 - Finals [Online Mirror, Div. 1]


A. Last chance
time limit per test: 2 seconds
memory limit per test: 128 megabytes
input: standard input
output: standard output

Examples
Input
3 5
0 1 4
2 5 4 1
1 1 4
Output
4
2 1
3 2
1 4
2 5
----------------------------------------------------------------------------------------------------
B. Space Isaac
time limit per test: 1.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
2 5
3 4
Output
1
2
Input
4 1000000000
5 25 125 625
Output
0
Input
2 4
1 3
Output
2
0 2
----------------------------------------------------------------------------------------------------
C. Hyperspace Highways
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 7 2
1 2
1 3
1 4
2 3
2 4
3 4
1 5
1 4
2 5
Output
1
2
Input
8 11 4
1 2
2 3
3 4
4 5
1 3
1 6
3 5
3 7
4 7
5 7
6 8
1 5
2 4
6 7
3 8
Output
2
2
3
3
----------------------------------------------------------------------------------------------------
D. Interstellar battle
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
0.50 0.29 0.49 0.95 0.83
2 3
0 3
3 4
2 1
3
4 0.66
1 0.69
0 0.36
Output
1.68040
1.48440
1.61740
----------------------------------------------------------------------------------------------------
E. Ancient civilizations
time limit per test: 0.5 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5
0 0 1
1 0 0
0 1 0
1 1 1
3 2 0
Output
3
1 4
4 2
3 0
----------------------------------------------------------------------------------------------------
F. Shady Lady
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
1 1
2 0
0 2
Output
Ani
Input
4
0 0
0 1
0 2
0 8
Output
Borna
----------------------------------------------------------------------------------------------------
G. AI robots
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3 2
3 6 1
7 3 10
10 5 8
Output
1
----------------------------------------------------------------------------------------------------
H. Self-exploration
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
10
1001
0
0
1
1
Output
1
Input
10
10001
1
2
3
4
Output
0
----------------------------------------------------------------------------------------------------
I. Palindrome Pairs
time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
3
aa
bb
cd
Output
1
Input
6
aab
abcac
dffe
ed
aa
aade
Output
6
----------------------------------------------------------------------------------------------------
J. Moonwalk challenge
time limit per test: 6 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
2 3 g
3 4 n
5 3 o
6 1 n
1 2 d
7
1 6 n
6 4 dg
6 4 n
2 5 og
1 2 d
6 5 go
2 3 g
Output
1
1
2
0
1
1
1
----------------------------------------------------------------------------------------------------
