e-olymp 219. Центральное отопление

Задача

Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 800333-90-06*. Для простоты Пин решил купить простые батареи. Согласно таблице 14.1.3 этого ГОСТа, каждая батарея обогревает определённый объём воздуха — ровно [latex]d[/latex] кубометров. Комната, которую собирается для своего друга обогреть Пин, имеет следующие размеры:

• высота [latex]a[/latex],

• ширина [latex]b[/latex],

• длина [latex]c[/latex].

Определите минимальное количество батарей, которое необходимо купить Пину. Учтите только, что если в домике у Кар Карыча температура будет ниже, чем по ГОСТу, Кар Карыч никогда не поправится.

Входные данные

Четыре целых числа [latex]a, b, c, d (a, b, c \leq 10^{5}, d \leq 2 \cdot 10^{9})[/latex].

Выходные данные

Выведите минимальное количество батарей, которое необходимо купить Пину.

Тесты

# Входные данные Выходные данные
1 2 3 4 2 12
2 4 5 7 3 47
3 75 61 88 50 8052
4 986 764 390 54 5440529
5 1 1 1 2000000 1

Алгортм решения

  1. Находим объём комнаты по заданным сторонам по формуле [latex]V=a \cdot b \cdot c[/latex].
  2. Делим полученный объём на объём, обогреваемый одной батареей.
  3. Округляем при необходимости полученный ответ вверх, чтобы найти минимальное количество батарей.

Округление

Если разделить объём [latex]V[/latex] на [latex]d[/latex] нацело, то в остатке у нас может получиться [latex]0, 1, 2, \ldots , d-1[/latex]. Добавив [latex]d-1[/latex] к объёму [latex]V[/latex] мы получим в делении нацело остатки [latex]d-1, d, d+1, \ldots , 2d-2[/latex]. Первое число [latex]d-1<d[/latex], поэтому при делении нацело оно даёт [latex]0[/latex]. Остальные числа больше либо равны [latex]d[/latex], но меньше [latex]2d[/latex], значит любое из них при делении нацело на [latex]d[/latex] даст [latex]1[/latex].

Условие задачи можно найти на e-olymp
Код решения — ideone

2 thoughts on “e-olymp 219. Центральное отопление

  1. Сделайте правильные отступы в коде.
    У вас довольно непонятно приводиться объяснение формулы, даже сказала бы, что это не объяснение, а «запутывание». Попробуйте написать понятнее.

    • Дополню:
      — cmath не используется, зачем его включать?
      — В коде Вы вычисляете объём комнаты, а в пояснении этого нет. Потом в коде делите объём комнаты на объём обогреваемый одной батареей и ни слова об этом. Надо про это написать в самом начале. А потом уже перейти к объяснению как избавиться от округления.
      — Про округление. Вы очень хорошо придумали как обойтись целочисленным делением без округления и ветвления. Молодец. Мне очень понравилось. Добавив $d-1$ к делимому при целочисленном делении на $d$ Вы действительно получите округление вверх. Вы попытались это объяснить не очень удачно. Кажется Вы имели в виду, что если разделить объём $V$ на $d$ нацело, то в остатке могут получиться числа $0, 1, 2, \ldots, d-1.$ Вы придумали добавить $d-1$. Такое увеличение превратит остатки в $d-1, d, d+1, \ldots, 2d-2.$ Поскольку первое число $d-1<d,$ при делении нацело на $d$ оно дает $0$. Остальные числа больше либо равны $d$ но меньше чем $2d.$ Значит при делении нацело на $d$ для любого из них получится $1$. Вот и вышло округление вверх.

Добавить комментарий