Піксельний равлик#182

Піксельний равлик (Розбір)

Малювати равлика й рахувати клітинки програмно не потрібно — при $k \leq 1 0^{8}$ k \le 10^8 це неможливо. Натомість помітимо, що відповідь лінійна за $k$ .

Подивимось, як змінюється фігура при збільшенні порядку на одиницю. Рамка — це периметр квадрата зі стороною $k$ , тобто $4 k - 4$ 4k - 4 клітинки; при зростанні $k$ на одиницю вона додає рівно $4$ клітинки. Зовнішній шар — це така сама рамка, тільки на одиницю більша з кожного боку, тому й вона додає рівно $4$ клітинки. Місток же завжди одна клітинка, і правило винятків біля містка теж не залежить від $k$ .

Отже, кожен наступний порядок додає рівно $8$ клітинок, і відповідь має вигляд $8 k + C$ 8k + C. Сталу $C$ визначаємо з малюнка в умові за будь-яким невеликим $k$ ; вона дорівнює $2$ , тобто

відповідь = 8 k + 2 (k \geq 2) .

\text{відповідь} = 8k + 2 \qquad (k \ge 2).

Окремо треба обробити $k = 1$ k = 1. Там рамка вироджується: квадрат зі стороною $1$ — це одна клітинка, а не чотири сторони, тому формула $4 k - 4$ 4k-4 (яка дала б нуль) не працює. Пряме підрахування за малюнком дає

відповідь = 11 (k = 1) .

\text{відповідь} = 11 \qquad (k = 1).

Обчислення — $O (1)$ . Значення сягає близько $8 \cdot 1 0^{8}$ 8 \cdot 10^8, що ще вміщується у 32-бітний знаковий тип, але 64-бітний надійніший.

k \leq 1 0^{8}

4 k - 4

8 k + C

відповідь = 8 k + 2 (k \geq 2) .

k = 1

4 k - 4

відповідь = 11 (k = 1) .

8 \cdot 1 0^{8}