Задача 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, то Петя должен успеть дочитать её в день с номером Ri − 1.

Петя хочет прочесть все необходимые ему книги. За день Петя может прочесть любое неотрицательное целое число страниц из любых имеющихся у него книг, однако хочет распределить нагрузку максимально равномерно. Найдите такое наименьшее целое 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

Problem E. Hot-keys

Author:A. Klenin   Time limit:5 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

When designing dialog forms for interactive programs, it is important to assign hot-keys (known also as accelerator keys) to each dialog element, so as to facilitate keyboard input.

For better mnemonics, hot-keys are assigned based on the letters of dialog elements' captions, usually favoring letters near the beginning of caption. Manual hot-keys distribution can be tedious and error-prone, as one must be careful not to assign same letter to different elements.

Your program will be given a list of captions. It must assign unique hot-keys to as many captions of possible. Each assigned hot-key must be a letter from the corresponding caption.

For each hot-key, position is the leftmost occurrence of the hot-key letter in the corresponding caption. From all solutions with the same numbers of hot-keys, your program must choose the one with minimal sum of hot-key positions. If there is still more than one optimal solution, output any of them.

Input file format

Input file contains number of captions N followed by N lines with captions.

Output file format

Output file must contain N lines with the same captions as in input. In those captions which have hot-key assigned, leftmost occurrence of hot-key letter must be preceded with '&' (ASCII 38).

Constraints

1 ≤ N ≤ 10, all captions are from 1 to 10 characters in length and consist of small Latin letters.

Sample tests

No. Input file (input.txt) Output file (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.402s 0.012s 23