Diplomlar (Həll təhlili)

Tutaq ki, $x$ axtarılan kvadrat taxtanın tərəfi uzunluğudur. $x$-i binar axtarışla tapacağıq. Aydındır ki, 0 < x \le max(w, h) \cdot n. Axtarışı [a; b] = [0; max(w, h) \cdot n] intervalında başlayacağıq.

Tutaq ki, m = (a + b) / 2 — taxtanın cari tərəf uzunluğudur. Çünki diplomun ölçüsü w \cdot h-dır, beləliklə taxtada maksimum (m / w) \cdot (m / h) diplom yerləşdirilə bilər. Əgər bu ədəd $n$-dən kiçikdirsə, o halda taxtanın ölçüsü çox kiçikdir, beləliklə a = m + 1 qoyuruq. Əks halda axtarışın sağ sərhədini yeniləyirik: b = m.

Tutaq ki, diplomun ölçüsü w \times h = 2 \times 3-dür.

• 8 \times 8 taxtasında maksimum (8 / 2) \cdot (8 / 3) = 4 \cdot 2 = 8 diplom yerləşdirilə bilər;

• 9 \times 9 taxtasında maksimum (9 / 2) \cdot (9 / 3) = 4 \cdot 3 = 12 diplom yerləşdirilə bilər;

10 diplom yerləşdirə bilən taxtanın minimal tərəf ölçüsü 9-dur.

Alqoritmin realizasiyası

Giriş verilənlərini oxuyuruq.

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

Binar axtarış sərhədlərini [a; b] = [0; max(w, h) \cdot n] kimi təyin edirik.

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

Binar axtarışa başlayırıq.

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

w \cdot h ölçülü diplomların sayı $m$ tərəfi olan taxtada yerləşə bilən maksimum ölçü olaraq dip = (m / w) \cdot (m / h) hesablanır.

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

Cavabı çıxışa veririk.

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

Python realizasiyası

Giriş verilənlərini oxuyuruq.

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

Binar axtarış sərhədlərini [a; b] = [0; max(w, h) \cdot n] kimi təyin edirik.

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

Binar axtarışa başlayırıq.

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

w \cdot h ölçülü diplomların sayı $m$ tərəfi olan taxtada yerləşə bilən maksimum ölçü olaraq dip = (m / w) \cdot (m / h) hesablanır.

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

Cavabı çıxışa veririk.

print(b)