Задача
Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 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 2 3 4 5 6 7 8 9 10 |
#include <iostream> using namespace std; int main () { unsigned long long a, b, c, d, v; cin>>a>>b>>c>>d; v = a * b * c; cout<<( v + d - 1 ) / d; return 0; } |
Алгортм решения
- Находим объём комнаты по заданным сторонам по формуле [latex]V=a \cdot b \cdot c[/latex].
- Делим полученный объём на объём, обогреваемый одной батареей.
- Округляем при необходимости полученный ответ вверх, чтобы найти минимальное количество батарей.
Округление
Если разделить объём [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
Сделайте правильные отступы в коде.
У вас довольно непонятно приводиться объяснение формулы, даже сказала бы, что это не объяснение, а «запутывание». Попробуйте написать понятнее.
Дополню:
— 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$. Вот и вышло округление вверх.