| Автор: | А. Усманов | Ограничение времени: | 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 |
|
|