Задача A. Разнообразные строки ≡

Условие

Будем называть разнообразностью строки количество символов, которые встречаются в ней ровно один раз. Например, разнообразность строки "INFORMATICS" - 9, поскольку символы "A", "C", "F", "M", "N", "O", "R", "S" и "T" встречаются в ней ровно один раз.

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

Строка A меньше строки B в лексикографическом порядке, если выполняется одно из условий:

1. A является началом B;
2. для некоторого числа i первые i символов строки A совпадают с первыми i символами строки B, а i+1-й символ в строке A идет в алфавите раньше i+1-го символа в строке B.

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

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

Ограничения

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

ABBAC

BAC

OLYMP

OLYMP

AAA

A

Задача B. Перепутанные диски ≡

Условие

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

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

Например, пусть у Васи есть три компакт-диска с играми — "Цивилизация", "Тетрис" и "Сапер". Пусть Вася сначала начал играть в "Цивилизацию", а затем решил поиграть в "Тетрис". Тогда после этого диск с "Цивилизацией" окажется в коробке от "Тетриса". Пусть затем он решил поиграть в "Сапера". Тогда диск от "Тетриса" окажется в коробке от "Сапера". Если после этого он снова решит поиграть в "Цивилизацию" (заметим, что для этого он достанет ее из коробки от "Тетриса"), то игра "Сапер" окажется в коробке от "Тетриса", а "Цивилизация" — в CD-приводе Васиного компьютера.

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

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

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

Ограничения

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

4
Civilization
Tetris
Minesweeper
Civilization

Civilization - *
Tetris - Minesweeper
Minesweeper - Tetris

Задача C. Домашние задания ≡

Условие

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

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

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

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

Первая строка входного файла содержит два числа: n — количество учебных дней, m — количество отличников в классе у Пети.

Вторая строка входного файла содержит m целых чисел a_i (1 ≤ i ≤ m), задающих для каждого отличника максимальное количество заданий подряд, которое он согласен выполнять за Петю (1 ≤ a_i ≤ n).

Следующие m строк содержат по n неотрицательных целых чисел, при этом j-е число i-й строки (c_{i, j}) означает количество конфет, которое Пете придётся отдать i-му отличнику, чтобы он сделал за Петю домашнее задание в j-й день.

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

Ограничения

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

5 2
2 2
1 3 6 4 1
5 2 3 1 1

9
1 1 2 2 1

Задача D. Задача массового поражения ≡

Условие

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

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

Количество роботов ограничено — в пещеру можно запустить не больше K штук. Вы находитесь на площадке с номером 1. После запуска каждого робота ему можно давать команды "перейти с текущей площадки на площадку i", причем площадка i должна быть соединена с текущей. Роботы чрезвычайно неповоротливы, вернее, они вообще неповоротливы. Если робот прошел по какому-то лазу, то больше он там пройти не может (однако позже там может пройти другой робот).

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

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

• K = 1, K = 2.

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

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

Ограничения

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

7 2
1 3
2 3
1 6
2 7
3 4
4 5

6