Пусть при записи этих N пар встретилось всего K различных символов, которые образуют множество X.
Идея решения задачи состоит в последовательном присвоении каждому символу s из Х номера, который определяет количество Р(s) элементов, предшествующих ему, с учетом свойства транзитивности (из (с,b) и (b,а) следует (с,а)). Это осуществляется следующим образом:
Первоначально предполагается, что каждому символу не предшествует ни один символ, т.е. Р(s)=0 для любого s.
При просмотре очередной пары (x,y) символу y присваивается большее из значений P(x)+1, P(y).
Очевидно, что при первом просмотре всех пар из входной последовательности определятся все упорядоченные цепочки длины 2, т.е. состоящие из 2 элементов. Поэтому номера некоторых элементов будут как минимум 1. При каждом из следующих просмотров входной строкивозможно несколько вариантов.
Не произошло изменения ни одного из номеров символов. Если при этом номера символов различны и лежат в пределах от 0 до N-1, то эта нумерация определяет полный порядок. Иначе порядок неполный.
Номер некоторого символа превысил N-1. Это произошло потому, что рост номеров неограничен, т.е. осуществляется циклически. Следовательно порядок противоречив.
Легко понять, что число просмотров не превысит N.
Вариант 2. Рассмотрим следующий метод:
Заведем массивы
A: array [1..N,0..N] of byte
и
Cnt: array[1..N] of byte;
сначала A[i,0]=0 и Cnt[i]=0 для любого i.
Пусть среди 2*N символов, образующих N пар, есть ровно K различных. Перенумеруем их от 1 до K. Будем считать, что пары составлены не из символов, а из соответствующих им номеров.
В i-ю строчку матрицы A будем заносить те элементы, которые являются вторыми элементами в парах с первым элементом i. В A[i,0] будет храниться текущее число этих элементов. Обработка пары (i,j) будет выглядеть следующим образом:
A[i,0]:=A[i,0]+1; {количество увеличилось на 1}
A[i,A[i,0]]:=j; {вставляем j на первое свободное место}
В Сnt[i] будет храниться число пар, у которых элемент i является вторым в паре.
Если все символы без повторений, использованные для записи пар, можно выписать в цепочку в порядке предшествования, то у этой цепочки должен быть первый символ s, у которого нет предшествующего и которому соответствует Cnt[s]=0.
Может быть несколько ситуаций:
1. Такой элемент единственный - следовательно, это начало цепочки. Отбрасываем s из цепочки и убираем все пары с первым элементом s из множества пар, корректируя при этом массив Cnt:
for i:=1 to A[0,s] do
Сnt[A[s,i]]:=Cnt[A[s,i]]-1;
после чего опять ищем элемент s, у которого нет предшествующего и которому соответствует Cnt[s]=0.
2. Таких элементов несколько, следовательно, между ними нельзя определить порядок предшествования - система неполна.
3. Таких элементов нет - следовательно, система противоречива.
Для решения этой задачи используем структуру данных 'список'. Каждый элемент списка указывает на следующий за ним элемент (другими словами - хранит информацию о расположении следующего элемента).
a). Заведем массив A из N ячеек - по числу людей в круге. В каждую из ячеек A[i] занесем номер стоящего следующим за i-ым человека. Первоначально A[i]=i+1, i=1,...,.N-1, A[N]=1. Начиная счет от текущего человека (человека с номером IndTek, с самого сначала IndTek=1) будем делать ход - отсчитывать M ячеек, двигаясь по кругу в поисках человека, который должен выйти из круга. С учетом определения массива A это будет выглядеть следующим образом:
{IndTek - это номер человека, с которого начинается счет}
for i:=1 to M-1 do {Отсчитываем M человек, начиная с IndTek}
begin
IndPred:=IndTek; {в IndPred сохраняем номер текущего человека в круге}
IndTek:=A[IndTek]; {и вычисляем номер следующего за ним}
end;
После выполнения этого цикла в переменной IndTek будет номер человека, на котором остановился счет (т.е. номер человека, который покинул круг), а в переменной IndPred - номер предшествующего ему человека в круге.
Удалим человека с номером IndTek. Для этого мы просто изменим ссылку A[IndPred] у предшествующего ему человека так, чтобы он указывал не на IndTek, а на следующего за IndTek, т.е. на A[IndTek], и новый отсчет M-того человека начнем со следующего за удаленным:
A[IndPred]:=A[IndTek];
IndTek:=A[IndTek];{Новый номер начального человека}
Все вышеописанные операции мы будем повторять до тех пор, пока в круге не останется одного единственного человека, т.е. до тех пор, пока A[IndTek] не станет равным IndTek, что означает, что следующим за человеком с номером IndTek является он сам.
Полностью весь фрагмент программы будет выглядеть так:
{Инициализация массива A}
<P>for i:=1 to N-1 do
A[i]:=i+1;
A[N]:=1;
{IndTek - это номер человека, с которого начинается счет}
IndTek:=1;
while A[IndTek] <> IndTek do
begin
for i:=1 to M-1 do {Отсчитываем M человек, начиная с IndTek}
begin
IndPred:=IndTek; {в IndPred сохраняем номер текущего человека в круге}
IndTek:=A[IndTek]; {и вычисляем номер следующего за ним}
end;
A[IndPred]:=A[IndTek];
IndTek:=A[IndTek]; {Новый номер начального человека}
end;
writeln('Номер последнего оставшегося человека ',IndTek);
Решения пункта b).
Будем считать, что человек с номером N+i - это то же самое, что и человек с номером i.
Предположим, что как и в пункте a), что мы начали счет с первого человека, выбрасывали из круга M-того, и последний оставшийся в круге человек имеет номер K. Очевидно, что если бы мы начали счет со второго человека, то последний оставшийся в круге человек имел бы номер K+1, ..., если с j-го, то K+j-1.
Если номер оставшегося человека L, то из равенства L=K+j-1 определяем номер j первого человека (если j<=0, то заменим j на j+N, считая как и раньше, что человек с номером N+j - это то же самое, что и человек с номером j).
Будем моделировать сложение полоски, затем пронумеруем получившуюся колонку клеток числами от 1 до 2n, после чего распечатаем числа, приписанные первой, второй, ..., 2n-ой клетке исходной полоски.
Сначала создаем двусвязный список, состоящий из 2k элементов. Поле next будет указывать на элемент находящийся под данным, а поле last - на элемент находящийся над данным. Для верхнего элемента last=0, а для нижнего next=n+1, где n-общее число элементов. Вначале длина верхней полоски равняется n элементов, после первого сгибания их она станет n/2, после второго - n/4, и т.д. Пусть в данный момент длина верхней полоски есть cn элементов. Значит нам необходимо cn/2 правых элементов опустить под cn/2 левых. Для этого запустим цикл, который будет менять i от 1 до cn/2 и на каждом шаге помещать (cn-i+1)-ю колонку элементов под i-ю, при этом порядок элементов в (cn-i+1)-ой колонке меняется на противоположный. После каждого сгибания cn уменьшается вдвое. Так продолжаем до тех пор пока cn>1.
Программа (программы для задач 3 и 4 написаны В.Белым):
{$A-,B-,D-,E+,F-,I-,L-,N-,O-,R-,S-,V-}
{$M 65520,0,655360}
uses crt;
const
maxk = 13; {Максимальное значение для k}
type
input = record
last,next,new : word;
end;
var
k,i,j,n,cn,half : word;
m : array[1..1 shl maxk] of input;
Procedure concat(a,b : word);
var i,j,nj : word;
begin
i:=a;while m[i].next<>n+1 do i:=m[i].next;
j:=b; while m[j].next<>n+1 do j:=m[j].next;
while j<>0 do
begin
nj:=m[j].last; m[i].next:=j; m[j].last:=i; i:=j; j:=nj;
end;
m[i].next:=n+1;
end;
begin
Write('Enter k...');readln(k);
n:=1 shl k; {Определение длины полоски}
for i:=1 to n do{Начальные значения}
with m[i] do
begin
last:=0;
next:=n+1;
new:=0;
end;
cn:=n;
while cn>1 do {Сгибание полоски}
begin
half:=cn div 2;
for i:=1 to half do concat(i,cn-i+1);
cn:=half;
end;
j:=1;
for i:=1 to n do {Нумерация клеток}
begin
m[j].new:=i; j:=m[j].next;
end;
for i:=1 to n do write(m[i].new:5);
writeln;
end.
Попробуйте найти формулу и написать программу, которая без моделирования складывания полоски по номеру клетки выдавала бы ее номер.
Решение этой задачи аналогично решению предыдущей задачи со сгибанием полоски с той лишь разницей, что тут будет поочередно производится два сгибания: сначала правая половина под левую, а затем нижнюю под верхнюю
{$A-,B-,D-,E+,F-,G-,I+,L-,N-,O-,R-,S-,V-,X-}
{$M 16384,0,655360}
uses crt;
const
maxk = 6;
type
input = record
last1,last2,next1,next2,new : word;
end;
var
k,i,j,i1,i2,j1,j2,nj1,nj2,n,n1,cn,half : word;
m : array[1..1 shl maxk,1..1 shl maxk] of input;
Procedure concat(a,b,c,d : word);
var i1,i2,j1,j2,nj1,nj2 : word;
begin
i1:=a; i2:=b;
while (m[i1,i2].next1<>n+1) and (m[i1,i2].next2<>n+1) do
begin
i1:=m[i1,i2].next1; i2:=m[i1,i2].next2;
end;
j1:=c; j2:=d;
while (m[j1,j2].next1<>n+1) and (m[j1,j2].next2<>n+1) do
begin
j1:=m[j1,j2].next1; j2:=m[j1,j2].next2;
end;
while j1<>0 do
begin
nj2:=m[j1,j2].last2; nj1:=m[j1,j2].last1;
m[i1,i2].next1:=j1; m[i1,i2].next2:=j2;
m[j1,j2].last1:=i1; m[j1,j2].last2:=i2;
i1:=j1; i2:=j2; j1:=nj1; j2:=nj2;
end;
m[i1,i2].next1:=n+1; m[i1,i2].next2:=n+1;
end;
begin
Write('Введите k...');readln(k);
n:=1 shl k; {Определение числа клеток в одной строке или столбце}
n1:=n*n; {Определение числа клеток в матрице}
for i:=1 to n do
for j:=1 to n do with m[i,j] do
begin
last1:=0; next1:=n+1;
last2:=0; next2:=n+1;
new:=0;
end;
cn:=n;
while cn>1 do {сгибание матрицы}
begin
half:=cn div 2;
for i:=1 to half do {сгиб по вертикали}
for j:=1 to cn do concat(j,i,j,cn-i+1);
for i:=1 to half do {сгиб по горизонтали}
for j:=1 to half do concat(i,j,cn-i+1,j);
cn:=half;
end;
j1:=1;j2:=1;
for i:=1 to n1 do {Назначение клеткам новые номера}
begin
m[j1,j2].new:=i;
nj1:=m[j1,j2].next1; nj2:=m[j1,j2].next2;
j1:=nj1; j2:=nj2;
end;
for i:=1 to n do {Вывод результатов}
begin
for j:=1 to n do write(m[i,j].new:8);
writeln;
end;
end.
Идея решения основывается на использовании очереди. Вначале в очередь помещается элемент, определяющий исходное положение шахматного коня, а соответствующая клетка поля помечается как посещенная.
На каждом из следующих шагов алгоритма (пока очередь не пуста или не помечена конечная клетка) выполняются следующие действия.
Из очереди извлекается очередной элемент, который определяет некоторую позицию (x,y).
Находятся клетки в пределах поля, которые достижимы из (x,y) одним ходом шахматного коня, и которые еще не помечены.
Элементы, соответствующие найденным клеткам, помещаются в очередь, а клетки помечаются как посещенные.
При этом вначале все клетки должны быть непомечены, а метку желательно ставить такую, чтобы можно было восстановить путь между полями.
Для этого метку поля можно определить как позицию поля, из которой она была помечена.
Необходимо организовать стек для позиций элементов, которые претендуют быть большими. Для каждого текущего элемента выталкивать из стека все позиции, на которых стоят элементы меньше текущего и заменить их текущим. Затем позицию текущего элемента поместить в стек. После просмотра всех элементов в стеке будут стоять позиции элементов, которые надо заменить на ноль.
Идея решения основывается на использовании очередей. Но если реализация движения от остановки к остановке по одному маршруту аналогична технике, используемой в задаче 6, то возможность изменения маршрутов несколько усложняет структуру элемента в очереди.
Для этого для каждой остановки введем тройку чисел (О,М,За), где О - номер остановки, М - номер маршрута, За - величина задержки. При выборе очередного элемента из очереди возможны 2 ситуации.
Продолжается движение по тому же маршруту. В этом случае в очередь заносятся тройки типа (О',М,За), где О' - номер остановки, соседней О, в маршруте М, а За=0.
2.Изменяется маршрут. В этом случае в очередь заносятся тройки типа (О,М',За), где М' - номер измененного маршрута, За=3 (задержка на пересадку).
При этом новые тройки порождаются только тройками с задержкой, равной 0. В случае тройки с ненулевой задержкой она вновь помещается в очередь с уменьшенным на 1 значением задержки.
Будем хранить в массиве A[1..N,1..2] координаты тех клеток, где король уже был. Возьмем N достаточно большим, N=500. A[i,1] - иксовая, A[i,2] - игрековая координата клетки. Пусть в переменной DLN хранится количество уже сделанных ходов (т.о. в массиве A после хода номер i будут заняты клетки с первой по i-ую).
Результаты очередного хода заносим в массив A на первое свободное место (т.е. на место с индексом DLN+1), увеличиваем количество сделанных ходов DLN:=DLN+1, и проверяем, совпадает ли хоть одна из позиций, на которых король уже был, с текущей позицией:
for i:=1 to DLN-1 do
if (A[i,1]=A[DLN,1]) and
(A[i,2]=A[DLN,2]) {проверка совпадения}
then begin
writeln('совпадение на ходах ',DLN,' и ',i);
halt; {останов}
end;
Давайте посмотрим, как можно вводить ходы короля. Он из клетки k может пойти на 8 соседних позиций.
В массив заносятся смещения по x- и y-координатам, соответствующие направлениям от 1 до 8. Координаты короля после сделанного хода вычисляются по формулам
Монеты лежат на N+M позициях. Пронумеруем эти позиции по порядку по контуру от 1 до N+M.
Заведем массив A из N+M ячеек. Первоначально все ячейки нулевые. Начиная счет от первой ячейки, будем делать ход - отсчитывать S ячеек (считаем, что за N+M-ым элементом следует непосредственно 1-ый элемент массива) и заменять в этой ячейке число i на число 1-i (т.е. 0 на 1, а 1 на 0). После k-того хода остановимся.
Рассмотрим возникшую ситуацию. После каждого хода переворачивается одна монета, при этом разность количества монет, лежащих гербами вверх и количества монет, лежащих гербами вниз либо увеличивается, либо уменьшается на 2. Например, если переворачивается монета, лежащая гербом вверх, то при этом увеличивается на 1 количество монет гербом вниз и уменьшается на 1 количество монет гербом вверх.
Предположим, что после k ходов в массиве A стало p единиц т.е. p монет, по сравнению с начальным положением, будут перевернуты после k-ого хода.
В случае, если L>=N, то (L-N) монет, которые лежали гербами вниз, должны после k-ого хода быть перевернуты гербами вверх. (Если p<(L-N), то это, очевидно, невозможно сделать). Среди оставшихся p-(L-N) перевернутых монет должна быть половина гербами вверх и половина - вниз, чтобы при перевороте суммарное число монет гербами вверх и вниз не изменилось. Следовательно, число p-(L-N) должно быть четным, иначе условию задачи удовлетворить нельзя. Пусть p-(L-N) = 2v. Должно быть, очевидно, v<=N, v+(L-N)<=M.
Итак, в случае L>=N, если не выполняется хотя бы одно из неравенств
p-(L-N)=2v>=0,
v<=N,
v+(L-N)<=M,
то преобразование начальной конфигурации в конечнуюневозможно.
Иначе на (L-N) мест, помеченных в массиве A единицами, выставляем монеты гербами вниз. На оставшиеся 2v=p-(L-N) помеченных единицами позиций кладем v монет гербами вниз и v гербами вверх в произвольном порядке. На остальные позиции кладем оставшиеся монеты опять же в произвольном порядке, чтобы в общей сложности было N монет гербами вверх и M - гербами вниз.
Но мы еще не учли тот факт, что счет начинается с первой монеты гербом вверх:
а) Если в массиве A первый элемент нулевой, то в случае, если среди (N+M)-p монет есть хоть одна гербом вверх (что эквивалентно выполнению условия N-v>0), то ее и кладем в первую позицию. Если все (N+M)-p монеты - гербом вниз (т.е. N-v=0), то размещение монет невозможно.
б) Если же A[1]=1, то среди p монет должна быть по крайней мере одна, которую необходимо положить гербом вверх, иначе, опять же, размещение невозможно.
Как и в задаче 10 заполняем сначала массив A нулями, перенумеровываем по порядку N+M позиций от 1 до N+M. Начиная с первой позиции (серая мышка) делаем ход - отсчитываем S нулевых позиций по порядку (считаем, что позиция, где сидела съеденная мышка, помечается единицей, несъеденная мышка - нулем; за N+M-ой позицией располагается первая) и выставляем в соответствующую позицию 1 мышка съедена. Далее отсчет начинаем со следующей за съеденной мыши. (Для более быстрого поиска S-той мышки среди оставшихся в круге можно использовать список, описанный в задаче 2).
Делаем P=(N+M)-(K+L) ходов.
По условию задачи в первой позиции сидит серая мышка. Есть A[1]=1 (первая мышь была съедена), то в оставшихся P-1 единичной позиции в произвольном порядке расставляем N-K-1 серых и M-L белых мышей. В оставшихся незанятыми позициях рассаживаем опять же в произвольном порядке оставшихся мышей.
Если A[1]=0, и K=0, то начальной расстановки не существует (все серые мыши съедены, а должна остаться еще одна в первой позиции); если же K<>0, то в единичных позициях рассаживаем N-K серых и M-L белых мышей, а в оставшихся позициях - в первую позицию серую мышь, а во все остальные - белых и серых в произвольном порядке.
Идея решения состоит в последовательном определении множества клеток, принадлежащих тому же куску, что и некоторая фиксированная клетка.
Начиная с некоторой непомеченной клетки (начальной), которая помечается, помечаются все клетки, имеющие с ней общую сторону. Затем, используя вновь помеченные клетки, помечается множество клеток, имеющих с ними общую сторону и т.д., пока на некоторой итерации не будет помечено ни одной новой клетки. Множество клеток, помеченных таким образом, и составляет единый кусок листа максимального размера.
Для подсчета общего количества кусков необходимо подсчитать количество клеток, выбранных в качестве начальных. Новая начальная клетка выбирается из множества клеток, не помеченных на предыдущих итерациях. Для хранения вновь помеченных клеток можно использовать очередь или стек, а пометку клеток можно проводить в матрице размера N*M.
Проще всего взять и промоделировать раскладку карточек: берем стопку из n черных и белых карточек и начинаем расклад как говорится в задаче - первая на стол, вторая под низ, третья на стол, и т.д. при этом первой выложенной карточке приписывается белый цвет, а каждой последующей - цвет, не совпадающий с цветом предыдущей карточки. Повторяет так, пока не найдем раскраску всех n карточек.
Для этой задачи возьмем такую структуру данных как список. У списка есть начало и конец, и каждый элемент его указывает на следующий за ним элемент. Будем считать , что у последнего элемента списка указатель на следующий за ним равен 0. Список можно представлять массивом. Например, если в списке 4 элемента, то массив будет выглядеть так:
т.е. за первым элементом находится A[1]=2 элемент, ..., за 4-ым - A[4]=0 (т.к. 4-ый элемент списка последний).
Пусть у нас есть указатель на начальный элемент списка и на последний (BEG и FIN соответственно). В списке n элементов.
Рассмотрим процедуру удаления элемента из начала списка (это соответствует переносу карточки на стол):
BEG:=A[BEG]; {теперь новый первый элемент списка - второй элемент старого списка}
Рассмотрим операторы перестановки элемента из начала списка в конец (это соответствует перемещению карточки сверху стопки под низ ее):
A[FIN]:=BEG; {следующей за последним элементом - бывший первый}
FIN:=BEG; {меняем ссылку на последний элемент}
BEG:=A[BEG] {новый первый элемент}
A[FIN]:=0 {корректировка ссылки у последнего элемента}
Фрагмент программы будет выглядеть так:
for i:=1 to N-1 do A[i]:=i+1;
A[N]:=0; {установка ссылок в списке}
BEG:=1; FIN:=N;
COLOR:=1; {белый цвет = 1, черный = 0}
while A[BEG]<>0 do
{пока первый элемент не является} {одновременно и последним}
begin
BEFORE:=BEG; {сохраняем индекс начала списка}
BEG:=A[BEG]; {удаляем первый элемент из списка}
A[BEFORE]:=COLOR; {раскрашиваем удаленный элемент}
{в нужный цвет}
COLOR:=1-COLOR; {меняем цвет}
A[FIN]:=BEG; {переставляем элемент из}
FIN:=BEG; {начала списка в конец}
BEG:=A[BEG];
A[FIN]:=0
end;
A[BEG]:=COLOR; {раскрашиваем последний элемент}
{списка}
for i:=1 to N do {распечатка цветов}
if A[i]=0
then writeln('элемент',i,' - черный')
else writeln('элемент',i,' - белый');
Для реализации данного алгоритма нам понадобится структура данных "очередь". Очередь в программировании, как и очередь в магазине, имеет начало и конец. Если приходит новый элемент, то он становится в конец очереди, если необходимо взять элемент из очереди, то он берется из ее начала. Очередь будем представлять в виде массива. Пусть у нас есть индекс первого - BEG и последнего FIN элементов очереди (если очередь пуста, то BEG=FIN+1; сначала же BEG=1, FIN=0).
Очередь опишем так: var Queue=array[1..MaxQ] of element;
Тут MaxQ - максимальное число элементов в очереди, element какой-то тип данных. В задаче ниже в качестве element можно взять такой
type element = record
x: byte;
y: byte;
end;
где element - это запись, состоящая из x-овой и y-овой координаты элемента матрицы A=array[0..M+1,0..N+1] of integer. Индексы матрицы принимают такое значение из-за того, что мы будем окаймлять матрицу нулевыми элементами (так будет проще проверять выливание за край фигуры).
С очередью можно проводить операции:
вставка в очередь InQueue,
удаление из очереди OutQueue.
Procedure InQueue (x : element);
begin
FIN:=FIN+1; {на первое свободное место}
Queue[FIN]:=x; {ставим элемент x}
end;
Procedure OutQueue (var x : element);
begin
x:=Queue[BEG]; {берем первый элемент}
BEG:=BEG+1; {и изменяем указатель}
{на следующий за ним}
end;
Находим максимальный элемент D в матрице A. Пока все элементы в матрице A не станут равны D, повторяем следующую последовательность действий:
а) Находим в матрице минимальный ненулевой элемент z (если их несколько, то берем любой из них), и заносим его в очередь (очередь сначала пустая). Если этот минимальный ненулевой элемент z=D, то СТОП.
Сначала считаем, что p=D - это минимальный граничный элемент области, заполненной элементами со значением z.
б) Для каждого еще не просмотренного элемента очереди (пусть в матрице этот элемент находится в позиции (i,j)) повторяем следующее:
Для каждого соседа (сверху, снизу, справа, слева) данного
элемента (i,j) проводим проверку-просмотр:
ЕСЛИ (сосед <> z)
ТО P=min{P,сосед}
ИНАЧЕ ЕСЛИ сосед еще не просмотрен
ТО координата соседа - в очередь (в очереди появился еще один непросмотренный элемент)
т.е. мы ищем минимальный окаймляющий элемент области, заполненной элементами со значением z.
Фрагмент программы поиска:
var Delta = array [1..4,1..2] of
integer = ((0,1),(1,0),(-1,0),(0,-1));
{Delta - возможные смещения соседних клеток от текущей клетки}
Current, neighbor : element;
z : integer;
....
{Будем обозначать то, что элемент в матрице уже просмотрен}
{умножением его на -1}
{минимальный ненулевой элемент матрицы имеет значение z}
while BEG<>FIN+1 do begin
OutQueue(Current);
for i:=1 to 4 do begin
neighbor.x:=Current.x+Delta[i,1], neighbor.y:=Current.y+Delta[i,2],
if A[neighbor.x,neighbor.y]=z
then InQueue(neighbor)
else p:=min(A[neighbor.x,neighbor.y],p); end;
end;
Если в очереди нет больше непросмотренных элементов, то, если p<z (случай, когда данная область имеет "слив" за границы матрицы) в матрице во все просмотренные элементы из очереди заносим значение D (делаем их равными накопленному значению, чтобы больше их не рассматривать).
Если же p>z, то высчитываем, сколько воды поместится в "бассейн" с глубиной дна z и с высотой ограждающего бордюра p:
Объем = (p-z)* количество просмотренных элементов в очереди.
Добавляем полученный объем к ранее найденному объему воды,
заполняющему матрицу до высоты x.
Заполняем в матрице элементы, соответствующие просмотренным элементам из очереди, значением p ("Доливаем" воды в "бассейн" до уровня p).
Переход на пункт а).
Суммарный полученный объем воды и является искомым.
Окаймление матрицы, упомянутое выше, может выглядеть следующим образом: матрица [1..N, 1..M] окаймляется нулями так: вводятся дополнительные нулевые 0-ая и (N+1)-ая строки и 0-ой и (M+1)-ый столбцы
var A: array[0..N+1,0..M+1] of byte;
{ввод и окаймление нулями}
for i:=1 to N do begin
A[i,0]:=0; A[i,M+1]:=0;
for j:=1 to M do read(A[i,j]);
end;
for j:=0 to M+1 do begin
A[0,j]:=0; A[N+1,j]:=0;
end;
Легко заметить, что для существования решения необходимо проводить людей от самого левого входа к самому левому выходу,от самого правого - к правому и т.д. Поэтому приведем решение только для случая б).
Основная стратегия человека, вошедшего в самый левый вход, состоит в прохождении лабиринта, используя наиболее левые свободные места лабиринта, т.е. он должен двигаться, держась правой рукой за "стенку" лабиринта. Этот процесс можно формализовать следующим образом. Находясь в очередной позиции лабиринта, он должен помнить, с какой стороны он пришел сюда (слева, справа, сверху, снизу), и, руководствуясь этой информацией, вобрать следующее наиболее предпочтительное направление в новую позицию (куда он может пойти и где еще не был). При этом удобно использовать стек, в верхушке которого находятся координаты текущей позиции и направление, по которому в нее пришли. При этом все посещенные клетки метятся. Легко заметить, что если в позицию попали сверху, то наилучшим направлением будет налево, затем вниз, направо, и наконец назад (вверх). Аналогично можно определить наилучшие направления для других случаев.
Эта стратегия повторяется каждым из людей, при этом позиции, помеченные предыдущими людьми, считаются запрещенными для следующих.
Так как могут быть потребованы подписи лишь непосредственных подчиненных, то для любого разумного способа получения лицензии подпись всех подписавших чиновников, кроме первого, используются в одном и только одном наборе. Таким образом, мы можем определить стоимость подписи любого чиновника как минимум по соответствующим ему набором сумм стоимостей подчиненных и взятии для набора. Таким образом, мы получаем простой и эффективный рекурсивный алгоритм определения стоимостей чиновников.
Но у этой задачи есть маленький подводный камень, а именно, должно быть заведено глобальное множество уже пройденных чиновников, что исключает повторную обработку этих чиновников. Сложность алгоритма - линейна по суммарному числу элементов в наборе.
