Модуль: (Python) Целочисленная арифметика - формула округления вверх


Задача

1 /6


Формула округления вверх

Теория Нажмите, чтобы прочитать/скрыть


Формула округления вверх

Разберем способ, который позволит выполнить целочисленное деление с округлением вверх, используя только арифметические операции (округление вверх означает округление до ближайшего целого числа не меньшего результата). 

Представьте, что у нас есть 25 тетрадей, и мы хотим упаковать их в коробки, в каждую из которых помещается не более 10 тетрадей. Сколько коробок нам понадобится?


Для того, чтобы рассчитать количество коробок, необходимо результат деления округлить до целого числа, не меньшего полученного результата. Другими словами, если при делении мы получаем нецелое число, то результатом будет целое число большее нашего. 
Если написать формулой расчет для нашего примера, то получим следующее выражение (скобки \(\lceil ... \rceil \) означают округление вверх результата выражения, записанного вместо ... ): 

\( \text{Количество коробок} = \lceil \frac{25}{10} \rceil = \lceil 2.5 \rceil = 3\)

В итоге, нам потребуется 3 коробки для упаковки 25 тетрадей.

Формула округления вверх (⌈x⌉) в данном случае помогает нам учесть, что если число тетрадей не делится ровно на 10, то нам всё равно нужна дополнительная коробка для оставшихся тетрадей.
 
Целочисленное деление с округлением вверх  можно записать следующей формулой:  \(\lceil \frac{a}{b} \rceil = (a + b - 1) // b\)


Почему эта формула округляет число вверх?

  1. Если a делится на b, то добавление к числу a числа (b-1) не изменит результата. Все равно число округлится до меньшего целого (в С++ произойдет отбрасывание дробной части).

  2. Если a не делится на b, то добавление к числу a числа (b-1) увеличит результат на 1 и мы получим число на 1 больше, чем при целочисленном делении.

Если у нас есть 25 тетрадей, и мы упаковывем их по 10 в коробку, то количество коробок равно: \((25+10-1)//10=34//10=3\).

Если у нас 25 тетрадей, и мы упаковываем их по 5 в коробку, то количество коробок равно: \((25+5-1)//5=29//5=5\).

Данные рассуждения справедливы для положительных a и b. Подумайте, справедливы ли эти рассуждения для отрицательных чисел?


Примечание
В языке программирования Python есть еще один способ округлить вверх. Он работает из-за особенностей целочисленного деления на Python. 

\(\lceil \frac{a}{b} \rceil = -(-a // b)\)

Попробуйте сами проанализировать, почему данная формула работает.

Задача

От организаторов олимпиады поступил заказ на покупку N пачек бумаги "Снегурочка". Магазин упаковывает бумагу по M пачек бумаги в одну коробку. Последняя коробка может быть неполной. Определите, какое количество пачек бумаги будет в последней коробке. 

Формат входных данных
В первой строке входных данных записано натуральное число N - количество пачек, которые были заказаны. Во второй строке - натуральное число M - максимальное число пачек, которое помещается в одну коробку.

Формат выходных данных
Выведите одно число - ответ на задачу
Примеры
Входные данныеВыходные данные
1 25
10
5

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
Python790
Комментарий учителя