У Маши есть прямоугольная шоколадка, состоящая из m×n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки. У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек). Определите число долек в этом куске. Условия выполнения Правила автоматической проверки Ограничения: Время выполнения: < 1000 ms Выделяемая память 256 mb Входные данные Программа получает на вход три натуральных числа, каждое в отдельной строке: m , n и k . Все числа — целые положительные, при этом m и n не превосходят 10 6 , а k≤mn . Обратите внимание на то, что значение mn , а, значит, и значение k в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). Выходные данные Программа должна вывести одно целое число — максимально возможное количество долек в том прямоугольном куске, который получит Юра. Система оценки Решения, правильно работающие при m≤1000 и n≤1000 , будут оцениваться в 60 баллов. Примечание: В примере из условия нужно разделить шоколадку 4×5 на 4 кусочка. Самый большой кусочек будет состоять из 16 долек, как показано на картинке. Примеры № Входные данные Выходные данные Примечание 1 4 5 4 16

Чтобы решить задачу о делении шоколадки, нам нужно определить максимальный размер самого большого куска, который может получить Юра, когда шоколадка размером \(m \times n\) разломана на \(k\) кусочков.

Основная идея заключается в том, что мы хотим, чтобы один из кусочков был как можно больше. Для этого нам необходимо разделить площади шоколадки так, чтобы разница в длинах и ширинах кусочков была минимальной.

Шаги для нахождения решения:

1. Общая площадь шоколадки: Площадь шоколадки равна \(m \times n\).

2. Минимальная площадь каждого кусочка: Если шоколадка разделяется на \(k\) кусочков, минимально возможная площадь одного кусочка (при равномерном делении) равна \(\frac{m \times n}{k}\). Однако, из-за целочисленного разбиения, мы не можем гарантировать, что все кусочки будут равны.

3. Определение максимального размера: Нам нужно найти максимальную площадь самого большого кусочка. Мы можем использовать бинарный поиск для нахождения этого значения.

Алгоритм:

1. Задаем границы для бинарного поиска:

   • Левую границу \( \text{left} = 1 \) (размер самого маленького куска).
   • Правую границу \( \text{right} = m \times n \) (размер всей шоколадки).

2. В процессе бинарного поиска:

   • Вычисляем среднее значение \( \text{mid} \).
   • Проверяем, возможно ли получить \(k\) кусков, каждый из которых будет иметь площадь не больше \(\text{mid}\).

3. Для проверки:

   • Определяем, сколько кусков можно получить, деля размер шоколадки по высоте и ширине с учётом площади \( \text{mid} \).
   • Площадь куска не должна превышать \(\text{mid}\), поэтому у нас будет такое количество кусочков: \[ \text{count} = \left\lfloor \frac{m}{\text{height}} \right\rfloor \times \left\lfloor \frac{n}{\text{width}} \right\rfloor \]

4. Если количество кусков больше или равно \(k\), значит мы можем увеличить \(\text{mid}\), иначе уменьшаем.

Пример реализации:

def can_divide(m, n, k, mid):
    count = 0
    for height in range(1, m + 1):
        for width in range(1, n + 1):
            if height * width <= mid:
                count += (m // height) * (n // width)
            if count >= k:
                return True
    return count >= k

def max_piece_size(m, n, k):
    left = 1
    right = m * n
    answer = 1

    while left <= right:
        mid = (left + right) // 2
        if can_divide(m, n, k, mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    
    return answer

# Ввод значений
m = int(input())
n = int(input())
k = int(input())

# Получение результата и его вывод
result = max_piece_size(m, n, k)
print(result)

Итого: Ваша задача заключается в вычислении максимального количества долек в самом большом куске, который получит Юра, выполнив предложенный алгоритм.