Задача 5. Обои и дипломы
ответОграничение по времени: 0.5 секунд
Родители Андрея решили поклеить на одну из стен в его комнате новые обои. Высота стены — n сантиметров, а ширина — m сантиметров. К сожалению, обои, выбранные родителями, Андрею не понравились, и он решил их чем-нибудь закрыть. Так как он участвовал в большом количестве олимпиад, у него накопилось много дипломов. Все дипломы у Андрея одинаковые — это прямоугольники высотой a сантиметров и шириной b сантиметров. Помогите Андрею узнать, сколько квадратных сантиметров обоев он сможет завесить дипломами, если не будет их разрезать и переворачивать. Все дипломы должны целиком размещаться внутри стены и не накладываться друг на друга.
Формат входных данных
В первой строке входных данных находится целое число n (1 ≤ n ≤ 2·109) — высота стены.
Во второй строке находится целое число m (1 ≤ m ≤ 2·109) — ширина стены.
В третьей строке находится целое число a (1 ≤ a ≤ 2·109) — высота диплома.
В четвёртой строке находится целое число b (1 ≤ b ≤ 2·109) — ширина диплома.
Формат выходных данных
Выведите одно целое число — площадь части стены, которая будет закрыта дипломами, если их не поворачивать, не обрезать и не накладывать друг на друга.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в С и С++, тип long в Java и C#).
Система оценки
Решения, правильно работающие при 1 ≤ n, m ≤ 104, будут оцениваться в 50 баллов.
Решения, правильно работающие при n < 2·a и m < 2·b, будут оцениваться в 15 баллов.
Пример
| стандартный ввод | стандартный вывод |
|---|---|
| 3 5 1 2 | 12 |
Замечание
В примере из условия можно разместить 6 дипломов, суммарная площадь которых равна 12 квадратным сантиметрам. Большее число дипломов разместить нельзя, они будут вылезать за границы стены.
Ответ на Задачу 5.
Чтобы заполнить как можно большую площадь стены дипломами, Андрею нужно выкладывать их вплотную друг к другу, начиная с самого края стены, до тех пор, пока это возможно.
Для решения на 15 баллов Андрей может положить всего один диплом — ответом будет a * b.
Для решения на 50 баллов можно смоделировать размещение дипломов на стене — прибавлять в переменную ширину диплома, пока она не превысит ширину стены, аналогично и с высотой.
Для полного решения необходимо вывести формулу. Чтобы закрыть стену дипломами полностью, например, в ширину, нужно, чтобы ширина стены делилась на ширину диплома. Если же она не делится, то остаток закрыть не получится. Таким образом, можно просто вычесть из размеров стены остатки от деления высоты стены n на высоту диплома a и ширины стены m на ширину диплома b и перемножить получившиеся результаты.
Пример решения на языке Python:
n = int(input()) m = int(input()) a = int(input()) b = int(input()) print((n - n % a) * (m - m % b))
