Card houses#5716

Card houses (Editorial)

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

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

Therefore,

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

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

or equivalently,

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

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

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

f (h) = 3 h - 1 + f (h - 1) = = 3 h - 1 + 3 (h - 1) - 1 + f (h - 2) = ... = 3 h - 1 + 3 (h - 1) - 1 + 3 (h - 2) - 1 + ... + 3 \cdot 1 - 1 = = 3 (h + (h - 1) + (h - 2) + ... + 1) - h = = 3 \cdot \frac{h + 1}{2} h - h = \frac{3 h ^{2} + 3 h}{2} - \frac{2 h}{2} = \frac{3 h ^{2} + h}{2}

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 \cdot 1 - 1 = \\ = 3 (h + (h - 1) + (h - 2) + ... + 1) - h = \\ = 3 \cdot \frac{h + 1}{2} h - h = \frac{3h^2+3h}{2} - \frac{2h}{2} = \frac{3h^2+h}{2}

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);