Сірникова модель#3

Сірникова модель (Розбір)

Задача полягає в розміщенні кубиків у тривимірному просторі для максимізації спільного використання ребер. Коли два кубики розміщені поруч один з одним, вони ділять грань, і 4 ребра навколо цієї грані стають внутрішніми для структури, а не вимагають окремих сірників.

Оптимальне розміщення — це прямокутна призма з розмірами якомога ближчими один до одного. Уявіть це як упаковку $n$ кубиків у коробку $a \times b \times c$ a \times b \times c. Кубоподібне розміщення (наприклад, $3 \times 3 \times 3$ 3 \times 3 \times 3) має мінімальну площу поверхні, що означає менше відкритих ребер і, відповідно, менше необхідних сірників.

Ми можемо порахувати сірники, розглядаючи розміщення як тривимірну сітку. Якщо у нас є $a \times b \times c$ a \times b \times c кубиків, сітка має $(a + 1) \times (b + 1) \times (c + 1)$ (a+1) \times (b+1) \times (c+1) вершин. Сірники — це ребра, що з'єднують ці вершини у трьох напрямках: горизонтальному, вертикальному та глибини.

Алгоритм розв'язку

Спочатку знаходимо $k \approx 3 n$ k \approx \sqrt[3]{n}, приблизно кубічний корінь з $n$ . Це дає нам базову лінію для розмірів, які приблизно рівні. Оскільки int(n**(1/3)) може помилятися на одиницю через точність обчислень з плаваючою комою, ми коригуємо $k$ вгору, якщо $(k + 1)^{3} \leq n$ (k+1)^3 \leq n, або вниз, якщо $k^{3} > n$ k^3 > n, поки не знайдемо правильний цілочисельний кубічний корінь.

Далі намагаємось вмістити $n$ кубиків в одне з трьох майже кубічних розміщень: $k \times k \times k$ k \times k \times k, $k \times k \times (k + 1)$ k \times k \times (k+1) або $k \times (k + 1) \times (k + 1)$ k \times (k+1) \times (k+1). Обираємо найбільше розміщення, яке не перевищує $n$ кубиків. Це стає нашим базовим блоком.

Для базового блоку обчислюємо кількість сірників за формулою підрахунку ребер:

сірники = a (b + 1) (c + 1) + b (a + 1) (c + 1) + c (a + 1) (b + 1)

\text{сірники} = a(b+1)(c+1) + b(a+1)(c+1) + c(a+1)(b+1)

У кожному напрямку рахуємо, скільки ребер охоплюють цей напрямок. Наприклад, у напрямку $x$ маємо $a$ ребер, повторених $(b + 1) \times (c + 1)$ (b+1) \times (c+1) разів для кожного ряду і шару.

Якщо після заповнення базового блоку залишаються кубики, розміщуємо їх оптимально зверху. Намагаємось сформувати прямокутник (приблизно $r \times r$ \sqrt{r} \times \sqrt{r}, де $r$ — залишок) для збереження компактності. Будь-які кубики, що не вміщуються в прямокутник, додаються в лінію, що коштує $3$ сірники на кубик плюс $2$ для прикріплення до структури.

Реалізація

import math

n = int(input())

if n == 0:
    print(0)
else:
    # Знаходимо k ≈ кубічний корінь з n, коригуючи для точності обчислень
    k = int(n**(1/3))
    while (k+1)**3 <= n:
        k += 1
    while k**3 > n:
        k -= 1

    # Обираємо розміри базового блоку
    # Пробуємо k×k×k, k×k×(k+1) або k×(k+1)×(k+1)
    if n <= k * k * (k + 1):
        a = k
        b = k
        c = k
        rem = n - k**3
    elif n <= k * (k+1) * (k+1):
        a = k
        b = k
        c = k + 1
        rem = n - k * k * (k + 1)
    else:
        a = k
        b = k + 1
        c = k + 1
        rem = n - k * (k+1) * (k+1)

    # Рахуємо сірники для базового блоку: ребра в напрямках x, y та z
    result = a * (b+1) * (c+1) + b * (a+1) * (c+1) + c * (a+1) * (b+1)

    # Додаємо сірники для залишкових кубиків, якщо такі є
    if rem > 0:
        # Розміщуємо залишок як прямокутник s×t
        s = int(math.isqrt(rem))

        if s > 0:
            t = rem // s
        else:
            t = 0

        left = rem - s * t

        # Додаємо ребра для прямокутника зверху базового блоку
        result += (s+1) * (t+1) + s * (t+1) + t * (s+1)

        # Додаємо залишкові кубики в лінію
        if left > 0:
            result += 3 * left + 2

    print(result)

Python

Аналіз складності:

Часова складність: $O (1)$ — тільки арифметичні операції
Просторова складність: $O (1)$ — константна додаткова пам'ять