Время: 1 сек.
Память: 16 Мб
Сложность: 28%
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причем, как оказалось, все они имели одинаковые размеры: w – в ширину и h – в высоту.
Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней – дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером w на h. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.
Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.
Входной файл input.txt содержит три целых числа: w, h, n (1 ≤ w, h, n ≤ 109).
В выходной файл output.txt выведите ответ на задачу.
| Ввод | Вывод |
|---|---|
| 2 3 10 | 9 |
Алгоритм
Из-за больших ограничений на n,w,h линейный перебор возможной длины стороны квадрата не проходит по времени, поэтому данную задачу следует решать, используя бинарный поиск по ответу. Очевидно, что размеры доски лежат в пределах от min(w,h) до n * max(w,h). За O(1) легко проверить, поместятся ли все грамоты в квадрат со стороной a (n <= (a / w) * (a / h)). Пускай мы уверены, что искомый ответ лежит в интервале от Min до Max, тогда проверим удовлетворяет ли условию квадрат со стороной Mid = (Min + Max) / 2. Если да, то Max = Mid, иначе Min = Mid+1. Выполняя эту процедуру до тех пор, пока не сойдутся Min и Max мы будем всё точнее получать возможный диапазон ответа (каждый раз область поиска уменьшается в 2 раза). Когда Min станет равно Max выведем значение Min и прекратим работу программы. Сложность такого решения: O(log(n*max(w,h))).