Кількість одиниць#44

Кількість одиниць (Розбір)

Нехай $f (n)$ — мінімальна кількість одиниць, за допомогою яких можна представити число $n$ . Очевидно, що $f (1) = 1$ f(1) = 1.

Число $2$ можна представити тільки як суму двох одиниць: $2 = 1 + 1$ 2 = 1 + 1. Тому $f (2) = 2$ f(2) = 2. Аналогічно, число $3$ представляється тільки у вигляді суми трьох одиниць: $3 = 1 + 1 + 1$ 3 = 1 + 1 + 1. Тому $f (3) = 3$ f(3) = 3.

Число $4$ можна записати або як суму чотирьох одиниць: $4 = 1 + 1 + 1 + 1$ 4 = 1 + 1 + 1 + 1, або як добуток: $4 = (1 + 1) \cdot (1 + 1)$ 4 = (1 + 1) \cdot (1 + 1). Однак в обох випадках використовується $4$ одиниці, тому $f (4) = 4$ f(4) = 4.

Розглянемо вираз, значення якого дорівнює $n$ .

1. Припустимо, що останньою виконаною операцією є додавання. Нехай один доданок дорівнює $i$ і складається з $f (i)$ одиниць, а другий доданок дорівнює $n - i$ n - i і складається з $f (n - i)$ f(n - i) одиниць. Тоді значення $i$ слід вибрати так, щоб сума $f (i) + f (n - i)$ f(i) + f(n - i) була мінімальною.

При цьому значення $i$ достатньо перебирати до $n /2$ , оскільки можна вважати, що перший доданок не перевищує другий. Таким чином, отримуємо наступне співвідношення:

f (n) = 1 \leq i \leq n /2 min (f (i) + f (n - i))

f(n) = \min_{1 \le i \le n/2} (f(i)+f(n - i))

2. Нехай останньою виконаною операцією було множення. Припустимо, що перший множник $i$ складається з $f (i)$ одиниць, а другий множник $n / i$ складається з $f (n / i)$ одиниць. Цей випадок має місце, якщо $n$ ділиться на $i$ без остачі.

Значення $i$ слід вибрати так, щоб сума $f (i) + f (n / i)$ f(i) + f(n / i) була мінімальною. При цьому достатньо перебирати значення $i$ в діапазоні від $2$ до $⌊ n ⌋$ \lfloor \sqrt{n} \rfloor. Таким чином, отримуємо наступне співвідношення:

f (n) = 1 \leq i \leq n min (f (i) + f (n / i))

f(n) = \min_{1 \le i \le \sqrt{n}} (f(i)+f(n/i))

Таким чином

f (n) = min (1 \leq i \leq n /2 min (f (i) + f (n - i)), 1 \leq i \leq n min (f (i) + f (n / i)))

f(n) = \min\left( \min_{1 \le i \le n/2} \bigl(f(i) + f(n - i)\bigr),\; \min_{1 \le i \le \sqrt{n}} \bigl(f(i) + f(n / i)\bigr) \right)

Приклад

Обчислимо відповідь для $n = 7$ n = 7:

f (7) = f (6) + f (1) = (f (2) + f (3)) + f (1) = 2 + 3 + 1 = 6

f(7) = f(6) + f(1) = (f(2) + f(3)) + f(1) = 2 + 3 + 1 = 6

Число $7$ можна представити за допомогою $6$ одиниць, а саме:

7 = (1 + 1) \cdot (1 + 1 + 1) + 1

7 = (1 + 1) \cdot (1 + 1 + 1) + 1

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

Оголосимо масив $r es$ .

int res[5001];

Зчитуємо вхідне значення $n$ .

scanf("%d",&n);

Ініціалізуємо $r es [1] = 1$ res[1] = 1.

res[1] = 1;

Далі послідовно обчислимо значення $r es [2], r es [3], ..., r es [n]$ res[2], res[3], ..., res[n] за наведеною вище формулою.

for (i = 2; i <= n; i++)
{
  res[i] = i;
  for (j = 1; 2 * j < i; j++)
    if (res[j] + res[i - j] < res[i]) res[i] = res[j] + res[i - j];
  for (j = 2; j * j <= i; j++)
    if (i % j == 0) 
      if (res[j] + res[i / j] < res[i]) res[i] = res[j] + res[i / j];
}

C++

Виводимо відповідь.

printf("%d\n",res[n]);