Бинарный поиск - C (СИ) (70749)

Формулировка задачи:

Имеется вот такая задачка:

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось

n дипломов

, причём, как оказалось, все они имели одинаковые размеры:

w — в ширину и h — в высоту

. Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w на h. Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов

Входные данные:

Входной файл содержит три целых числа: w, h, n (1<=w,h,n<=109 ).

Выходные данные:

В выходной файл необходимо вывести ответ на поставленную задачу. Вот реализовал решение, но некоторые тесты задачка не проходит, не могли бы вы подсказать, в чём ошибка?

#include<stdio.h>
 
main()
{
    int w, h, n, mid, l, r, kol;
    
    scanf("%d%d%d",&w,&h,&n);
    
    if(h>w)
    {
        l=w;
        r=n*h;
    }
    
    else
    {
        l=h;
        r=n*w;
    }
    
    while(l<r)
    {
        mid=(l+r)/2;
        
        kol=(mid/h)*(mid/w);
        
        if(kol<n) l=mid+1;
        else r=mid;
    }
    
    printf("%d",l);
    
}

Решение задачи: «Бинарный поиск»

Листинг программы

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int i, j, min, max, w, h, n, side ;
    puts("Input 1 <= w, h, n <= 109");
    while(1){
        if(3 == scanf("%d%d%d", &w, &h, &n) && (w >= 1 && w <= 109) && (h >= 1 && h <= 109)
           && (n >= 1 && n <= 109))
           break;
        else
            puts("Incorrect input!Try again.");
    }
    if(w <= h){//определяем меньшую и большую стороны диплома
        min = w;
        max = h;
    }
    else{
        min = h;
        max = w;
    }
    if(min * n <= max){
        printf("Side of square = %d\n", max);
        return 0;
    }
    j = n;//сначала выстраиваем дипломы в один ряд
    i = 1;
    while((j * min - i * max) >= max){//и по возможности приближаемся к квадратной форме
        --j;
        if(j * i < n)
            ++i;
        while(j * i - i >= n)
            --j;
    }
    side = j * min > i * max ? j * min : i * max;//в получившемся прямоугольнике выбираем
    printf("Side of square = %d\n", side);                 //бОльшую сторону
    return 0;
}

Объяснение кода листинга программы

Объявление переменных: i, j, min, max, w, h, n, side.
Ввод данных с помощью функции scanf.
Проверка корректности введенных данных.
Определение меньшей и большей сторон прямоугольника.
Проверка возможности построения квадрата со стороной, равной максимальной стороне прямоугольника.
Выстраивание прямоугольников в один ряд.
Приближение к квадратной форме путем перебора вариантов.
Выбор большей стороны в получившемся прямоугольнике.
Вывод результата.
Возврат 0, означающий успешный конец работы программы.