CCOQR '16 - Data Structure
View as PDFIt's a well-known fact that, inside computers, all data is stored in 2D pyramids of data blocks.
A certain pyramid has (
) rows, numbered
from top to bottom. Each row
has
block spaces, which are labelled
from left to right. Each block space
in rows
rests on top of two supporting block spaces in the row below it — block spaces
and
. For example, a pyramid with 6 rows is illustrated below, with block spaces
,
, and
indicated in red:
Now, each block space may either contain data, or be empty. A block space containing data is only stable if it's in the bottom row (row ), or if both of its two supporting block spaces also contain data. The entire pyramid is only stable if all of its non-empty block spaces are stable.
You know that there are (
) different block spaces which must contain data - the
of these is block space
(
). All of the other block spaces in the pyramid may either be filled with arbitrary data or be left empty. However, everyone knows that data is expensive. As such, you're interested in the smallest amount of data that the pyramid's block spaces can contain such that at least the
required block spaces contain data, and the entire data structure is stable.
Subtasks
- For 3 of the 15 marks available,
and
.
- For another 3 of the 15 marks available,
and
.
- For another 3 of the 15 marks available,
and
.
Note that the original data were weak, so an additional test case was added to the first two subtasks. Data were provided by .
Input Specification
The first line of the input contains two integers, and
. The remaining
lines each contain two integers,
and
for
.
Output Specification
Output a single integer, the minimum number of block spaces which can contain data such that the entire pyramid is stable. Note that this value may not fit in a 32-bit signed integer, and may need to be stored in a long long / long / int64 variable in C++ / Java / Pascal, respectively.
Sample Input
6 3
3 1
4 4
6 2Output for Sample Input
15Explanation for Output for Sample Input
The diagram below illustrates the pyramid described by the sample case, where the 3 red block spaces must contain data, while the 12 orange block spaces represent the optimal set of blocks to additionally fill with data to make the entire pyramid stable.
Comments
Since the original data were weak, an additional test case was added to the first two batches, and all submissions were rejudged. Data were provided by dxke02.
Is it guaranteed that the answer can be stored in a 64 bit integer? What if the test case is
10e9 1 1 1?The answer to that case is on the order of
, which fits in a 64-bit integer.
Sorry im dumb, i think i typed 2^54 into my calculator earlier
10e9is actually1e9isUGHH whats wrong with me, thx for all ur help
How is this a data structure problem?
The problem is about a structure that contains data, not a data structure problem
You're right Data structure is not a data structure problem, Convex hull is not a convex hull problem, Gaussian elimination is not a Gaussian elimination problem, Heavy-light decomposition is not a heavy-light decomposition problem. This is the real world~
Raytracing is not a ray tracing problem, Gradient Descent is not a gradient descent problem.
Is anyone interested in making editorials for these ccoqr problems?