Карткові будинки#5716

Карткові будинки (Розбір)

Нехай $f (h)$ — кількість карт, необхідних для побудови карткового будинку висоти $h$ . Наприклад, $f (1) = 2, f (2) = 7, f (3) = 15$ f(1) = 2, f(2) = 7, f(3) = 15.

Щоб побудувати будинок висоти $h$ , в основі необхідно встановити $h$ будинків висоти $1$ , на що знадобиться $2 h$ карт, а також $h - 1$ h - 1 перекриттів. На цю основу потім встановлюється будинок висоти $h - 1$ h - 1, для будівництва якого потрібно $f (h - 1)$ f(h - 1) карт.

Відповідно,

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

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

або

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

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

Виведемо явну формулу. Послідовно розкриваючи рекурсію, отримаємо:

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}

Приклад

Для будинку висоти $1$ достатньо $2$ карти.

Для будинку висоти $2$ необхідно $7$ карт.

Будинок висоти $3$ можна побудувати із $15$ карт.

Реалізація алгоритму

Читаємо висоту будинку $n$ .

scanf("%lld", &n);

Визначаємо та виводимо кількість карт у будинку.

res = n * (3 * n + 1) / 2;
printf("%lld\n", res);