Алгоритмы

Вам нужно напечатать N слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:

Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.

 

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

 

Ваша программа должна считать следующие входные данные:

 

На первой строке число N (1<=N<=25000).

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

Ваша программа должна вывести следующие данные:

 

На первой строке M — число операций.

На следующих M строках по одному символу — описание операций. Каждая операция описывается одним символом:

Добавление символа обозначается собственно символом.

Удаление символа обозначается символом «-» (минус, ASCII-код 45).

Операция «напечатать текущее слово» обозначается символом «P» (заглавная латинская буква P).
 

Ввод	Вывод
3 print the poem	20 t h e P - - - p o e m P - - - r i n t P

Цепочкой слов длины n назовем последовательность слов w₁, w₂, ..., w_n такую, что для 1 ≤ i ≤ n слово wi является собственным префиксом слова w_i + 1.

 

Напомним, что слово u длины k называется собственным префиксом слова v длины l, если l > k и первые k букв слова v совпадают со словом u.

 

Задано множество слов S = {s₁, s₂, ..., s_m}. Найдите максимальную длину цепочки слов, которую можно построить, используя (возможно, не все) слова этого множества.

 

Первая строка входного файла содержит целое число m(1 ≤ m ≤ 255). Каждая из последующих m строк содержит по одному слову из множества S.

 

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

 

В выходной файл выведите ответ на задачу.
 

Ввод	Вывод
3 a ab abc	3
5 a ab bc bcd add	2

В теории кодирования часто используют беспрефиксные коды наборы слов, ни одно из которых не является префиксом. Слово α называется префиксом слова β, если α получается из β удалением нуля или более символов в конце. Например, слова a, ab и aba являются префиксами слова aba. Например, набор слов aba, aa и bac является беспрефиксным кодом, а набор abac, aba, ba нет, поскольку слово aba является префиксом слова abac.

 Профессор Дешифро работает в лаборатории исследования бесполезной информации и изучает свое новое изобретение почти беспрефиксные коды. Набор слов называется почти беспрефиксным кодом уровня k, если наибольший общий префикс двух любых слов из набора не превышает по длине k. Например, набор abac, abс, ba является почти беспрефиксным кодом уровня 2, а набор abac, abab, ba нет, поскольку наибольший общий префикс слов abac и abab имеет длину 3.

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

 

Первая строка входного файла содержит два целых числа: n и k количество слов в заданном наборе и уровень почти беспрефиксного кода, который требуется построить (\(1<= n <= 100000\), \(0 <= k <= 200\)). Следующие n строк содержат по одному слову. Слова состоят из строчных букв латинского алфавита. Длина каждого слова от 1 до 200 символов. Суммарная длина всех слов не превышает \(10^6\). Все слова различны.

 

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

 

Примеры

№	Входные данные	Выходные данные
1	6 2 aba bacaba abacaba baca abac caba	3

Мальчик Кирилл написал однажды на листе бумаги строчку, состоящую из больших и маленьких латинских букв, а после этого ушел играть в футбол. Когда он вернулся, то обнаружил, что его друг Дима написал под его строкой еще одну строчку такой же длины. Дима утверждает, что свою строчку он получил циклическим сдвигом строки Кирилла на несколько шагов вправо (циклический сдвиг строки abcde на 2 позиции вправо даст строку deabc).
Однако Дима известен тем, что может случайно ошибиться в большом количестве вычислений, поэтому Кирилл в растерянности – верить ли Диме? Помогите ему! По данным строкам выведите минимальный возможный размер сдвига или -1, если Дима ошибся.

 

Первые две строки входных данных содержат строки Кирилла и Димы, соответственно. Длины строк одинаковы, не превышают 10000 и не равны 0.

 

Выведите единственное число – ответ  на вопрос задачи.
 

 

Примеры

№	Входные данные	Выходные данные
1	zabcd abcdz	4

Последовательность 011212201220200112… строится следующим образом: сначала пишется 0, затем повторяется следующее действие: уже написанную часть приписывают справа с заменой 0 на 1, 1 на 2, 2 на 0, и т.д.

 

Требуется написать программу, которая по заданному натуральному числу N определяет, какое число стоит на N-ом месте.

 

Дано натурально число число N (1 ≤ N ≤ 10¹⁸).

 

Выведите число, которое стоит на k-ом месте в последовательности.
 

Ввод	Вывод
1	0
10	2

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

 

Входные данные

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

 

Выходные данные

Выведите «1», если выигрывает первый игрок или «2», если выигрывает второй игрок. Если выигрывает первый игрок, во второй строке выведите число K — общее количество выигрышных ходов. В последующие K строк выведите информацию о выигрышных ходах — пары чисел, перечисленные в порядке возрастания первой координаты, а при равенстве в порядке возрастания второй координаты. В каждой такой паре первое число должно обозначать номер кучки, а второе — количество спичек, которые необходимо взять из этой кучки.

Ввод	Вывод
1 10	1 1 1 10
2 1 1	2

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

 

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

 

Выведите «1», если выигрывает первый игрок или «2», если выигрывает второй игрок.

Петя получил золотую медаль на IOI, за что от правительства ему положена благодарность в виде шоколадки. На данный момент имеется N видов шоколадок, которые производит государственная шоколадная фабрика. У каждой шоколадки есть стоимость. Кроме того, у каждого вида, кроме шоколадки "Юлька", есть вид-прародитель. Известно, что прародителем может быть только шоколадка, которая была выпушена хронологически раньше. Исторически самый первый вид - "Юлька". Чиновник и Петя выбирают шоколадку ему в подарок. При этом цель первого - сэкономить, второго - получить настолько дорогую шоколадку, насколько это возможно. Начинается выбор с "Юльки". Петя за ход либо берет текущую шоколадку, либо меняет свой выбор на шоколадку-потомка (если это возможно). Чиновнику же кажется, что позже выпущенные виды хуже и дешевле, поэтому он меняет выбор на шоколадку-потомка (если это возможно), либо покупает Пете шоколадку (если потомков нет). Они ходят по очереди, Петя - первый. Определите, на шоколадку какой стоимости может претендовать Петя.

 

Входные данные

Сначала вводится число 0 < N <= 200000 - количество видов. "Юлька" имеет номер 1. Далее идут N строк с парами чисел 0 <= P_i <= N - номер сорта-предка (для шоколадки "Юлька" указан 0, у остальных P_i > 0) и 0 < Ci <= 1000000000 - стоимость i-го сорта.

 

Выходные данные

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

Ввод	Вывод
8 0 4 5 3 1 2 5 1 1 5 4 8 3 6 3 7	6

Напомним содержание первой серии. Двое играют в такую игру: перед ними лежит шоколадка размера NxM. За ход можно разломить имеющийся кусок шоколадки вдоль одной из сторон на 2 "непустых".

 

Однако, нельзя разламывать куски размером не больше, чем 1k (куски можно поворачивать; мы считаем, что один кусок "не больше" другого, если он равен ему или его части). Таким образом, нельзя разламывать куски размером 11, 12, , 1k, а остальные куски разламывать можно.

 

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

 

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

 

Проигрывает тот, кто не может сделать ход. Определите, кто же станет победителем в игре, если известны начальные размеры шоколадки.

 

Входные данные

Вводятся целые числа 0 < N, M, K <= 100.

 

Выходные данные

Выведите 1 или 2 - номер игрока, который выиграет при правильной игре.

Ввод	Вывод
1 1 1	1
1 1 100	1

Двое играют в такую игру: перед ними лежит шоколадка размера NxM. За ход можно разломить имеющийся кусок шоколадки вдоль одной из сторон на 2 "непустых".

 

Однако, нельзя разламывать куски размером не больше, чем 1k (куски можно поворачивать; мы считаем, что один кусок "не больше" другого, если он равен ему или его части). Таким образом, нельзя разламывать куски размером 11, 12, , 1k, а остальные куски разламывать можно.

 

Проигрывает тот, кто не может сделать ход. Определите, кто же станет победителем в игре, если известны начальные размеры шоколадки.

 

Входные данные

Вводятся целые числа 0 < N, M, K <= 100.

 

Выходные данные

Вывести 1 или 2 - номер игрока, который выиграет при правильной игре.

Ввод	Вывод
1 1 1	2
2 2 1	1

 

В начальный момент времени Снарк находится в точке прямой с целой неотрицательной координатой X. За ход он может оказаться в любой точке с целой координатой Y при условии, что |X-Y| <= S. Кроме того, Снарк не любит булочки, поэтому он никогда не прыгнет в клетку, где одна из этих противных штук лежит. Булочник не хочет, чтобы Снарк попал домой. После каждого хода Снарка Булочник может положить булочку в любую точку прямой при условии, что это не начало координат (дом Снарка) и в этой клетке нет Снарка. Определите, сможет ли Булочник помешать Снарку оказаться дома. Изначально в некоторых клетках лежат булочки.

 

Входные данные

В первой строке задаются целые числа 0 <= X < 10000, 0 < S <= 100 и 0 <= N < max(X-1, 0) - количество булочек, которые уже лежат на прямой. Далее идут N различных чисел 0 < b_i < X - координаты точек, где лежит гадость.

 

Выходные данные

Выведите "YES", если Булочник сможет реализовать свои грязные планы, "NO" - если при любых действиях врага Снарк сможет припрыгать домой.

Ввод	Вывод
1 1 0	NO
10 3 3 7 8 9	YES

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

 

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

 

Требуется вывести одно число – ответ  на вопрос задачи.
 

 

Примеры

№	Входные данные	Выходные данные
1	z	1
2	abcdef	6

Сегодня у Кэрол выходной. Но даже в этот прекрасный весенний день она не отдыхает, а тренируется и готовится к сражениям со скруллами. Одним из важных навыков является умение быстро ориентироваться в незнакомых местах. Для того, чтобы отточить это умение, Кэрол пригласила своего наставника Йон-Рогга.

Кэрол и Йон-Рогг будут играть в следующую игру. Сначала Йон-Рогг нарисует на бумаге карту убежища скруллов. Карта представляет из себя n помещений, пронумерованных от 1 до n. Некоторые пары помещений соединены двусторонними переходами. Убежище устроено так, что от любого помещения до любого другого можно добраться, перемещаясь по коридорам. Для того, чтобы игра не была слишком сложной, Йон-Рогг нарисует ровно n − 1 переход между помещениями. Иными словами, карта убежища представляет собой дерево.

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

После того, как Йон-Рогг нарисует на бумаге карту убежища, он также для каждого перехода отметит, в каком направлении по нему перемещаются роботы. Иными словами, Йон-Рогг ориентирует ребра нарисованного дерева.

Чтобы структурировать карту убежища, Кэрол должна составить список, состоящий из всех номеров помещений в некотором порядке. При этом должно выполняться следующее условие: в любом переходе роботы перемещаются от помещения, которое идет в списке раньше, к помещению, которое идет с писке позже. Более формально, Кэрол должна составить такую перестановку номеров помещений p₁p₂ . . . p_n, для которой верно, что если роботы могут перемещаться по переходу от помещения pi к помещению p_j , то i < j.

Пока Кэрол бьется над своим заданием, Йон-Роггу стало интересно, сколько всего решений существует у этой задачи. Иными словами, Йон-Роггу интересно, сколько перестановок удовлетворяют условию, описанному выше. Помогите ему узнать это. Так как ответ может быть очень большим, Йон-Рогг попросил вас сообщить лишь его остаток от деления на 998 244 353.

Входные данные: Первая строка входных данных содержит единственное целое число n — количество помещений в убежище, нарисованном Йон-Роггом (1 <= n <= 3 000).

Каждая из следующих n − 1 строк содержит два целых числа a, b — номера помещений, соединенных очередным коридором (1 <= a, b <= n). Роботы перемещаются по коридору в направлении от помещения a к помещению b.

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

Выходные данные: Выведите остаток от деления на 998 244 353 количества различных перестановок p₁p₂ . . . p_n, для которых верно, что если роботы перемещаются по переходу от помещения p_i к помещению p_j , то i < j.
 

В первом тесте из примера Кэрол может выписать две перестановки: {1, 2, 3} или {1, 3, 2}.

Во втором тесте Кэрол может выписать три перестановки: {2, 3, 1, 4}, {2, 3, 4, 1} или {2, 4, 3, 1}.

 

Верс нужно подготовить рапорт о последнем боевом вылете. Она уже сочинила в голове текст, осталось лишь его записать. Рапорт будет состоять из двух частей: первая будет содержать n слов, i-е из которых состоит из ai букв, вторая — m слов, j-е из которых состоит из bj букв. Язык Крии не содержит никаких знаков препинания. Верс должна записать рапорт на клетчатом рулоне бумаги, шириной w клеток. Так как рапорт состоит из двух частей, она разделит вертикальной чертой рулон на две части целой ширины, после чего в левой части напишет первую часть, а в правой — вторую.

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

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

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

   

Примеры

№	Входные данные	Выходные данные
1	15 6 6 2 2 2 3 2 2 3 3 5 2 4 3	3

Примечание

Кэрол Дэнверс, известная как Капитан Марвел противодействует флоту Скруллов. Каждый из

кораблей Скруллов имеет определенную мощность, выраженную натуральным числом.

Кэрол считает, что настолько сильна, что может не только вывести из строя флот, но и немного

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

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

мощность которого является медианой мощностей оставшихся кораблей.

Медиану ряда чисел Кэрол вычисляет следующим образом:

• Если количество чисел в ряду нечетно, то медиана — число, стоящее посередине упорядоченного по возрастанию данного ряда.

• Если количество чисел в ряду чётно, то медианой ряда является:

– Меньшее из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда, если два средних различны.

– Любое из двух стоящих посередине чисел упорядоченного по возрастанию данного ряда,

если два средних равны.

Помогите Капитану Марвел посчитать порядок, в котором нужно атаковать корабли.

На шахматной доске NxN в клетке (x1, y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2, y2), где растет вкусная шахматная трава. Какое наименьшее количество ходов он должен для этого сделать?

 

Формат входных данных
На вход программы поступает пять чисел: N, x1, y1, x2, y2 (\(5 <= N <= 20\), \(1 <= x_1,\ y_1,\ x_2,\ y_2 <= N\)). Левая верхняя клетка доски имеет координаты (1, 1), правая нижняя - (N, N).

 

Формат входных данных
Выведите единственное число K - наименьшее необходимое число ходов коня. 

Дана непустая строка S, длина которой N не превышает \(10^6\). Будем считать, что элементы строки нумеруются от 1 до N.

 

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

 

Значением префикс-функции \(\pi[i]\) будем считать длину этой подстроки.

 

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

 

Требуется для всех i от 1 до N вычислить \(\pi[i]\).

 

Одна строка длины N, \(0 < N <= 10^6\), состоящая из маленьких латинских букв.

 

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

 

Примеры

№	Входные данные	Выходные данные
1	abracadabra	0 0 0 1 0 1 0 1 2 3 4

Учёный-ботаник получил карту дорог страны Лимония. Чтобы составить план исследования этой страны, ему требуется найти кратчайшие расстояния между каждой парой городов этой страны (можно ехать только по проложенным дорогам). Помогите учёному – напишите программу, которая решает эту задачу.

 

Входные данные

В первой строке вводится количество городов N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог между городами: положительное число означает расстояние между городами, ноль говорит о том, что дороги нет.

 

Выходные данные

Программа должна вывести все кратчайшие маршруты между всеми городами в следующем формате:

 

(1->3): 1 2 3 (23)

 

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

 

Ввод	Вывод
4 0 0 0 0 0 0 2 1 0 2 0 4 0 1 4 0	(1,2): 0  (1,3): 0  (1,4): 0  (2,3): 2 3 (2) (2,4): 2 4 (1) (3,4): 3 2 4 (3)

В одной из деревень Центрального района решили построить новую школу, но никак не могут выбрать, в какой именно. Решили сделать так: подсчитать для каждой деревни суммарное расстояние, которое будут проходить все школьники Центрального района, если школа будет построена в этой деревне, и выбрать место, для которого эта сумма будет минимальной. В распоряжении администрации есть карта дорог Центрального района. Напишите программу, которая поможет выбрать место для школы. Если какой-то населенный пункт не имеет связи с другим населенным пунктом, где предполагается разместить школу, считайте, что доставка каждого ученика вертолётом "стоит" 10000 единиц расстояния.

 

Входные данные

В первой строке вводится количество деревень N ( 1 ≤ N ≤ 100 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему дорог: положительное число означает расстояние между деревнями, ноль говорит о том, что дороги нет. В последней строке вводится N чисел - количество школьников в каждой деревне.

 

Выходные данные

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

Ввод	Вывод
4 0 11 8 4 11 0 2 5 8 2 0 13 4 5 13 0 15 26 30 12	2 255