Задача A. Ежеминутные автобусы

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

Условие

На автобусную остановку каждую минуту подходит автобус одного из маршрутов. Диспетчерская служба собрала данные за N минут — номера маршрутов каждого автобуса.

Требуется определить максимально возможное время ожидания для пассажира, желающего уехать определённым маршрутом. Т.е. в данной последовательности номеров маршрутов нужно найти два самых удаленных числа, равных между собой. Например, для последовательности 2, 11, 2, 2, 25, 11, 25, 11 максимальное время ожидания равно 4 — для маршрута номер 11.

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

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

Все числа целые. Каждый номер маршрута встречается не менее двух раз.

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

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

Ограничения

2 ≤ i ≤ 106

1 ≤ ai ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
8
2 11 2 2 25 11 25 11
4
2
4
23 23 41 41
1

Задача B. Судьба математика

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

Условие

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

В городе, где они живут, телефонные номера состоят из 6 цифр от 0 до 9 в любой комбинации (например, 000999 — правильный телефонный номер).

Между цифрами номера возможны 6 видов отношений: >, <, =, <=, >=, <>. Например, 2>5 означает, что вторая цифра в номере больше, чем пятая.

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

В каждой строке входного файла содержится одно отношение, состоящее из двух различных номеров цифр от 1 до 6, между которыми стоит один из знаков >, <, =, <=, >=, <>. Внутри строки пробелов нет.

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

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

Ограничения

Количество отношений находится в диапазоне от 1 до 30.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1&lt;2
3=1
3&gt;4
12000

Задача C. Двойные тетради Чебурашки

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

Условие

Пришла осень, каникулы закончились, и Чебурашке снова нужно идти в школу. Он заранее готовился к этому: накупил карандашей, ручек, тетрадей. Среди покупок, кроме обычных тетрадей, были также и двойные, каждая из которых предназначена сразу для двух предметов.

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

У Чебурашки есть NS одинарных и ND двойных тетрадей. Все одинарные тетради имеют вес WS, а все двойные — вес WD. Чебурашка учится N дней в неделю. Он изучает M предметов, пронумерованных от 1 от M. Вес, который Чебурашке придётся перенести за один день, равен сумме весов всех тетрадей, которые он должен будет взять.

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

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

Во входном файле содержатся числа N M NS ND WS WD. Далее следует расписание, состоящее из N дней. Каждый день описывается одной строкой. В начале строки содержится Ki — число уроков в i-ый день, за которым следует Ki чисел — номера предметов. Все числа во входном файле целые.

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

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

Ограничения

0 ≤ N ≤ 6

0 ≤ M ≤ 10

0 ≤ WS, WD ≤ 109

0 ≤ K1 + K2 + … + KN ≤ 15

2 × ND + NS = M

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

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

Задача D. R2D2

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

Условие

Перед сражением с ситхами Энакен Скайуокер решил протестировать своего дроида R2D2. Для проверки системы передвижения он решил поместить робота на специальную горизонтальную площадку, имеющую форму прямоугольника. Площадка разделена на квадратные клетки со сторонами длины 1. На некоторые клетки можно перемещаться, на некоторые - нет. R2D2 разрешено перемещаться только вверх, вперед, влево, вправо на соседние клетки.

Для первого теста Энакен хочет заставить робота пройти от начальной клетки площадки до конечной всеми возможными способами, проходя через каждую клетку ровно 1 раз. Чтобы заставить робота двигаться, юному джедаю надо записать все траектории, которые следует пройти роботу, в виде последовательностей символов 'l', 'r', 'u', 'd'. Символ 'l' означает, что робот должен перейти в левую соседнюю клетку, 'r', 'u', 'd' - в правую, верхнюю, нижнюю соответственно. Энакену лень записывать таким образом все способы перемещения, и он просит вас написать программу, которая напишет их за него.

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

Первая строка входного файла содержит два целых числа N, M - длины сторон прямоугольника. За ними следует N * M чисел A[i, j], которые равны 0, если в клетку с координатами i, j перемещаться нельзя, или 1 - можно. Первое число задает верхнюю левую клетку (она является начальной), последнее - нижнюю правую(конечная). Гарантируется, что есть хотя бы один путь из начальной клетки в конечную.

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

В выходной файл выведите число C - количество способов перемещения из начальной клетки в конечную, за которым следует C строк - способы перемещения в виде последовательностей символов 'l', 'r', 'u', 'd'. Последовательности можно выводить в любом порядке.

Ограничения

2 ≤ N,M ≤ 5

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 1
1
1
1
d
2
2 2 
1 0
1 1
1 
dr

Задача E. Две кучки

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

Условие

Однажды у Хана Соло и Леи Скайуокер родились двое детей. Когда детям было около года они любили играть с камушками. Тогда Лея и Хан решили собрать им по кучке красивых камней. К обеду они насобирали камней, но надо было распределить их на две кучки так, чтобы дети не поссорились. Для этого камни надо распределить так, чтобы разница между суммарными весами двух кучек была минимальной и надеяться, что дети ее не заметят.

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

В выходном файле содержится целое число N - количество камней. Следующие N чисел Wi - веса каждого камня.

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

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

Ограничения

1 ≤ N ≤ 20 1 ≤ Wi ≤ 100000

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

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

Задача F. Странный переводчик

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

Условие

Однажды Чубакка решил перепрограммировать C-3PO так, чтобы он преобразовывал речь окружающих в речь в стиле магистра Йоды.

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

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

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

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

Выходной файл должен содержать преобразованные предложения, каждое из которых расположено на новой строке.

Ограничения

Длина каждого предложения не превосходит 255. Всего предложений не больше 30.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
you don't_want that_cheeseburger.
you want_to_give your_potatoes to_Yoda.
that_cheeseburger don't_want you.
to_Yoda your_potatoes want_to_give you.


Задача G. Универсальный галактический гороскоп

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

Условие

Летоисчисление на планетах галактического альянса ведется следующим образом: эпоха начинается с момента свершения События. Событие считается мгновенным, и с этого же момента начинается последовательное чередование знаков зодиака, которых P штук. Определенных имен у знаков нет, поэтому они обозначаются просто порядковыми номерами начиная с единицы.

Год состоит из M месяцев, каждый месяц состоит из D дней. Количество лет, месяцев и дней в записи даты означает количество полных прошедших, соответственно, лет, месяцев и дней. Событие имело место в нулевом дне нулевого месяца нулевого года (0.0.0), и, например, спустя два с половиной дня дата будет 2.0.0. Таким образом, если дата рождения галактического жителя 5.0.0, то есть через пять полных дней с момента События, то считается, что он родился уже в течение шестого дня.

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

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

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

Входной файл содержит целые положительные числа N, M, D, K, P, после которых идут N дат дней рождения галактических жителей в формате DAYS.MONTHS.YEARS.

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

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

Ограничения

1 ≤ N, M, D, K, P ≤ 1000

0 ≤ DAYS < D; 0 ≤ MONTHS < M; 0 ≤ YEARS ≤ 999

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5 2 2 1 4
0.0.0
1.0.0
0.1.0
1.1.0
0.0.1
1 2 3 4 1
2
3 2 5 1 3
4.0.133
1.1.77
3.1.44
2 0 3

Problem H. Judging tires

Author:A. Zhuplev   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

According to ISO stadnard Metric tire code, tire dimensions are described by a string of letters and numbers in the following format:

Rules of ACM (Any Car Modification) race specify a fixed tire dimensions for all participating cars. Young racer Vasya has not been able to find this type of tire. However, his car will still be approved for the race by judges only if radius of the wheel (wheel disk radius plus sidewall height) differs by at most K percent from that of the specified tire.

Note: 1 inch = 25.4 millimeters. Number a differs from b by at most c percent when 100 × |a − b| / b ≤ c.

Input file format

First line of input file contains integer K.

Second and third lines contain Metric tire codes of specified tire and Vasya's tire respectively. Tire codes contain only digits, R and slash (ASCII 47) characters.

Output file format

Output file must contain a single string — APPROVED if Vasya's car is approved to the race or DISAPPROVED otherwise.

Constraints

0 ≤ K ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2
195/65R15
205/55R15
DISAPPROVED
2
1
195/65R15
185/070R15
APPROVED

Задача I. Реформа галактических вооруженных сил

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

Условие

Армия галактического альянса состоит из 2 N дивизионов боевых дроидов. Верховное командование приняло решение сократить количество дивизионов вдвое, объединив их попарно. Объединение двух дивизионов происходит следующим образом: каждый из дивизион разбивается на одинаковое количество Ki отрядов дроидов, после чего отряды сливаются и формируют Ki увеличенных отрядов, составляющих новый объединенный дивизион.

Программное обеспечение дроидов поддерживает разбиение дивизиона дроидов только на равные по количеству отряды. Например, дивизион из 6 дроидов может быть разбит на 1 отряд из 6 дроидов, 2 отряда из 3 дроидов, 3 отряда из 2 дроидов или 6 отрядов из 1 дроида.

Считается, что после объединения двух дивизионов, максимальную эффективность в бою имеет объединенный дивизион с наибольшим количеством отрядов. Например, максимально эффективный способ объединить два дивизиона, состоящие из из 6 и 4 дроидов — это разбить каждый на два отряда по 3 и 2 дроида, соответственно. Затем сформировать два увеличенных отряда по 5 дроидов. Новый объединенный дивизион будет состоять из 10 дроидов, состоящих в 2 отрядах.

Рассмотрим армию, состоящую из 4 дивизионов: 4 9 3 6. Возможные варианты разбиения дивизионов на равные по численности отряды: 1 дивизион: 1 по 4, 2 по 2, 4 по 1. 2 дивизион: 1 по 9, 3 по 3, 9 по 1. 3 дивизион: 1 по 3, 3 по 1. 4 дивизион: 1 по 6, 2 по 3, 6 по 1.

Соответственно, оптимальным решением будет объединение дивизионом 1 и 4 с разбиением на 2 отряда каждого, а также дивизионов 2 и 3 с разбиением на 3 отряда каждого. Общее количество отрядов в армии после объединения — 5.

Требуется данные 2 N дивизионов дроидов попарно объединить таким образом, чтобы общее количество отрядов в армии было максимальным.

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

Входной файл содержит целое положительно число N, за которым следуют 2 N целых положительных чисел Di — количество дроидов в i-ом дивизионе.

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

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

Ограничения

1 ≤ N ≤ 10; 1 ≤ Di ≤ 109

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

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

Задача J. Зельеварение

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

Условие

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

Вася сварил N таких зелий, i-е зелье увеличивает температуру окружающей среды на целое число ai градусов. Каждое зелье он налил в отдельную колбу, чтобы зелья начали испаряться. Все колбы одинаковы. Эффекты от паров зелий в разных колбах складываются. Колбы Вася выставил в ряд и начал наблюдать за изменением температуры в комнате.

К сожалению, температура в комнате очень быстро стала некомфортной. И тут Вася подумал, почему бы не сделать температуру воздуха в комнате равной T0 + K, где T0 — температура в комнате до приготовления зелий. Он тут же вспомнил, что на уроках заклинаний он недавно научился заклинанию исчезновения! Заклинание позволяет ему безвозвратно уничтожить любой непрерывный отрезок подряд идущих колб вместе с их влиянием на температуру воздуха в комнате. Используя только это заклинание, Вася хочет сделать температуру в комнате желаемой.

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

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

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

Первая строка входного файла содержит два целых числа N K —– количество колб с зельями и температура, на которую Вася хочет изменить исходную в комнате.

Вторая строка содержит N целых чисел, i-е число — количество градусов, на которое увеличится температура окружающей среды из-за паров i-ой колбы.

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

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

Ограничения

1 ≤ N ≤ 2 ⋅ 103

107 ≤ K ≤ 107

104 ≤ ai ≤ 104

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

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

Задача K. Breadth First Search

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

Условие

Требуется написать программу, которая получает невзвешенный неориентированный граф и выводит все его вершины в порядке увеличения расстояния от данной вершины S. Расстояние между вершинами A и B это длина кратчайшего пути из A в B. Если есть несколько вершин, находящихся на одном и том же расстоянии от вершины S, выведите их в произвольном порядке.

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

Входной файл содержит три целых числа N, M и S, где M — число рёбер, S — номер стартовой вершины. Вершины пронумерованы целыми числами от 1 до N. Каждая из следующих M строк содержит пару целых чисел — номера вершин, соединённых ребром.

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

Выходной файл должен содержать последовательность из N номеров вершин, упорядоченных по возрастанию расстояния от S. Если какая-то из вершин недостижима из S, выведите единственное число 1.

Ограничения

0 ≤ N, M ≤ 100000

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

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

Задача L. Интернет по ЛЭП

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

Условие

Один из интернет-провайдеров решил опробовать новую технологию — передачу данных по линиям электропередач. Для этого на подстанциях были установлены N ретрансляторов.

Рассмотрим i-й ретранслятор и провод от него к другому ретранслятору. Количество ретрансляторов, сигнал от которых к i-му проходит через рассматриваемый провод, назовем нагрузкой на данный провод для i-го ретранслятора. Максимум из нагрузок на все провода для i-го ретранслятора называется нагрузкой на данный ретранслятор. Известно, что по проводам электросети сигнал может пройти от одного ретранслятора к другому единственным образом.

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

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

Во входном файле содержится число N — количество ретрансляторов, за которыми следуют N − 1 пар чисел ui vi, означающих, что i-ый провод соединяет ретрансляторы ui и vi.

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

В выходном файле должно содержаться N чисел a1 a2… aN, где ai — нагрузка на i-ый ретранслятор.

Ограничения

1 ≤ N ≤ 100000.

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

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

Задача M. Бюрократия

Автор:ACM ICPC 2009-2010, NEERC, Northern Subregional Contest   Ограничение времени:3 сек
Входной файл:bureau.in   Ограничение памяти:256 Мб
Выходной файл:bureau.out  

Условие

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

Много веков спустя юристы обнаружили, что в королевстве было только два вида законов:

Закон считается активным если и только если нет активного закона, отменяющего его.

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

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

Первая строка входного файла содержит целое число n (1 ≤ n≤ 105) — число изданных законов.

Следующие n описывают по одному закону каждая. Каждое описания удовлетворяет одному из следующих форматов:

Законы нумеруются с единицы.

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

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

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

Входной файл (bureau.in) Выходной файл (bureau.out)
1
5
declare
cancel 1
declare
cancel 2
cancel 3
3
1 4 5

Problem N. Dijkstra

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

First line of input file contains three integers N M and S, where M is the number of edges. Next M lines contain three integers each — starting vertex number, ending vertex number and weight of some edge respectively. All weights are positive. There is at most one edge connecting two vertices in every direction.

Output file format

Output file must contain N integers — distances from source vertex to all vertices. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N ≤ 1000. All weights are less or equal than 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Задача O. Дорога в аэропорт

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

Условие

Город соединяется с аэропортом автодорогой, имеющей N полос движения. Дорога состоит из K участков длиной 10 километров каждый. На каждом участке полосы разделены сплошной линией разметки (т.е. сворачивать с одной полосы на другую запрещено). На стыке участков разрешено перемещение на любую из соседних полос. В начале каждого участка на каждой полосе дороги поставлен знак ограничения скорости, при этом на разных полосах ограничения могут различаться.

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

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

Во входном файле находятся числа N и K, за которыми идут N строк по K вещественных чисел ai, j в каждой — ограничение скорости на j-м участке i-й полосы (в км/час).

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

Выходной файл должен содержать единственное число — минимальное время (в часах) за которое можно попасть из города в аэропорт, с точностью до трех знаков после запятой.

Ограничения

1 ≤ N ≤ 10, 1 ≤ K ≤ 1000, 1 ≤ ai, j ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 3
70 60 40
0.559
2
3 2
1 10000
1 1
100 1
10.001

0.484s 0.010s 41