У Маши есть прямоугольная шоколадка, состоящая из m×nm×n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки.

Question

Вопрос. Полная версия

Деление шоколадки
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
У Маши есть прямоугольная шоколадка, состоящая из m×nm×n квадратных долек. Маша хочет разделить эту шоколадку между своими друзьями, разломив шоколадку по линиям на k кусочков, то есть каждому другу достанется прямоугольный кусочек шоколадки.
У Юры сегодня день рождения, поэтому Маша хочет разделить шоколадку так, чтобы Юре достался самый большой кусок (содержащий как можно больше долек). Определите число долек в этом куске.

Формат входных данных
Программа получает на вход три натуральных числа, каждое в отдельной строке: m, n и k. Все числа целые положительные, при этом mm и nn не превосходят 106, а k≤mn.
Обратите внимание на то, что значение mnmn, а значит, и значение k в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат выходных данных
Программа должна вывести одно целое число максимально возможное количество долек в том прямоугольном куске, который получит Юра.
Система оценки
Решения, правильно работающие при m≤1000 и n≤1000, будут оцениваться в 60 баллов.
Замечание
В примере из условия нужно разделить шоколадку 4×5 на 4 кусочка. Самый большой кусочек будет состоять из 16 долек, как показано на картинке.
Ввод
4
5
4
Вывод
16

Ответы

Answer 1

# Read input
m, n, k = map(int, input().split())

# Calculate the maximum number of squares in the largest piece
max_squares = min(m, n) * k // (m + n — 1)

# Print the result
print(max_squares)

Answer 2

Чтобы решить эту задачу, мы можем использовать следующий алгоритм:

Ввести три числа m, n и k, представляющие размеры шоколадки и количество кусков.
Рассчитать максимально возможное количество долек в куске, который получит Юра.

Формат входных данных: m = int(input()) n = int(input()) k = int(input())

Алгоритм решения: def calculate_max_pieces(m, n, k): max_pieces = 0 for i in range(1, m + 1): for j in range(1, n + 1): if i * j <= k: if i * j * (m // i) * (n // j) > max_pieces: max_pieces = i * j * (m // i) * (n // j) return max_pieces

print(calculate_max_pieces(m, n, k))

Эта функция возвращает максимально возможное количество долек в куске, который получит Юра.