AIM Tech Round 4 (Div. 1)


A. Sorting by Subsequences
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
6
3 2 1 6 5 4
Output
4
2 1 3
1 2
2 4 6
1 5
Input
6
83 -75 -49 11 37 62
Output
1
6 1 2 3 4 5 6
----------------------------------------------------------------------------------------------------
B. Interactive LowerBound
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

Examples
Input
5 3 80
97 -1
58 5
16 2
81 1
79 4
Output
? 1
? 2
? 3
? 4
? 5
! 81
----------------------------------------------------------------------------------------------------
C. Upgrading Tree
time limit per test: 4 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3
3 2
1 3
Output
0
Input
7
1 2
2 3
3 4
4 5
5 6
6 7
Output
2
4 3 2
4 5 6
----------------------------------------------------------------------------------------------------
D. Dynamic Shortest Path
time limit per test: 10 seconds
memory limit per test: 512 megabytes
input: standard input
output: standard output

Examples
Input
3 2 9
1 2 0
2 3 0
2 1 2
1 3
1 2
2 1 1
1 3
1 2
2 2 1 2
1 3
1 2
Output
1
0
2
1
4
2
Input
5 4 9
2 3 1
2 4 1
3 4 1
1 2 0
1 5
1 4
2 1 2
2 1 2
1 4
2 2 1 3
1 4
2 1 4
1 4
Output
-1
1
2
3
4
----------------------------------------------------------------------------------------------------
E. Maximum Flow
time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

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