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

Объяснение формулы

Каждый раз, когда мы прибавляем [latex]d[/latex], мы увеличиваем количество повторений [latex]d[/latex] на [latex]1[/latex]. Пусть [latex]n[/latex] количество повторений [latex]d[/latex], тогда [latex]k=\frac{n\cdot d}{d}[/latex] целое число, равное [latex]n[/latex]. Отдельно рассмотрим случай деления нацело, а для остальных мы установим два требования:

  1. Полученное число должно быть больше либо равно числу, целая часть которого больше на [latex]1[/latex], чем целая часть изначального числа.
  2. Полученное число должно быть строго меньше числа, целая часть которого больше на [latex]2[/latex], чем целая часть изначального числа.

Рассмотрим числители дробей

Отдельно случай, когда делится нацело: [latex]k[/latex] равно [latex]n\cdot d[/latex], [latex]n[/latex] принадлежит [latex]0[/latex] и натуральным, тогда, прибавляя [latex]d-1[/latex], мы получаем [latex]n\cdot d+d-1=\left(n+1\right)\cdot d-1[/latex] что меньше, чем [latex]\left(n+1\right)\cdot d[/latex] следовательно полученное в итоге число не изменится.

Для нецелых чисел:

Числитель может принимать значения [latex]k=d\cdot n+1…d\cdot n+d-1[/latex]. Если [latex]n\cdot d+1 + d-1[/latex] будет больше либо равно [latex]\left(n+1\right)\cdot d[/latex], то [latex]n\cdot d+2 + d-1…n\cdot d+d-1 + d-1[/latex] также будут больше либо равны [latex]\left(n+1\right)\cdot d[/latex]. Возьмем [latex]k=n\cdot d+1[/latex], тогда, прибавив [latex]d-1[/latex], получится [latex]n\cdot d+1+d-1[/latex] больше либо равно [latex]\left(n+1\right)\cdot d[/latex], значит первое требование выполняется

Eсли [latex]k=n\cdot d + d-1 + d-1[/latex] будет строго меньше [latex]\left(n+2\right)\cdot d[/latex], то [latex]n\cdot d + d-2 + d-1…n\cdot d + 1+ d-1[/latex] также будут строго меньше [latex]\left(n+2\right)\cdot d[/latex]. Возьмем [latex]k=n\cdot d+ d-1[/latex], тогда, прибавив [latex]d-1[/latex], получится [latex]n\cdot d+d-1+d-1=n\cdot d+2\cdot d-2=\left(n+2\right)\cdot d-2[/latex] строго меньше [latex]\left(n+2\right)\cdot d[/latex], значит второе требование также выполняется

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