Для более удобного хранения информации заведем матрицу

C[1...n,1..n] (так называемую матрицу смежности) в которой C[i,j]=1, если в наборе есть пара (A_i,A_j) и C[i,j]=0 иначе.

Будем строить все возможные цепочки (по правилу, данному в условии) и искать среди них ту, которая имеет максимальную длину.

В качестве начального символа цепочки можно взять любой символ из A. Пусть это символ Ai. Ищем, просматривая строку i матрицы C слева направо элемент C[i,j]=1 (другими словами, ищем пару с первым элементом Ai). Если такого элемента не существует, то берем в качестве начала строки другой элемент множества A. Если элемент C[i,j]=1 найден, то ему соответствует пара (A_i,A_j). Помечаем ее как уже использованную полагая, например, C[i,j]=-1. Далее просматриваем слева направо строку j матрицы C в поисках еще не использованной пары (A_j,A_k) (C[j,k]=1). Присоединяем элемент Ak к имеющейся цепочке, полагаем C[j,k]=-1, ищем единичный элемент в строке k и т.д. Предположим, на некотором шаге мы получили цепочку

и в строке p матрицы больше нет ни одного единичного элемента. Это означает, что при таком подборе предыдущих элементов мы нашли максимальную по длине строку. Если ее длина больше длин всех найденных ранее строк, запоминаем эту строку как рекорд. После этого "отщепляем" от строки последний элемент Ap и смотрим, есть ли еще в строке l единичный элемент с индексом, большим p. Если да, то приписываем уже этот элемент к строке и пытаемся затем снова увеличить длину полученной строки, если же нет, то "отщепляем" от строки элемент A₁, в строке S ищем единичный элемент с индексом, большим l и т.д.

Останов осуществляется тогда, когда мы должны "отщепить" от строки A_i.

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

const M=10; {максимально число элементов в A}
{будем считать, что A состоит из чисел от 1 до N} 
var c:array[1..M,1..M] of integer;
curstr, maxstr: array[0..M] of integer;
{в этих переменных хранятся текущая цепочка и}
{цепочка максимальной длины.}
{В нулевом элементе хранится длина цепочки}
N,E : integer; {N - число элементов в A}
i,j,k : integer; {E - число пар в наборе}
procedure find;
var l,j : integer;
begin
l:=curstr[curstr[0]]; {l = последний элемент цепочки}
for j:=1 to N do {просмотр строки l}
if C[l,j]=1
then begin
curstr[0]:=curstr[0]+1;
curstr[curstr[0]]:=j; {j -> в цепочку}
c[l,j]:=-1; {пара использована}
find;
c[l,j]:=1; {пару снова разрешено использовать}
curstr[0]:=curstr[0]-1;
end;
if curstr[0]>maxstr[0] {если нашли более}
then maxstr:=curstr {длинную строку}
end;
begin
readln(N); readln(E);
for i:=1 to N do
for j:=1 to N do
C[i,j]:=0;
for k:=1 to E do begin
write('очередная пара: ',i,j);
c[i,j]:=1
end;
for i:=1 to N do begin
curr[0]:=1; {поиск цепочки}
curr[1]:=i; {начинающейся элементом i}
find;
end;
for i:=1 to maxstr[0] do
write(maxstr[i]); {печать максимальной строки} end.

[Назад]

Для решения задачи важно понять, что встреча роботов может произойти либо в пункте, либо на дороге. В первом случае задача решается просто: необходимо последовательно строить множества пунктов для каждого робота, в которых они могут оказаться через время, равное 0.5,1,1.5,2,...Т. Это можно делать, используя очереди. В случае же встречи роботов на дороге легко понять, что непосредственно перед встречей все они должны были находится в следующих пунктах:

1. Либо в двух пунктах, связанных дорогой;

2. Либо в пунктах, из которых есть дороги в один и тот же пункт;

3. Либо в трех пунктах, образующих треугольник.

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

[Назад]

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

Легко понять, что если рассмотреть точку, имеющую наибольшую координату Y, причем самую левую (т.е. наименьшую координату Х, если таких несколько), то для нее существует только 2 возможность быть пройденной роботом: робот должен прийти из ближайшей точки А снизу и пойти в ближайшую точку Б справа или наоборот. В любом случае эти 2 отрезка фиксированы для робота. Теперь те же рассуждения можно провести и для точек Б и точки, находящейся правее Б, а также для самых нижних, левых и правых точек. Окончательно получается, что возможный проход робота строго фиксирован. Если упорядочить точки по горизонталям (вертикалям), то первая точка горизонтали (вертикали) должна соединятся со второй, третья с четвертой и т.д. Понятно, что если получившаяся фигура связна (цикл), то решение существует для случаев 2. и 3., а для случая 1. нужно проверить, в нужном ли направлении стоит робот. Однако есть одна трудность в случае, когда существуют горизонталь и вертикаль, содержащие нечетное число точек, а обход существует. Это возможно только в случае, когда это стартовая точка обхода, причем она находится в 'нечетной' горизонтали и вертикали. Удалив ее, можно воспользоваться предыдущей процедурой, при этом фиксированные отрезки не должны пересекаться в удаленной точке.

[Назад]

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

[Назад]

Решается аналогично задаче 4.

[Назад]

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

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

Перебирая сначала все возможные варианты выбрасывания по одной, затем, в случае неудачи по две, три, ... ,N-1 шестерни и проводя аналогичные рассуждения мы получаем максимальное число шестерен, которое могло бы прийти в движение. О генерации вариантов выбрасывания шестерен см. задачу 2 (перебор).

[Назад]

Можно сформировать граф, состоящий из 2*N вершин, соответствующих открыткам и конвертам, причем две вершины соединены ребром, если одна соответствует открытке, а другая - конверту, при этом соответствующая открытка входит в соответствующий конверт. Добавив в этом графе 2 новые вершины, одна из которых смежна всем вершинам, соответствующим открыткам, а другая - всем вершинам, соответствующим конвертам, сведем задачу к задаче нахождения максимального потока между этими вершинами.

[Назад]

Разбиение на группы осуществляется аналогично, как и в Задаче 10. за тем исключением, что в ситуации 3. организуются две новые группы (пара групп, одна из них может оказаться в результате пустой). После разбиения всех людей будем использовать принцип формирования двух результирующих групп, основываясь на идее решения Задачи 2 из главы "Сортировки", учитывая возможности об'единения двух пар групп в одну пару групп произвольным слиянием двух групп из различных пар.

[Назад]

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

Для решения задачи достаточно определить, является ли связным граф, определяемый матрицей смежности, элементы которой а[i,j] равны 1, если люди с номерами i и j знакомы и равны 0 иначе. Граф называется связным, если существует путь между любыми парами его вершин. Понятно, что путь между вершинами i и j в таком графе и определяет возможную последовательность знакомств, позволяющих познакомить людей с номерами i и j.

Для определения связности графа можно воспользоваться методом поиска в ширину, который состоит в следующем.

На начальном этапе в очередь помещается некоторая начальная вершина, например вершина с номером 1.

На каждой из следующих итераций (пока очередь не пуста) выполняются следующие действия:

- извлекается вершина из очереди;

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

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

[Назад]

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

Предположим, что уже построен некоторый простой путь (x[1],x[2],...x[k]) Множество вершин, вошедших в путь, будем считать пройденными, остальные не пройденные. Возможны 3 ситуации.

1. Одна из вершин x[1],x[k] смежна одной из не пройденных еще вершин. В этом случае путь можно очевидным образом удлинить на одну вершину.

2. Ни одна из вершин x[1],x[k] не смежна одной из не пройденных еще вершин, а вершины x[1] и x[k] смежны. В этом случае понятно, что k>N/2, так как вершины x[1] и x[k] смежны N/2 вершинам. Следовательно количество не пройденных вершин не больше N/2. Следовательно любая вершина у из них смежна одной из пройденных вершин, например x[i]. Но тогда можно получить более длинный путь (у,x[i],x[i+1],...,x[k],x[1],x[2],...x[i-1]).

3. В этом случае степеней вершин нетрудно показать, что в пути (x[1],x[2],...x[k]) существует такой индекс i, что x[1] смежна x[i], а x[i-1] смежна x[k]. Следовательно, рассмотрев путь (x[i],x[i+1],...,x[k],x[i-1],x[i-2],...x[1]) мы имеем ситуацию 2., поэтому можно получить более длинный путь.

Применяя описанный выше способ начиная с пути длины 1, построим простой цикл, включающий все вершины.

[Назад]

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

Для существования такого цикла необходимо и достаточно наличия двух условий:

1. граф является связным;

2. степень любой вершины графа четна.

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

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

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

Такой процесс повторяется до тех пор, пока все ребра не будут пройдены. Описанный процесс можно начинать с пустого цикла А (пустой последовательности).

[Назад]

Так как сеть дорог определяет некоторый граф, то определим в этом графе множество вершин с нечетной степенью. Понятно, что количество таких вершин четно (так как сумма степеней вершин графа четна). Определим на этом множестве взвешенный граф (граф, на ребрах которого определены веса или расстояния) по следующему правилу. Вес ребра (i,j) равен кратчайшему расстоянию между вершинами, соответствующими i и j в исходном графе. Построим в этом графе совершенное сочетание минимального веса. Паросочетанием называется множество попарно несмежных ребер (не имеющих общих вершин). Паросочетание называется совершенным, если оно покрывает все вершины. Весом паросочетания называется суммарный вес входящих в него ребер. Существуют эффективные алгоритмы поиска совершенного сочетания минимального веса. Однако они очень трудны. Поэтому при малом количестве вершин в графе можно воспользоваться перебором всех возможных совершенных паросочетаний. При добавлении к исходному графу ребер совершенного паросочетания получится граф, у которого все степени вершин четны. Найдем в нем цикл, проходящий по каждому ребру графа ровно один раз. Этот цикл и является решением задачи. Заметим при этом, что каждое ребро (i,j) паросочетания должно быть заменено последовательностью дорог исходного графа, которая определяет кратчайшее расстояние между вершинами i и j в исходном графе.

[Назад]

Производительность конвейера определяется минимальной производительностью рабочего на конвейере. Поэтому для решения задачи нам достаточно определить максимальную производительность Р, при которой возможно распределить по станкам, всех рабочих, когда для каждого рабочего определен набор станков, на которые он может быть поставлен (понятно, что это те станки, производительность на которых у рабочего не ниже производительности Р). Легко понять, что для выбранной производительности Х задача определения, возможно ли распределение по станкам для каждого рабочего, аналогична решению задачи 4. Для определения максимальной производительности Р, при которой возможно распределить по станкам всех рабочих, можно воспользоваться методом дихотомии следующим образом. Отсортируем в одномерном A массиве размера N*N все элементы C[i,j], 1<=i,j<=N. Определим левую границу ЛГ=1 и правую границу ПГ=N.

Для элемента массива А с индексом СГ=(ЛГ+ПГ)/2, рассматриваемого в качестве возможной максимальной производительности Р, определяем, можно ли распределить по станкам всех рабочих. Если да, то величина возможной максимальной производительности Р увеличивается. Для этого пересчитывается значение левой границы по правилу ЛГ:=СГ+1. Если нет, то величина возможной максимальной производительности Р уменьшается. Для этого пересчитывается значение правой границы по правилу ПГ:=СГ-1.

Процесс заканчивается, когда ЛГ>=ПГ. Значение А[ПГ-1] и является максимальной производительностью Р, а конкретное распределение рабочих определяется структурой максимального потока.

[Назад]

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

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

Для каждой вершины к из множества непомеченных вершин (а на начальном этапе это все вершины, кроме первой) определяется ближайшая вершина из множества помеченных вершин БЛИЖ[к]. На каждой итерации определяется кратчайшее ребро (i,j) между множеством помеченных вершин и множеством непомеченных вершин, используя массив БЛИЖ. Найденное ребро выбирается для системы дорог, а соответствующая вершина j считается помеченной. После этого пересчитывается массив БЛИЖ. При этом учитывается, что к изменение некоторой величины БЛИЖ[k] может произойти только тогда, когда расстояние от k до j меньше, чем от k до БЛИЖ[k].

Алгоритм

для i от 1 до N выполнять
нц
флаг[i]:=0;
БЛИЖ[i]:=1
кц
флаг[1]:=1;
для k от 1 до N-1 выполнять
нц
минрас:=бесконечность;
для i от 2 до N выполнять
если флаг[i]=0 и минрас > C[БЛИЖ[i],i]
то минрас:=C[БЛИЖ[i],i];
j:=i;
все
Вывод ребра (БЛИЖ[j],j)
флаг[j]:=1;
для i от 2 до N выполнять
если флаг[i]=0 и C[БЛИЖ[i],i]>C[i,j]
то БЛИЖ[i]:=j;
все
кц

[Назад]

Предположим, что мы нашли точку встречи z, и пусть она лежит на дороге (u,v) длины l на расстоянии d>0 от дома u и на расстоянии (l-d)>0 от дома v. Все множество домов разделим на два непересекающихся подмножества V и U. В подмножество U входят те дома, расстояние от которых до дома v меньше, чем расстояние до дома u. Все остальные дома отнесем к подмножеству U.

Пусть B подмножестве V домов K_v, а в U – K_u, и пусть K_v>K_u.

Обозначим суммарное расстояние от точки z (находящейся на расстоянии d от дома u) до всех N домов через R(z,d). Очевидно, что

R(z,d)= сумма расстояний от v до домов множества V + сумма расстояний от u до домов множества U + K_u*d + K_v*(L-d).

Если мы сдвинем z на расстояние p, p<(L-d) по направлению к дому v, то

R(z,d+p)=R(z,d)+K_u*p+K_v*(-p)=R(z,d)+(K_u-K_v)p<R(z,d) ?!

т.е. первоначальная установка точки z была неверной. Случай Kv<Ku рассматривается аналогично. Если же Kv=Ku, то точка z может быть на дороге в любом месте, в том числе и в концевых домах.

Итак, из всего выше сказанного следует, что искомая точка совпадает с одним из N домов, и что нам достаточно для каждого из домов i вычислить (например, по алгоритму Дейкстры) кратчайшее расстояние от него до каждого из оставшихся домов, затем найти сумму этих кратчайших расстояний (т.е. минимальное суммарное расстояние до всех домов от i). Минимальное из суммарных расстояний по всем i и даст решение задачи.

[Назад]

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

[Назад]

Можно сформировать граф, состоящий из 2*N вершин, соответствующих К-гранникам и типу наклеек, причем две вершины соединены ребром, если одна соответствует наклейке, а другая - К-граннику, при этом наклейка соответствующего типа находится на соответствующем К-граннике. Добавив в этом графе 2 новые вершины, одна из которых смежна всем вершинам, соответствующим типам наклеек, а другая - всем вершинам, соответствующим К-гранникам, сведем задачу к задаче нахождения максимального потока между этими вершинами.

[Назад]

Показывается, что точное решение есть максимум из двух

решений, полученных при помощи следующих эвристик:

1) Вершину 1 соединяем последовательно с вершинами 2, 3, ...,N.
Вершину 2 соединяем последовательно с вершинами 3,4,...,N.

......

Вершину i соединяем последовательно с вершинами i+1, i+2, ...,N.

......

и так до тех пор, пока хватит проводков.

2) Вершину 2 соединяем с вершиной 1.
Вершину 3 соединяем последовательно с вершинами 1,2.

......

Вершину i соединяем последовательно с вершинами i-1, i-2,...,1.

......

и так до тех пор, пока хватит проводков.

[Назад]

Алгоритм нахождения второго минимального расстояния между двумя вершинами:

По алгоритму Дейкстры находим кратчайший путь между начальной вершиной N и конечной K, состоящий из дуг a₁, ..., a_s. Во втором по длине кратчайшем пути из N в K не будет по крайней мере одного из ребер a_i. Поэтому алгоритм нахождения этого второго пути будет следующим:

Для i от 1 до s повторять
удалить из графа ребро (дорогу) a_i;
найти кратчайший путь из N в K в новом графе;
если его длина меньше рекордной минимальной длины, полученной ранее,
то запомнить текущий путь и его длину как рекорд;
восстановить в графе ребро (дорогу) a_i;
конец_для;