Diplomas
InterviewTime limit2sMemory limit512 MB
Given n identical w by h rectangles, find the smallest square side length that can contain all of them without overlaps.
- Level
Medium5 of 10
- Topics
- Binary search, Math, Greedy, Implementation
- Solved
- No attempts yet
Problem
When Petya was in school, he often took part in programming, mathematics, and physics olympiads. Since he was a capable boy and studied hard, he received diplomas at many of these olympiads. By the time he finished school, he had collected n diplomas, and it turned out that they all had the same size: w in width and h in height.
Now Petya studies at one of the best Russian universities and lives in a dormitory with his classmates. He decided to decorate his room by hanging his school olympiad diplomas on one of the walls. Since attaching diplomas to a concrete wall is rather difficult, he decided to buy a special cork board, attach it to the wall, and attach the diplomas to it. To make this arrangement look nicer, Petya wants the board to be square and to take up as little space on the wall as possible. Each diploma must be placed strictly inside a rectangle of size w by h. Rectangles corresponding to different diplomas must not have any common interior points.
You must write a program that computes the minimum side length of the board Petya needs to place all his diplomas.
Input
The input file contains three integers: w, h, n (1 ≤ w, h, n ≤ 10^9).
Output
The output file must contain the answer to the problem.
Hint
