Задача
Кар Карыч с Пином восемнадцать часов подряд распивали холодные молочные коктейли и закусывали их мороженым. После этого Кар Карыч свалился со страшной простудой, а Пин решил провести в домик своему другу центральное отопление. Расчет количества отопительных приборов необходимо производить строго по ГОСТу 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 11 12 13 14 15 16 17 18 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) throws java.lang.Exception { long a, b, c, d, v; Scanner in = new Scanner (System.in); a=in.nextLong(); b=in.nextLong(); c=in.nextLong(); d=in.nextLong(); v = a * b * c; System.out.println(( v + d - 1 ) / d); } } |
Алгортм решения
- Находим объём комнаты по заданным сторонам по формуле [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].