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

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

Условие

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

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

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

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

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

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

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

Ограничения

2 ≤ N, K ≤ 231 − 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 2
3
2
2 3
1

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

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

Условие

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

Например, Вася, получивший в течение четверти оценки 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 баллов.

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

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

Входной файл содержит целое число N — количество учеников, за которым следует N списков оценок. Список оценок i-го ученика состоит из целого числа Qi — количества оценок, за которым следуют Qi целых чисел в диапазоне от 1 до 5 — сами оценки.

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

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

Ограничения

1 ≤ N ≤ 100; 1 ≤ Q ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1
6 2 2 2 2 2 2
0
2
2
6 3 4 2 3 3 5
4 4 5 4 5
1

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

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

Условие

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

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

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

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

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

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

Ограничения

3 ≤ N ≤ 103

0 ≤ xi, yi ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
5 5  5 4  10 4
1 2 3

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

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

Условие

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

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

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

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

Входной файл содержит целые числа N M, за которыми следуют N чисел ai — жажда i-го ученика.

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

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

Ограничения

1 ≤ N, M ≤ 105

0 ≤ ai ≤ 109

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 3
9 30
0
2
4 3
0 101 5 12
7

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

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ DC ≤ 31, 1 ≤ MC ≤ 12, 1600 ≤ YC ≤ 9999

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 10 2010
10 10 2010
2
29 10 2010
1 11 2010
3
8 4 6579
9 7 6579

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

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

Условие

При выпуске нового сорта конфет на некоторой фабрике было проведено исследование рынка с целью определения их оптимальной цены. Оказалось, что эта оптимальная цена контрольной партии из 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 ≤ 231 − 1

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

Входной файл (input.txt) Выходной файл (output.txt)
1
27 6
1 1
2
15 760
19 3

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

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

Условие

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

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

+95238
276
9541014

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

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

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

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

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

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

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

Ограничения

0 ≤ A ≤ 101000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
23
12
2
123
52

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

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

Условие

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

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

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

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 230

1 ≤ X < Y ≤ N

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 2 5
1 2  5 6
1 3  5 5
1 5
2
21 9 15
9 10  15 16
9 11  13 15
9 13

0.549s 0.013s 27