Задача A. Коммивояжёр возвращается!

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

Условие

Коммивояжёр возвращается в систему Альфы Центавра! Население системы с нетерпением ждёт его прибытия — каждый хочет приобрести что-нибудь с далёких планет!

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

Найдите оптимальный маршрут для коммивояжёра. Массы больше не могут ждать!

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

В системе Альфы Центавра n планет. Это число записано в первой строке входного файла. Следующие n строк содержат по n чисел каждая: j-ое число на i-ой из этих строк — стоимость перемещения aij от i-ой планеты до j-ой. Числа в каждой строке разделены пробелами. aij = -1 означает, что из планеты i нельзя на прямую добраться до планеты j.

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

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

Ограничения

1 ≤ n ≤ 19, aij ≤ 108

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

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

Задача B. Номер циклической перестановки

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

Условие

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

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

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

В заголовке входного файла "input.txt" содержится единственная строка S, состоящая из цифр и строчных букв латинского алфавита.

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

Выходной файл "output.txt" должен содержать порядковый номер исходной строки.

Ограничения

0 < |S| ≤ 2 ⋅ 105

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

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

Задача C. Эффективное чтение

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

Условие

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

Более формально, занумеруем дни учебного семестра начиная с 1. Пете для учебы необходимо N книг. Занумеруем их числами от 1 до N. Для книги с номером i известны три числа:

Будем считать, что Петя приходит в библиотеку утром, забирая и отдавая необходимые книги. Таким образом, взяв книгу в день с номером Li, он может в тот же день начать её читать. Вместе с этим, если книгу необходимо отдать в день с номером Ri, то Петя должен успеть дочитать её в день с номером Ri1.

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

В приведённом примере имеется 2 книги и 3 дня для чтения (в день номер 4 Петя приходит в библиотеку утром). В первый день Петя берёт в библиотеке книгу с номером 1 и прочитывает, например, 30 страниц из неё. Во второй день Петя берёт книгу с номером 2. Поскольку эту книгу необходимо отдать в следующий день, все её 50 страниц следует прочесть в день с номером 2. На третий день Петя относит книгу 2 в библиотеку и дочитывает оставшиеся 30 страниц первой книги. Таким образом, Петя может прочесть обе книги, читая не более 50 страниц в день. С другой стороны, ответ не может быть меньше 50, поскольку вторую книгу нужно прочесть за один день.

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

N = 1;

N ≤ 103;

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

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

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

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

Ограничения

1 ≤ N ≤ 105;

1 ≤ Li < Ri ≤ 105;

1 ≤ pi ≤ 105;

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

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

Задача D. Антон и магазин радиодеталей

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

Условие

Инженер Антон зашёл в магазин радиодеталей. В магазине ровно N стеллажей. На i-м стеллаже лежат радиодетали типа ai (на двух различных стеллажах тип радиодеталей может повторяться). Антон обходит с тележкой стеллажи в порядке от первого до N-го.

Когда Антон подходит к очередному стеллажу, он смотрит в тележку. Если в тележке нет радиодеталей такого типа, как на стеллаже, Антон берёт деталь со стеллажа и складывает в тележку. Если радиодеталь такого типа в тележке уже лежит, Антон просто идет дальше.

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

Антон знает заранее, какие типы радиодеталей лежат на стеллажах, и хочет каждый раз выбрасывать из тележки такую деталь, чтобы как можно меньше раз складывать новые радиодетали в тележку (складывает он их только в случае, если таких деталей в тележке нет на данный момент).

Помогите Антону узнать, какое минимальное количество раз ему придётся складывать новую деталь в тележку.

Примечание

Рекомендуется рассмотреть частичные решения для N ≤ 1000, ai ≤ 105.

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

Входной файл содержит целое число два целых числа N и K, вторая строка содержит N чисел ai.

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

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

Ограничения

1 ≤ N, K ≤ 105

0 ≤ ai ≤ 109

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

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

Задача E. Hot-keys

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

Условие

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

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

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

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

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

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

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

Выходной файл должен содержать N строк с одинаковыми заголовками, как и во входном файле. В каждом заголовке, которому была назначена какая-то комбинации, перед самым левым вхождением символа из горячей клавиши необходимо добавить символ '&' (ASCII 38).

Ограничения

1 ≤ N ≤ 10, все заголовки имеют длину от 1 до 10 символов и состоят из строчных латинских букв.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
yes
no
cancel
&yes
&no
&cancel
2
4
abc
bca
acb
aaaa
&amp;abc
&amp;bca
a&amp;cb
aaaa

Задача F. Киберспортивный турнир

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

Условие

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

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

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

Первая строка входного файла содержит числа N и M. Следующие M строк содержат пары чисел ai и bi. Гарантируется, что не существует такой пары i и j, что ai = bj и bi = aj.

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

Если невозможно провести турнир так, как хочет Влад, необходимо вывести No. Иначе первая строка выходного файла должна содержать Yes, а следующие далее N − 1 строк — описание матчей в порядке их проведения. По два числа на строку: первое число — номер победившего в очередном матче игрока, второе число — номер проигравшего игрока. Если существует несколько правильных ответов, выведите любой из них.

Ограничения

2 ≤ N ≤ 100000, 0 ≤ M ≤ 500000, 1 ≤ ai, bi ≤ N

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

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

0.461s 0.012s 23