Показать сообщение отдельно
Hammer
48 61 6D
Аватар для Hammer
Сообщения: 3,305
Регистрация: 05.10.2006
Откуда: Нижневартовск
Старый пост, нажмите что бы добавить к себе блог 23 ноября 2010, 15:20
  #489 (ПС)
-Цитата от A_D Посмотреть сообщение
-Цитата от Hammer Посмотреть сообщение
На каком языке? Или просто алгоритм? Там всё решается с помощью дихотомии.
алгоритм))
С помощью дихотомии(бинарный поиск) ищем наименьшую длину стороны квадрата, которая позволяет разместить все n дипломов.

На алгоритмическом языке:

Код:
w, h, n //целые числа.

x = 0; //в квадрате со стороной x не гарантированно, что должно поместиться n дипломов
y = n * Максимум(w,h); //в квадрате со стороной y должно гарантированно поместиться n дипломов

ПОКА x < y ВЫПОЛНИТЬ
    c = (y + x) div 2; //пробная длина стороны квадрата посредине между x и y
    k = c div w;  //проверяем переполнение
    k = k * (c div h); //k - количество дипломов, которое поместится в квадрате со стороной c
    ЕСЛИ k >= n ТО y = c //изменяем верхнюю границу квадрата
    ИНАЧЕ x = c + 1; //изменяем нижнюю границу квадрата
КОНЕЦ
Ответом на поставленную задачу будет являться число x.

P.S. Давно решал данную задачу на олимпиаде.

offline
Ответить с цитированием