Задача A. Экономная маршрутизация ≡

Условие

N компьютеров нужно объединить в сеть. Для этого можно использовать маршрутизаторы. Каждый маршрутизатор имеет K "нисходящих" разъемов и один "восходящий" разъем. К каждому нисходящему разъему можно подключить компьютер или другой маршрутизатор. Восходящий разъем служит для подключения маршрутизатора к нисходящему разъему другого маршрутизатора.

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

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

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

Во входном файле находятся два целых числа — N K.

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

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

Ограничения

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

4 2

3

2 3

1

Задача B. Последний урок ≡

Условие

Обычно последний урок в четверти посвящён определению четвертных оценок. Четвертная оценка школьника вычисляется как округлённое до ближайшего целого среднее арифметическое всех его оценок в течение четверти.

Например, Вася, получивший в течение четверти оценки 3, 4, 2, 3, 3, 5, будет иметь среднюю оценку 20 / 6 = 3.3333... и получит итоговую оценку 3.

Средние оценки 1.5, 2.5, 3.5 и 4.5 округляются до 2, 3, 4 и 5 соответственно.

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

Например, если Вася на последнем уроке сумеет получить пятёрку, то его средняя оценка станет равна 25 / 7 = 3.571... и итоговая оценка повысится до 4 баллов.

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

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

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

Ограничения

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

1
6 2 2 2 2 2 2

0

2
6 3 4 2 3 3 5
4 4 5 4 5

1

Задача C. Самый тупой ≡

Условие

Среди данных N точек на плоскости с координатами (x_i, y_i) требуется найти такие три точки A, B и C, что выпуклый (меньший 180°) ∠ ABC будет наибольшим.

Никакие три исходные точки не лежат на одной прямой.

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

Во входном файле содержится число N, за которым следует N пар целых чисел x_i y_i.

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

В выходном файле должно содержаться три целых числа A B C — номера точек, образующих максимальный угол ∠ ABC. Точки нумеруются с 1. Если решений несколько, вывести любое из них.

Ограничения

3 ≤ N ≤ 10³

0 ≤ x_i, y_i ≤ 10⁶

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

3
5 5  5 4  10 4

1 2 3

Задача D. Бутылка на всех ≡

Условие

После урока физкультуры N школьников собрались в магазине, чтобы купить воды. Купив одну бутылку, они задумались: ведь в бутылке всего M глотков воды, а денег на еще одну бутылку у них нет!

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

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

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

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

Ограничения

1 ≤ N, M ≤ 10⁵

0 ≤ a_i ≤ 10⁹

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

2 3
9 30

0

4 3
0 101 5 12

7

Задача E. Вирус 10.10.10 ≡

Условие

В преддверии очередной «красивой» даты —— 10 октября 2010 года —— суеверные пользователи Интернета были встревожены слухами о предстоящих сбоях в работе компьютеров. Особенный вирус, который получил условное название «три десятки» (по записи круглой даты 10.10.10) вызвал активное обсуждение на сайтах и в социальных сетях.

Напомним, что дата записывается в виде число.месяц.год. Существует несколько способов записи даты в данном формате: число и месяц могут быть записаны с лидирующим нулём (если значение не превышает 9), год может быть записан либо полностью, либо в виде последних двух цифр. Например, дата 2 марта 2004 года может быть записана как 02.03.2004, 2.03.04, 02.3.2004 и т.д.

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

Будем считать дату «красивой», если найдётся такой способ записи даты, что после удаления разделяющих точек, получившаяся строка удовлетворяет хотя бы одному из следующих условий:

• строка является палиндромом, т.е. одинакова при чтении слева направо и справа налево, например 7 февраля 2070 — 07.02.2070 или 5 декабря 1915 — 5.12.15
• строка разбивается на подстроки равной длины, равные между собой, например 31 июля 3107 — 31.07.3107 или 9 августа 2898 — 9.8.98 в случае разбиения на две подстроки, 5 июля 5757 — 5.7.5757 в случае разбиения на три подстроки

Требуется написать программу, которая по указанной дате определит ближайшую следующую за ней (включая её саму) «красивую» дату.

Примечание: количество дней в месяцах равно 31, 28 или 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31. Год является високосным, если его номер кратен 4 и при этом не кратен 100 либо кратен 400.

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

Входной файл содержит три целых числа — D_C M_C Y_C, обозначающих дату, где D_C — день, M_C — месяц, Y_C — год.

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

Выходной файл должен содержать три целых числа — D_V M_V Y_V, задающих ближайшую "красивую" дату, где D_V — день, M_V — месяц, Y_V — год.

Ограничения

1 ≤ D_C ≤ 31, 1 ≤ M_C ≤ 12, 1600 ≤ Y_C ≤ 9999

Входная дата корректна, т.е. день месяца не превышает количество дней в данном месяце данного года.

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

10 10 2010

10 10 2010

29 10 2010

1 11 2010

8 4 6579

9 7 6579

Задача F. Конфеты с десятичной точкой ≡

Условие

При выпуске нового сорта конфет на некоторой фабрике было проведено исследование рынка с целью определения их оптимальной цены. Оказалось, что эта оптимальная цена контрольной партии из B конфет составляет A рублей.

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

Кроме того, для подбора размера ценника необходимо определить количество значащих цифр после десятичной точки.

Требуется написать программу, которая, получив на вход количество конфет контрольной партии B и цену партии A, рассчитает минимально возможное количество конфет в коробке C и соответствующее число цифр D.

Например если оказалось, что стоимость 6-ти конфет составляет 27 рублей, то их нужно выпускать в коробках по 1-ой конфете стоимостью 4.5 рубля — значит D = 1. Или если оказалось, что 760 конфет стоят 15 рублей, то их можно выпускать по 19 штук в коробке стоимостью 0.375 рублей — значит D = 3.

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

Входной файл содержит два целых числа A B.

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

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

Ограничения

1 ≤ A, B ≤ 2³¹ − 1

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

27 6

1 1

15 760

19 3

Задача G. Марсианская арифметика: декомпозиция ≡

Условие

Марсианские правила для сложения натуральных чисел отличаются от земных.

• Аргументы записываются в десятичной системе счисления.
• Производится поразрядное сложение цифр справа налево.
• В случае, если сумма цифр превысила 9, разряд переноса не прибавляется к следующему, а вставляется в результат перед текущим разрядом.

Например, сумма 95238 + 276 вычисляется следующим образом:

Дано марсианское число A, требуется написать программу, вычисляющую количество способов разложить A на два неотрицательных слагаемых.

Разложения, отличающиеся порядком различных слагаемых, считаются различными.

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

Входной файл содержит единственное число — A.

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

Выходной файл должен содержать единственное число — количество способов разложить число A на два слагаемых по модулю 10⁸ + 7.

(Иными словами, поскольку ответ может быть большим, следует вывести остаток от его деления на 10⁸ + 7).

Ограничения

0 ≤ A ≤ 10¹⁰⁰⁰

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

23

12

123

52

Задача H. Матрёшки АТЭС ≡

Условие

К моменту проведения саммита АТЭС во Владивостоке было решено изготовить подарочные наборы матрёшек, по N штук в каждом.

Матрёшек в каждом наборе располагают в порядке убывания вместимости и нумеруют от 1 до N. Таким образом самая большая матрёшка получает номер 1, а самая маленькая — N. Для упаковки матрёшек в набор используют следующий алгоритм: за один шаг каждая матрёшка, находящаяся на четной позиции, помещается (вместе со всеми матрёшками внутри) внутрь ближайшей слева матрёшки. Эта операция продолжается до тех пор, пока все матрёшки не будут упакованы в одну.

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

i-ый шаг алгоритма описывается путём указания четырёх чисел X_Li, X_Ri, Y_Li, Y_Ri, обозначающих, что после упаковки матрёшки с номером X_Ri в матрёшку с номером X_Li, матрёшка X оказалась внутри X_Li. Аналогично для матрёшки Y.

Последний шаг алгоритма описывается двумя числами L_F, R_F — после упаковки матрёшки с номером R_F в матрёшку с номером L_F оказалось, что матрёшки X и Y находятся внутри матрёшки L_F.

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

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

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

Выходной файл должен содержать подробный процесс упаковки матрёшек:

• Каждая строка, описывающая один шаг алгоритма, кроме последней, должна содержать четыре целых числа — X_Li, X_Ri, Y_Li, Y_Ri
• Последняя строчка должна содержать два целых числа — L_F, R_F

В случае, когда на каком-либо шаге в матрёшку ничего не упаковывается, указать, что матрёшка помещается сама в себя.

Ограничения

2 ≤ N ≤ 2³⁰

1 ≤ X < Y ≤ N

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

6 2 5

1 2  5 6
1 3  5 5
1 5

21 9 15

9 10  15 16
9 11  13 15
9 13