Задача B. Доставка почты ≡

Условие

Почтальон Пётр привёз посылки для жителей 108 дома. В этом доме всего один подъезд, N этажей и отсутствует лифт.

Так совпало, что именно сегодня на каждый этаж необходимо доставить по одной посылке. Почтальон хочет сделать работу как можно быстрее, поэтому берёт всегда как можно больше посылок, но не более чем M штук — тяжелые они, однако.

Пётр не привык выбирать, какие посылки доставлять в первую очередь, поэтому берёт их случайно. Взяв посылки, он доставляет их в порядке возрастания этажей. Например, если почтальон взял посылки для 2, 5 и 10 этажа, то сначала он доставит посылку на 2-й этаж, потом на 5-й, потом на 10-й. После этого он возвращается в свой грузовик за новой партией. И так до тех пор, пока не будут доставлены все посылки.

Подъёмом называется суммарное количество этажей, на которое необходимо подняться, доставляя посылки. Например, если почтальон доставляет посылки на 1 и 3 этажи, а потом на 2, то сначала он поднимется на 1-й этаж, потом поднимется с 1-о этажа на 3-й, потом вернётся в грузовик за посылкой для 2-о этажа и доставит её. Подъём в данном случае будет равен 1 + (3 − 1) + 2 = 5.

Разумеется, от порядка доставки зависит величина подъёма. Пётр хочет узнать минимальное или максимальное возможное значение подъёма.

Требуется написать программу, которая определит минимальное или максимальное возможное значение подъёма, если известны количество этажей в доме и количество посылок, которые почтальон может унести.

Формат входных данных

Первая строка содержит одно целое число N — количество этажей в доме.

Вторая строка содержит одно целое число M — количество посылок, которые почтальон может унести за один раз.

Третья строка содержит одно целое число P. Если P = 1, то необходимо посчитать минимальное значение подъёма. Иначе P = 2 и необходимо посчитать максимальное значение подъёма.

Формат выходных данных

В единственной строке выведите ответ на задачу.

Ограничения

1 ≤ M ≤ N ≤ 2 ⋅ 10⁹

1 ≤ P ≤ 2

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

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

Пояснение к примерам

Обратите внимание, что первый и третий примеры относится к первой подзадаче, а второй и четвёртый — к четвёртой.

В первом примере Пётр мог сначала доставить посылки на 2-й и 3-й этажи, а потом на 1-й. Подъём равен 2 + (3 − 2) + 1 = 4.

Во втором примере Пётр мог сначала доставить посылки на 1-й и 2-й этажи, а потом на 3-й. Подъём равен 1 + (2 − 1) + 3 = 5.

Примеры тестов

3
2
1

4

3
2
2

5

7
3
1

12

7
3
2

18

Разбор

Полное решение

Почтальону потребуется сделать K = N / M, округлённое вверх, заходов в дом, чтобы доставить все посылки.

Понятно, что значение подъёма может складываться из наибольших номеров этажей в заходах почтальона. Определим, какими могут быть эти номера.

Предположим, что в очередном заходе почтальон доставлял одну посылку на максимальный по номеру этаж, а остальные — на минимальный. То есть в первом заходе почтальон доставил посылки на N, 1, 2, ..., M − 1 этажи. Во втором: N − 1, M, M + 1, ..., 2 ⋅ M − 2 этажи, и т.д. Тогда значение подъёма будет равным N + (N − 1) + ...  + (N − K + 1). Получить значение подъёма больше этого не получится, так как в каждом из заходов присутствует один из K наибольших этажей.

Предположим, что в очередном заходе почтальон доставлял все посылки на максимальные по номеру этажи. То есть в первом заходе почтальон доставил посылки на N, N − 1, ..., N − M + 1 этажи. Во втором: N − M, N − M − 1, ..., N − 2 ⋅ M + 1 этажи, и т.д. Тогда значение подъёма будет равным N + (N − M) + (N − 2 ⋅ M) + ...  + (N − (K − 1) ⋅ M). Получить значение подъёма меньше этого не получится: если в двух заходах поменять местами две любые посылки, то в одном заходе номер максимального этажа не изменится, а в другом станет больше.

Можно заметить, что и первая, и вторая суммы являются суммами арифметических прогрессий, а значит, их значения можно быстро вычислить с помощью формулы: sum = (first + last) ⋅ cnt / 2, где first — первый элемент прогрессии, last — последний элемент, cnt — количество элементов в прогрессии.

Стоит отметить, что значение подъёма может быть очень большим, поэтому следует использовать 64-х битный тип данных. Решения, не учитывающие данную особенность, могут пройти только первую и четвёртую подзадачи.

Частичные решения

Ограничения первой и четвёртой подзадач позволяют промоделировать работу почтальона: определять в каждом заходе минимальный или максимальный этаж для доставки очередной посылки.

Вторая и пятая подзадачи подразумевают подсчет суммы арифметической прогрессии с помощью цикла.