Задача A. Посекундная тарификация ≡

Условие

Телефонная компания ввела новый тарифный план "Посекундный". Согласно этому плану, каждый месяц абоненту предоставляется F бесплатных минут. При этом длительности звонков, использующих только бесплатные минуты, округляются вверх до целой минуты. Например, звонок продолжительностью 3 минуты 15 секунд использует 4 бесплатных минуты.

Когда бесплатные минуты исчерпаны (даже если это произошло в середине звонка), включается посекундная тарификация — 1 рубль в секунду.

История звонков абонента представляет собой список из N пар чисел m s, где m — число минут, s — число секунд. Напишите программу, которая по истории звонков абонента за месяц определяет, сколько рублей ему придётся заплатить.

В первом примере первый и второй звонок тратят по 1 бесплатной минуте, третий звонок тратит 4 бесплатных минуты. На последний звонок остаётся 4 бесплатных минуты. После их исчерпания абонент оплачивает 12 секунд.

Рекомендуется рассмотреть частичные решения

1. F = 0;
2. N ≤ 1.

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

Входного файла содержит целые числа N F, за которыми следует N пар целых чисел m_i s_i.

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

Выходной файл должен содержать единственное целое число — общие затраты абонента за месяц.

Ограничения

0 ≤ N, F ≤ 1000, 0 ≤ s_i ≤ 59, 0 ≤ m_i ≤ 1000.

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

4 10
1 0
0 5
3 40
4 12

12

2 5
6 40
70 11

4311

Задача B. Топография ≡

Условие

Юный топограф Вася тренируется в рисовании карт местности. Вася отметил на карте вокруг своей школы четыре точки A, B, C, D, образующие выпуклый четырёхугольник, и тщательно измерил расстояния AC, AD, BC и BD. Измерить расстояние CD ему помешало здание школы.

Напишите программу, принимающую на вход измеренные Васей расстояния, и вычисляющую минимальную и максимальную возможную длину отрезка CD. Все расстояния измеряются в целых сантиметрах.

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

Входной файл содержит целые числа AC AD BC BD.

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

Выходной файл должен содержать два целых числа — минимальное и максимальное возможные расстояния CD. Если подходящих целочисленных значений расстояния CD не существует, выведите единственное число  − 1.

Ограничения

1 ≤ AC, AD, BC, BD ≤ 10⁹

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

3 5 6 3

4 7

3 2 50 60

-1

Задача C. Гаджет в кредит ≡

Условие

Студент Вася решил приобрести себе новый гаджет. Стипендия у Васи небольшая, а гаджет — дорогой, поэтому Вася решил купить гаджет в кредит.

В магазине Васе объяснили правила предоставления кредита.

• Первоначально сумма долга равна стоимости гаджета C.
• По истечении максимум N лет вся сумма долга должна быть выплачена
• Вася должен определить ежемесячный платеж M — целое число рублей, которое он будет выплачивать каждый месяц. Исключение может составлять последний платёж — оставшаяся на последний месяц сумма долга может оказаться меньше M.
• Каждый месяц после Васиного платежа оставшаяся сумма долга увеличивается на P процентов и округляется вверх до целого числа.

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

Рекомендуется рассмотреть частичные решения

1. P = 0
2. C, P ≤ 10³

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

Входной файла содержит целые числа N P C.

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

Выходной файл должен содержать единственное целое число — подходящий Васе ежемесячный платеж.

Ограничения

1 ≤ C ≤ 10⁹; 0 ≤ P ≤ 10⁹; 1 ≤ N ≤ 10⁴

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

1 0 1

1

1 124 12

8

1 1 12

2

Задача D. Крейзик ≡

Условие

Юный программист Вася придумал собственный язык программирования "Крейзик". Васе всегда не нравились правила вычисления арифметических выражений, поэтому он решил, что в Крейзике все арифметические операции будут выполняться строго слева направо, а скобок не будет вообще.

Кроме того, обычные четыре арифметических действия Вася заменил на четыре своих:

• Сцепление (обозначается символом +) — результат получается путём записи сначала всех цифр первого аргумента, а затем всех цифр второго.
• Выметание (обозначается символом -) — результат получается записью всех цифр первого аргумента, отсутствующих во втором. Если ни одной такой цифры не нашлось, результат равен 0.
• Окружение (обозначается символом *) — результат получается циклическим сдвигом первого аргумента влево столько раз, какова величина второго аргумента.
• Дробление (обозначается символом /) — результат получается записью цифр первого и второго аргумента по очереди, пока один или оба аргумента не закончатся, и затем оставшихся цифр более длинного аргумента.

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

Отправка решения и тестирование

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

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

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

Первая строка входного файла содержит целое число N — количество выражений. Последующие N строк содержат по одному выражению каждая.

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

Выходной файл должен содержать N строк — результаты вычисления каждого выражения.

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

5
2+3
57578-255
12304*8
11111/222
1+2/44*5-20

23
778
4123
12121211
441

Задача E. Доклад с картинками ≡

Условие

Школьник Вася приготовил доклад по географии, затратив минимальное количество усилий. Доклад у него получился вообще без текста и содержит лишь n картинок, скачанных из интернета. Тем не менее, Вася хочет представить свою работу в наилучшем свете. Для этого он пытается расположить картинки в таком порядке, чтобы доклад занял как можно больше страниц.

Текстовый процессор, который использует Вася, работает следующим образом. Каждая страница имеет высоту k сантиметров. Картинки располагаются одна за другой, начиная с первой страницы. Если очередная картинка не входит на текущую страницу целиком, то текстовый процессор переходит на следующую страницу.

Зная высоту каждой картинки в сантиметрах h_i, определите порядок следования картинок, при котором полученный документ будет иметь наибольшее количество страниц.

В тестовом примере имеется 4 картинки с высотами 6 см, 4 см, 6 см и 4 см. Высота страницы составляет 10 см. Одно из оптимальных решений — расположить картинки в следующем порядке: 4, 4, 6, 6. Тогда первые две картинки окажутся на первой странице, а оставшиеся две картинки займут по одной странице каждая. Таким образом, весь доклад займёт 3 страницы.

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

Входной файл содержит два целых числа — n k, за которыми следуют n целых чисел — h₁… h_n.

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

Выходной файл должен содержать n целых чисел — высоты картинок в оптимальном порядке. Если имеется несколько оптимальных ответов, выведите любой из них.

Ограничения

1 ≤ n ≤ 15;

1 ≤ k ≤ 10⁸;

1 ≤ h_i ≤ k;

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

4 10
4 6 4 6

4 4 6 6