Задача C. Доставка почты 2

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

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

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

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

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

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

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

Требуется определить минимальное и максимальное возможное значение подъёма для каждого дня, если известны количество этажей в доме и количество посылок, которые почтальон может унести. В качестве решения принимается как программа, так и текстовый файл, содержащий ответы к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Формат входного файла

Первая строка содержит целое число Q — количество рабочих дней у почтальона.

Далее следует Q строк, в каждой из которых записано по два целых числа Ni и Mi — количество этажей в доме и количество посылок, которые почтальон может унести за один раз в i-й рабочий день.

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

Второй пример соответствует тестам, которые будут оцениваться.

Формат выходного файла

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

На каждый тест должен быть дан ответ (иначе есть риск неверной проверки). Если вы не знаете ответ на какой-то тест, то следует написать в выходном файле "0 0" (без кавычек).

Ограничения

1 ≤ Q ≤ 15

1 ≤ Mi ≤ Ni ≤ 200

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

Баллы начисляются пропорционально количеству правильных ответов в выходном файле, причем половина баллов начинается за минимальное значение подъёма, и половина — за максимальное.

По запросу сообщается количество набранных баллов.

Тесты Баллы Способ проверки
1-5По 6 баллов за тестПроверка осуществляется сразу после отправки решения
6-10По 6 баллов за тестПроверка осуществляется только после окончания олимпиады
11-15По 8 баллов за тестПроверка осуществляется только после окончания олимпиады

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

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

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
3 2
7 3
4 5
12 18
2
15
4 1
5 2
7 4
19 2
20 7
10 1
15 8
21 2
33 4
50 9
108 1
101 2
150 4
170 31
200 199
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

0.070s 0.012s 15