#527

Антон решает задачи

Темы: [Алгоритмы сортировки]

Источники: [ Командные олимпиады, Московская командная олимпиада, 8 класс, 2006, Задача C ]

Мальчик Антон решает вступительную работу в летний математический лагерь. В ней $N$ заданий, которые можно выполнять в произвольном порядке. Разные задачи требуют разного времени для решения. При этом известно, что если задание с номером $i$ выполнять $j$-м по счету, Антону потребуется $T_i$*$j$ времени: чем больше думаешь, тем больше устаешь. Например, если начать с первой задачи, а затем выполнить вторую, то потребуется $T_1$*1 + $T_2$*2 времени, а если выполнить сначала вторую задачу, а затем первую – то $T_2$*1 + $T_1$*2. Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени.

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

В первой строке вводится число $N$, во второй строке —$N$ чисел через пробел$T_1$, $T_2$, …, $T_N$, разделенные пробелами. Все числа целые и удовлетворяют следующим ограничениям: 0 < $N$ ≤ 10, 0 < $T_i$ ≤ 100.

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

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

(Во входных данных не хватает вывода номеров задач)

#537

Форум

Темы: [Сортировка подсчетом]

Источники: [ Командные олимпиады, ВКОШП, 2002, Задача B ]

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

Клуб Юных Хакеров организовал на своем сайте форум. Форум имеет следующую структуру: каждое сообщение либо начинает новую тему, либо является ответом на какое-либо предыдущее сообщение и принадлежит той же теме.

После нескольких месяцев использования своего форума юных хакеров заинтересовал вопрос - какая тема на их форуме наиболее популярна. Помогите им выяснить это.

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

В первой строке вводится целое число N - количество сообщений в форуме (1 <= $N$ <= 1000). Следующие строки содержат описание сообщений в хронологическом порядке.

Описание сообщения, которое представляет собой начало новой темы, состоит из трех строк. Первая строка содержит число 0. Вторая строка содержит название темы. Длина названия не превышает 30 символов. Третья строка содержит текст сообщения.

Описание сообщения, которое является ответом на другое сообщение, состоит из двух строк. Первая строка содержит целое число - номер сообщения, ответом на которое оно является. Сообщения нумеруются, начиная с единицы. Ответ всегда появляется позже, чем сообщение, ответом на которое он является. Вторая строка содержит текст сообщения.

Длина каждого из сообщений не превышает 100 символов.

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

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

Примеры

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

2
0
topic 1
body of message 1
0
topic 2
body of message 2

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

topic 1

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

2
0
topic 1
body of message 1
1
body of message 2 being the reply to message 1

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

topic 1

#543

Военная сортировка

Темы: [Сортировка "пузырьком"] [Сортировка выбором (максимума)]

Источники: [ Командные олимпиады, ВКОШП, 2002, Задача H ]

Требуется упорядочить числа от 1 до N. Разрешается менять только соседние числа и нельзя переставлять число, которое уже стоит на своем месте.

Фирма Macrohard получила заказ от армии одной страны на реализацию комплекса программного обеспечения для нового суперсекретного радара. Одной из наиболее важных подпрограмм в разрабатываемом комплексе является процедура сортировки.

Однако в отличие от обычной сортировки, эта процедура должна сортировать не произвольный массив чисел, который передается ей на вход, а специальный заранее заданный массив из $N$ чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до $N$, и кроме того, ни одно число в нем изначально не находится на своем месте (то есть на позиции с номером i изначально не находится число $i$).

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

Например, если массив из 6 элементов в некоторый момент имеет вид <2, 1, 3, 6, 4, 5>, то можно поменять местами 1 и 2, 6 и 4 или 4 и 5, а менять местами 1 и 3 или 3 и 6 нельзя, поскольку число 3 находится на своем месте (на позиции с номером 3).

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

Подсказка

Найти такую последовательность обменов всегда возможно.

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

В первой строке вводится целое число $N$ - размер входного массива (1 <= $N$ <= 100). Вторая строка содержит $N$ целых чисел - исходную перестановку чисел от 1 до $N$ в массиве. Изначально ни одно число не стоит на своем месте.

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

Выведите $K$ строк, где $K$ - количество обменов в Вашей сортировке. На каждой строке выведите по два числа $x_i$ и $y_i$, разделенных пробелом - позиции в массиве, числа на которых следует поменять местами на i-ом обмене. Помните, что должно выполняться условие |$x_i$ - $y_i$| = 1 и что нельзя перемещать число, которое уже стоит на своем месте.

Пояснение к примеру

В приведенном примере массив последовательно имеет следующий вид:
исходный вид массива
2 3 1 6 4 5
поменяли местами числа на 2 и 3 позициях
2 1 3 6 4 5
поменяли местами числа на 1 и 2 позициях
1 2 3 6 4 5
поменяли местами числа на 4 и 5 позициях
1 2 3 4 6 5
поменяли местами числа на 5 и 6 позициях
1 2 3 4 5 6

Примеры

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

6
2 3 1 6 4 5

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

#553

Расшифровка письменности Майя

Темы: [Строки] [Сортировка подсчетом]

Источники: [ Личные олимпиады, Международные олимпиады, 2006, 1 тур, Задача A ]

Дана строка и подстрока. Требуется определить, сколько раз в строке встречалась подпоследовательность, состоящая из символов подстроки.

Расшифровка письменности Майя оказалась более сложной задачей, чем предполагалось ранними исследованиями. На протяжении более чем двух сотен лет удалось узнать не так уж много. Основные результаты были получены за последние 30 лет.

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

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

Археологи ищут некоторое слово $W$. Они знают значки для него, но не знают все возможные способы их расположения. Поскольку они знают, что Вы приедете на IOI ’06, они просят Вас о помощи. Они дадут Вам $g$ значков, составляющих слово $W$, и последовательность $S$ всех значков в надписи, которую они изучают, в порядке их появления. Помогите им, подсчитав количество возможных появлений слова $W$.

Задание

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

Ограничения

1 ≤ $g$ ≤ 3 000, $g$ – количество значков в слове $W$

$g$ ≤ |$S$| ≤ 3 000 000 где |$S$| – количество значков в последовательности $S$

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

На вход программы поступают данные в следующем формате:

СТРОКА 1: Содержит два числа, разделенных пробелом – $g$ и |$S$|.
СТРОКА 2: Содержит $g$ последовательных символов, с помощью которых записывается слово $W$ . Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.
СТРОКА 3: Содержит |$S$| последовательных символов, которые представляют значки в надписи. Допустимы символы: ‘a’-‘z’ и ‘A’-‘Z’; большие и маленькие буквы считаются различными.

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

Единственная строка выходных данных программы должна содержать количество возможных вхождений слова $W$ в $S$.

Оценивание

Для части тестов, оцениваемых в 50 баллов, выполняется ограничение $g$ ≤ 10.

Важно для программирования на PASCAL

По умолчанию во FreePascal переменная типа string имеет ограничение размера в 255 символов. Если Вы хотите использовать более длинные строки, Вы должны добавить директиву {$ H +} в ваш код, сразу после строки program ...;.

Примеры

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

4 11
cAda
AbrAcadAbRa

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

#574

Выпуклая оболочка

Темы: [Многоугольники. Выпуклые оболочки] [Сканирующая прямая]

Источники: [ Командные олимпиады, ВКОШП, 2007, Задача C ]

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

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

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

На рисунке слева приведены два угла, на рисунке справа изображена их выпуклая оболочка.

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

В первой строке вводится число $n$ - количество углов (1 <= $n$ <= 1000). Каждая из следующих n строк содержит описание одного угла. Угол задается координатами трех точек: вершины и двух отличных от вершины точек - по одной на каждом из лучей. Все координаты целые и не превышают $10^4$ по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.

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

Выведите границу выпуклой оболочки в виде последовательности направленных лучей, прямых и отрезков. Никакие два объекта в выходных данных не должны лежать на одной прямой. Все отрезки должны иметь длину больше нуля. Объекты должны быть перечислены в таком порядке, чтобы начало каждого следующего совпадало с концом предыдущего. Все выводимые числа должны быть целыми и не превосходить $10^5$ по абсолютной величине. При проходе вдоль описанной границы выпуклая оболочка углов должна быть справа. На первой строке выведите $L$ - количество объектов в ответе. Следующие $L$ строк должны содержать описание объектов. Объекты описываются следующим образом:

*Отрезок: "segment $x_1$ $y_1$ $x_2$ $y_2$", где ($x_1$, $y_1$) и ($x_2$, $y_2$) - концы отрезка, отрезок считается направленным от ($x_1$, $y_1$) к ($x_2$, $y_2$).
*Луч, направленный от начала: "outray $x_1$ $y_1$ $x_2$ $y_2$", где ($x_1$, $y_1$) - начало луча, а ($x_2$, $y_2$) - произвольная точка на луче, отличная от начала.
*Луч, направленный к началу: "inray $x_1$ $y_1$ $x_2$ $y_2$", где ($x_2$, $y_2$) - начало луча, а ($x_1$, $y_1$) - произвольная точка на луче, отличная от начала.
*Прямая: "line $x_1$ $y_1$ $x_2$ $y_2$", где ($x_1$, $y_1$) и ($x_2$, $y_2$) - две точки на прямой, причем при движении вдоль прямой в ее направлении точка ($x_1$, $y_1$) следует ранее точки ($x_2$, $y_2$).
*Если выпуклой оболочкой является вся плоскость, то выведите $L$ = 0.

Примеры

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

2
3 1 4 1 4 4
2 2 4 3 3 4

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

3
inray 4 1 3 1
segment 3 1 2 2
outray 2 2 3 5

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

2
0 0 1 0 0 1
0 0 -1 0 0 1

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

1
line 0 0 -1 0

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

2
0 0 1 0 0 1
0 0 -1 0 0 -1

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