Дипломи (Розбір)

Нехай $x$ — шуканий розмір сторони квадратної плати. Шукатимемо $x$ бінарним пошуком. Очевидно, що 0 < x \le max(w, h) \cdot n. Пошук почнемо на відрізку [a; b] = [0; max(w, h) \cdot n].

Нехай m = (a + b) / 2 — поточний розмір сторони плати. Оскільки диплом має розмір w \cdot h, то на ньому можна розмістити максимум (m / w) \cdot (m / h) дипломів. Якщо це число менше $n$, то розмір плати недостатній, встановлюємо a = m + 1. Інакше зсуваємо праву межу пошуку: b = m.

Нехай розмір диплома w \times h = 2 \times 3.

• На платі 8 \times 8 можна розмістити максимально (8 / 2) \cdot (8 / 3) = 4 \cdot 2 = 8 дипломів;

• На платі 9 \times 9 можна розмістити максимально (9 / 2) \cdot (9 / 3) = 4 \cdot 3 = 12 дипломів;

Мінімальний розмір сторони плати, на якій можна розмістити $10$ дипломів, дорівнює $9$.

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

Читаємо вхідні дані.

scanf("%lld %lld %lld", &w, &h, &n);

Встановлюємо межі бінарного пошуку [a; b] = [0; max(w, h) \cdot n].

a = 0;
b = max(w, h) * n;

Запускаємо бінарний пошук.

while (a < b)
{
  m = (a + b) / 2;

Найбільша кількість дипломів розміру w \cdot h, яку можна розмістити на платі зі стороною $m$, дорівнює dip = (m / w) \cdot (m / h).

  dip = (m / w) * (m / h);
  if (dip < n) a = m + 1;
  else b = m;
}

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

printf("%lld\n", b);

Python реалізація

Читаємо вхідні дані.

w, h, n = map(int, input().split())

Встановлюємо межі бінарного пошуку [a; b] = [0; max(w, h) \cdot n].

a = 0
b = max(w, h) * n

Запускаємо бінарний пошук.

while a < b:
  m = (a + b) // 2

Найбільша кількість дипломів розміру w \cdot h, яку можна розмістити на платі зі стороною $m$, дорівнює dip = (m / w) \cdot (m / h).

  dip = (m // w) * (m // h)
  if dip < n:
    a = m + 1
  else:
    b = m

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

print(b)