Problem G. Graveyard Design
Statement
King George has recently decided that he would like to have a new
design for the royal graveyard. The graveyard must consist of several
sections, each of which must be a square of graves. All sections
must have different number of graves.
After a consultation with his astrologer, King George decided that
the lengths of section sides must be a sequence of successive
positive integer numbers. A section with side length s contains s2
graves.
George has estimated the total number of graves
that will be located on the graveyard and now wants to know all
possible graveyard designs satisfying the condition.
You were asked to find them.
The picture below illustrates the graveyard for the first example.
Input file format
Input file contains
n — the number of graves to be located in the graveyard.
Output file format
On the first line of the output file print k — the number of possible
graveyard designs. Next k lines must contain the descriptions of the
graveyards. Each line must start with l — the number of sections in the
corresponding graveyard, followed by l integers — the lengths of section
sides (successive positive integer numbers).
Change: sections must me enumerated in descending order.
Constraints
1 ≤
n ≤ 10
14.
Sample tests
| No. |
Input file (graveyard.in) |
Output file (graveyard.out) |
|---|
| 1 |
29
|
1
3 2 3 4
|
| 2 |
2030
|
2
4 21 22 23 24
3 25 26 27
|
Problem H. Honey and Milk Land
Statement
Bad rumors are spreading over the Land of Honey and Milk.
Informed people say that the milk in the famous grid of milk rivers
is turning sour. Of course, the security service quickly found out
that the people are informed by the Kingdom of Tar, which is jealous to
tourist popularity of the land. However, this discovery does not help to
stop these rumors. The government wants to prevent crisis of
the tourist industry, so it wants to establish daily monitoring
of the rivers.
A new Milk Security Department is established, which is responsible for
preventing the milk from turning sour. It's equipped with powerful
boilers and pasteurizer, so any danger for the milk can be quickly
neutralized. To better fight the new threat, the department
needs to know about possible dangers beforehand. They have a
helicopter, capable to check milk freshness. The equipment is perfect.
It's enough just to cross a river in any place in order to detect all
its potentially dangerous places.
To start the Milk Security Department operations, the government needs
to add funding of the Service to the Land budget. One of the issues is
the morning route of the helicopter. The helicopter should check all
the rivers in the shortest time. They need to determine the price of
this flight to add it to the budget.
The grid consists of two sets of milk rivers. Rivers from the first set
run from North to South, rivers from the second set — from East to
West. The rivers are straight. The rivers from each set are parallel
and the distance between the adjacent rivers is known. There are n
rivers, running from North to South and e rivers, running from
East to West.
The government needs to determine the minimal morning flight cost.
Each kilometer costs 1 honey barrel, the Land national currency.
The cost of take-off and landing is not included into this cost.
You may freely choose the starting and ending points of the flight.
Input file format
The first line of the input file contains n and e.
The second line contains n − 1 integer numbers that represent
distances (in kilometers) between adjacent rivers running from
North to South, listed from East to West.
The third line contains e − 1 integer numbers that represent
distances (also in kilometers) between adjacent rivers running
from East to West, listed from North to South. The distance
between any two adjacent rivers does not exceed 27 kilometers.
Output file format
Output the minimal morning flight cost in honey barrels. Since
there is no smaller denomination, you must output the minimal integer
number of honey barrels that would be sufficient to support the
flight.
Constraints
1 ≤
n,
e ≤ 1000.
Sample tests
| No. |
Input file (honey.in) |
Output file (honey.out) |
|---|
| 1 |
2 1
1
|
1
|
| 2 |
10 10
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
|
26
|
| 3 |
1 1
|
0
|
Problem K. K-th Number
Statement
You are working for Macrohard company in data structures
department. After failing your previous task about key insertion
you were asked to write a new data structure that would be able
to return quickly k-th order statistics in the array segment.
That is, given an array a[1…n] of different integer numbers,
your program must answer a series of questions
Q(i, j, k)
in the form:
«What would be the k-th number in a[i…j] segment,
if this segment was sorted?»
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the
question be Q(2, 5, 3). The segment a[2…5] is (5, 2, 6, 3).
If we sort this segment, we get (2, 3, 5, 6), the third number is 5,
and therefore the answer to the question is 5.
Input file format
The first line of the input file contains
n — the size of the array,
and
m — the number of questions to answer.
The second line contains
n different integer numbers
not exceeding 10
9 by their absolute values — the array for which the
answers should be given.
The following
m lines contain question descriptions, each description
consists of three numbers:
i,
j, and
k
(1 ≤
i ≤
j ≤
n,
1 ≤
k ≤
j -
i + 1)
and represents the question
Q(
i,
j,
k).
Output file format
For each question output the answer to it — the
k-th number
in sorted
a[
i…
j] segment.
Constraints
1 ≤
n ≤ 100000,
1 ≤
m ≤ 5000.
Sample tests
| No. |
Input file (kth.in) |
Output file (kth.out) |
|---|
| 1 |
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
|
5
6
3
|
