Как решить: У Маши есть шоколадка, состоящая из m×n квадратных долек?

Деление шоколадки

Ограничение по времени: 1 секунда

Ограничение по памяти: 256 мегабайт

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

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

Формат входных данных

Программа получает на вход три натуральных числа, каждое в отдельной строке: m, n и k. Все числа целые положительные, при этом m и n не превосходят 106, а k≤mn.

Обратите внимание на то, что значение mn, а значит, и значение k в этой задаче может превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Формат выходных данных

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

Система оценки

Решения, правильно работающие при m≤1000 и n≤1000, будут оцениваться в 60 баллов.

Замечание

В примере из условия нужно разделить шоколадку 4×5 на 4 кусочка. Самый большой кусочек будет состоять из 16 долек, как показано на картинке.

Ввод

4

5

4

Вывод

16

тэги:

информатика

категория:

образование

ответить

комментировать

бонус

1 ответ:

старые выше
новые выше
по рейтингу

0

FameM­yname
[-2]

2 месяца назад 

n = int(input())

m = int(input())

k = int(input())

n, m = (reversed(sorted([n, m])))

i = 1

j = max([j for j in range(1, m + 1) if i * j + k <= n * m + 1])

ans = i * j

flag = True

while i + j:

if flag:

i += 1

flag = False

else:

j -= 1

if i > n or j <= 0:

break

if i * j + k <= n * m + 1:

flag = True

if ans + k < i * j + k:

ans = i * j

print(ans)

Источник: bolshoyvopros.ru