Задача A. Сортировка подсчетом

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

Условие

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

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

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

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

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

Ограничения

0 ≤ N ≤ 100000, все числа находятся в диапазоне от 1 до 100000

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

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

Задача B. Куча максимумов

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

Условие

Из данных N чисел необходимо выбрать K наибольших и вывести их в порядке возрастания.

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

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

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

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

Ограничения

1 ≤ N ≤ 106, 1 ≤ K ≤ min(N, 105), 231 ≤ Ai ≤ 231

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

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

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

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

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

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

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

Автор: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

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

Автор:М. Спорышев   Ограничение времени: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

Задача G. 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

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

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


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

Автор:С. Пак   Ограничение времени: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 J. 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

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

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

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

Автор:Н. Ляхута, М. Спорышев   Ограничение времени: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

Задача 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

Problem O. Floyd-Warshall

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

Statement

You are to write a program that finds shortest distances between all pairs of vertices in a directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N and M, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a matrix of size NxN. Element in the j-th column of i-th row mush be the shortest distance between vertices i and j. The distance from the vertex to itself is considered to be 0. If some vertex is not reachable from some other, there must be empty space in corresponding cell of matrix.

Constraints

0 ≤ N ≤ 100. All weights are less than 1000 by absolute value.

Sample tests

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

Problem P. Ford-Bellman

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

Statement

You are to write a program that finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

Sample tests

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

Problem Q. Topological sorting

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

Statement

You are to write a program that performs a topological sorting of a directed graph. Graph contains N vertices, numbered with integers from 1 to N, and M edges.

In other words, given a partial order on numbers from 1 to N, your program must produce some linear order on these numbers which does not conflict with the given partial order.

Input file format

Input file contains two integers N and M, followed by M pairs of integers. Integers in each pair are different, and represent starting and ending vertex of a graph edge.

These pairs may also be considered comparisons where the first number precedes the second one.

Output file format

Output file must contain a permutation of integers from 1 to N — numbers of vertices sorted in topological order. (That is, representing a linear order.) If ordering is not possible, output file must contain a single number 1.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
4 3
1 2
1 3
3 4
1 3 2 4

0.279s 0.006s 47