Деление шоколадки Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт У Маши есть прямоугольная шоколадка, состоящая из т х п квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки. У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек). Определите число долек в этом куске. Формат входных данных Программа получает на вход три натуральных числа, каждое в отдельной строке: т, п и к. Все числа — целые положительные, при этом т и п не превосходят 106 , ak ≤mn. Обратите внимание на то, что значение тп, а значит, и значение k в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и С#). Формат выходных данных Программа должна вывести одно целое число — максимально возможное количество долек в том прямоугольном куске, который получит Юра. Система оценки Решения, правильно работающие при т ≤ 1000 и n ≤ 1000, будут оцениваться в 60 баллов. Замечание В примере из условия нужно разделить шоколадку 4 × 5 на 4 кусочка. Самый большой кусочек будет состоять из 16 долек, как показано на картинке. Ввод Вывод 4 5 4 16 Код 1 2 3 Код из файла Python 3 ）く 不

Для решения задачи необходимо найти максимальный размер прямоугольного куска шоколадки, который можно получить при делении шоколадки размером t x p на k частей. Давайте проанализируем, как это можно сделать.

Подход к решению

1. Параметры: У нас есть размеры шоколадки t (количество строк) и p (количество столбцов), а также число k (количество кусков, на которые нужно разделить шоколадку).
2. Максимальный размер куска: Нам нужно найти максимальную площадь куска, который можно получить, деля шоколадку на k частей.
3. Проблема разбиения: При разбиении шоколадки, мы можем выделить оптимальный кусок, разделив шоколадку на части. Чем больше кусков, тем меньше может быть максимальный размер куска. Но нам также нужно учесть, что при разбиении на k кусков, максимальный кусок не может превышать т x п // k.
4. Бинарный поиск: Можно использовать бинарный поиск по размеру максимального куска. Проверяем, можем ли мы разбить шоколадку на k кусков так, чтобы кусок имел определённый размер.

Алгоритм

1. Определим границы для бинарного поиска: минимальный размер = 1, максимальный размер = t * p // k.
2. Для каждой длины, которая будет проверяться, проверим, можно ли разбить шоколадку, чтобы куски были не больше этой длины.
3. Для проверки: делим размеры t и p на соответствующие размеры прямоугольного куска и рассчитываем, сколько кусочков мы можем получить.

Код

Вот пример реализации на Python:

def can_split(t, p, k, max_piece_size):
    # Определяем максим количество кусочков для заданного размера max_piece_size
    count = (t // (max_piece_size // p)) * (p // (max_piece_size // t))
    return count >= k

def max_chocolate_piece(t, p, k):
    # Определяем границы для бинарного поиска
    left, right = 1, (t * p) // k
    answer = 0

    while left <= right:
        mid = (left + right) // 2
        if can_split(t, p, k, mid):
            answer = mid  # mid – это возможный максимальный размер
            left = mid + 1
        else:
            right = mid - 1
    
    return answer

# Ввод данных
t = int(input())
p = int(input())
k = int(input())

# Вывод результата
print(max_chocolate_piece(t, p, k))

Объяснение кода

1. Функция can_split проверяет, можем ли мы разбить шоколадку так, чтобы каждый кусок был не больше max_piece_size.
2. max_chocolate_piece использует бинарный поиск для нахождения максимального размера куска.
3. Ввод данных осуществляется через стандартный ввод, что позволяет легко тестировать программу.

Этот код должен быть эффективным и удовлетворять ограничениям задачи, даже для максимальных значений.