Дистанционные семинары

Будем решать задачу нахождения количества скобочных последовательностей, удовлетворяющих первым k символам шаблона, у которых баланс всегда неотрицателен и в конце равен m (обозначим количество таких последовательностей a_k,m). Есть два варианта: либо на k-м месте стоит открывающаяся скобка, тогда последовательность из k-1 скобки (без последней) должна иметь баланс m-1 - таких последовательностей a_k-1,m-1, либо закрывающаяся - тогда, наоборот, баланс последовательности без последней скобки равен m+1 - таких последовательностей a_k-1,m+1. В зависимости от шаблона и баланса возможны один, два (если в шаблоне стоит на этом месте ?) или ноль из этих вариантов. a_k,m равно их сумме. Ответ на поставленную задачу будет в a_n,0.

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

Задача 03-2. Шаблон и слово

• 
  В шаблоне на m-м месте стоит буква. Тогда она соответствует последней букве слова и a_k,m=(s1[k]=s2[m]) and a_k-1,m-1
  
• 
  В шаблоне на последнем месте стоит '?'. Тогда он соответствует последней букве слова и a_k,m=a_k-1,m-1
  
• 
  В шаблоне на последнем месте стоит '*'. Тогда возможны два варианта: либо этой звездочке соответсвует пустая последовательность букв слова, либо непустая. Во втором случае в части слова с 1-го по k-1-й символ этой звездочке тоже соответствует некоторая последовательность букв (возможно пустая). Таким образом a_k,m=a_k-1,m or a_k,m-1.
  

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

Занятие 4. Графы - введение.

Граф - это абстрактный математический объект. Он состоит из вершин и ребер. Каждое ребро соединяет пару вершин. Если одну и ту же пару вершин соединяют несколько ребер, то эти ребра называются кратными. Ребро, соединяющее вершину с ней самой, называется петлей. По ребрам графа можно ходить, перемещаясь из одной вершины в другую. В зависимости от того, можно ли по ребру ходить в обе стороны, или только в одну, различают неориентированные и ориентированные графы соответсвенно. Ориентированные ребра называются дугами. Если у всех ребер графа есть вес (т.е. некоторое число, однозначно соответсвующее данному ребру), то граф называется взвешенным. Вершины, соединенные ребром, называются соседними. Для неориентированного графа степень вершины - число входящих в нее ребер. Для ориентриованного графа различают степень по входящим и степень по исходящим ребрам. Граф называется полным, если между любой парой различных вершин есть ребро.

Граф - объект абстрактный, и интерпритировать его мы можем по-разному, в зависимости от конкретой задачи. Рассмотрим пример. Пусть вершины графа - города, а ребра - дороги, их соединяющие. Если дороги имеют одностороннее движение, то граф ориентированный, иначе неориентированный. Если проезд по дорогам платный, то граф взвешенный.

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

Есть несколько способов представления графа в памяти компьютера. На этом занятии мы рассмотрим некоторые из них.

• 
  В матрице смежности графа без петель на главной диагонали стоят 0.
  
• 
  Матрица смежности неориентированного графа симметрична относительно главной диагонали.
  

Задача 04-1. Города и дороги

Задача 04-2. Светофорчики

Задача 04-3. Цветной дождь

Задача 04-4. Издевательство

В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

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

Формат входных данных
Во входном файле INPUT.TXT записано сначала число N (3 <= N <= 100), а затем матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

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

Пример

Занятие 5. Графы: поиск кратчайшего пути, обход в ширину.

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

Будем решать чуть более общую задачу: искать кратчайшее расстояние от начальной вершины до всех остальных. Рассмотрим два способа ее решения.

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

В начале работы алгоритма нам известна только длина пути до начальной вершины, она равна 0. Рассмотрим все вершины, соседние с начальной, расстояние до каждой из них равно 1. Рассмотрим все вершины, являющиеся соседями для вершин, расстояния от начальной вершины до которых равно 1. Если расстояние до такой вершины еще не посчитано, то оно равно 2, и так далее. Таким образом, на k-ом шаге мы находим все вершины, расстояние до которых равно k-1: найдя такую вершину, перебираем все соседние с ней вершины, и, если расстояние до нее еще не посчитано, то оно равно k. Если на некотором шаге мы не изменили ни одного числа в массиве - длины всех путей найдены. Заметим, что кратчайший путь до вершины не может иметь длину больше, чем N-1.

Заведем очередь. Вероятно, что в жизни очередь видели все. По мере поступления, объекты помещаются в очередь. Когда "продавец" очереди освобождается, он извлекает из очереди следующий элемент и "обслуживает" его. Очередь часто удобно реализовывать с помощью массива и двух указателей - на первый "необслуженный" элемент, и первый свободный элемент массива. Тогда добавление элемента в очередь выглядит так: помещаем его в элемент массива, на который указывает 2-й указатель, с увеличиваем этот указатель на 1. Извлечение из очереди столь же просто: берем элемент, на который указывает 1-й указатель, и указатель увеличиваем на 1.

Вернемся к поиску длин кратчайших путей. Изначально поместим в очередь один элемент - начальную вершину. До нее расстояние известно и равно 0. На каждом шаге алгоритма извлекаем из очереди одну вершину (пусть это вершина v и до нее расстояние k). Затем пербираем всех соседей данной вершины, расстояние до которых еще не известно и добавляем их в очередь. Расстояние до них записываем k+1. Алгоритм заканчивается, когда очередь опустеет. Этот алгоритм работает быстрее предыдущего. Время работы алгоритма зависит от конкретной реализации. Обычно алгоритм выполняет порядка N² или M действий.

Восстановление пути
Пусть мы знаем кратчайшие расстояния до всех вершин. Как найти кратчайший путь до конкретной вершины? Рассмотрим эту вершину (обозначим ее V). Пусть длина пути до нее L. Эта вершина является последней в пути к V. Найдем какую-нибудь вершину, которая соединена с V, и расстояние до которой равно L-1. Тогда эта вершина является предпоследней в пути (если таких вершин несколько, значит существует несколько кратчайших путей и можно выбрать любую из этих вершин). Далее найдем вершину, которая соединена с предпоследней и расстояние до которой равно L-2. Она является пред-предпоследней. Продолжая этот процесс мы можем "раскрутить" весь путь задом наперед. Осталось только запомнить его в массиве и вывести в правильном порядке.

Задача 05-1. Путь

Задача 05-2. Один конь