## CCOQR '16 - Data Structure

View as PDF

Points: 15 (partial)
Time limit: 0.4s
Memory limit: 64M

Author:
Problem types

It'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.

• 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 .

#### 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 2

#### Output for Sample Input

15

#### Explanation 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.

• commented on Nov. 2, 2017, 9:59 a.m.

Is it guaranteed that the answer can be stored in a 64 bit integer? What if the test case is 10e9 1 1 1 ?

• commented on Nov. 2, 2017, 12:59 p.m.

The answer to that case is on the order of , which fits in a 64-bit integer.

• commented on Nov. 2, 2017, 3:32 p.m.

Sorry im dumb, i think i typed 2^54 into my calculator earlier

• commented on Nov. 2, 2017, 9:33 p.m.

10e9 is actually , 1e9 is . That might be why.

• commented on Nov. 3, 2017, 8:32 a.m.

UGHH whats wrong with me, thx for all ur help

• commented on Dec. 13, 2016, 1:16 p.m.

How is this a data structure problem?

• commented on March 20, 2021, 7:50 p.m.

The problem is about a structure that contains data, not a data structure problem

• commented on Jan. 19, 2017, 6:29 p.m.

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~

• commented on March 25, 2016, 9:55 a.m.

Is anyone interested in making editorials for these ccoqr problems?