5716. Card houses

Slavik dreams of becoming a performer of an original genre, so he constantly practices manipulating various objects. Lately, he has been dedicating all his free time to building card houses. He has already managed to construct a four-story card house at home, which required 26 cards. During a technology class, Slavik secretly demonstrated his skill to his classmates by building a three-story card house using only 15 cards.

The “creations” of the future artist are captured in the photos below:

Now Slavik is interested in a mathematical question: how many cards are needed to build a card house of  stories?

He asks for your help, as mathematics is not his strongest subject.

Input. One non-negative integer n (n ≤ 10⁸) –  the number of stories in the card house to be built.

Output. Print the number of cards required to build a card house with n stories.

Sample input	Sample output
3	15

SOLUTION

combinatorics

Algorithm analysis

Let f(h) denote the number of cards required to build a card house of height . For example, f(1) = 2, f(2) = 7, and f(3) = 15.

To build a house of height h, one must place h houses of height 1 at the base, which requires 2h cards, as well as h – 1 horizontal cards forming the overlaps. On top of this base, a house of height h – 1 is placed, which requires f(h – 1) cards.

Therefore,

f(h) = 2h + h – 1 + f(h – 1)

or equivalently,

f(h) = 3h – 1 + f(h – 1)

Let us derive an explicit formula. By successively expanding the recursion, we obtain:

f(h) = 3h – 1 + f(h – 1) =

= 3h – 1 + 3(h – 1) – 1 + f(h – 2) =

. . .

= 3h – 1 + 3(h – 1) – 1 + 3(h – 2) – 1 + … + 3 * 1 – 1 =

= 3 (h + (h – 1) + (h – 2) + … + 1) – h =

= = =

Example

A house of height 1 requires 2 cards.

A house of height 2 requires 7 cards.

A house of height 3 can be built using 15 cards.

Algorithm implementation

Read the height of the house n.

scanf("%lld", &n);

Compute and print the number of cards required to build the house.

res = n * (3 * n + 1) / 2;

printf("%lld\n", res);