Окулов.Программирование.в.алгоритмах. По вопросам приобретения обращаться

• Название: По вопросам приобретения обращаться
• Анкор: Окулов.Программирование.в.алгоритмах.pdf
• Дата: 26.04.2017
• Размер: 5.46 Mb.
• Имя файла: Окулов.Программирование.в.алгоритмах.pdf
• Тип: Документы; #5718
• страница: 20 из 26

40 90
100 1000000000 15

278 6. Избранные задачи по программированию ния границ не изображены. Границы с номерами 0 и 3 соответ- ствуют предельным значениям.
Пусть есть два интервала. о 1 2 3
Различные варианты разме-
•
6 ч о щения интервалов показаны на следующих рисунках.
Кружками большего размера отмечены границы второго
6 ч 6
интервала. Можно продол- жить рисование: много отрез-
2 я
5
ков, интервалы, начинающи-
•
еся в одной точке и т. д., но эти рисунки будут только подтверждать идею. Если отсортиро- вать все границы в порядке возрастания, то белые участки после всех перекрашиваний начинаются с четных номеров границ.
12. «Отрезки». На прямой линии расположено N
отрезков. Из них нужно выбрать наибольшее количество по- парно не пересекающихся. Отрезки пересекаются, если они имеют хотя бы одну общую точку.
Входные данные. В первой строке файла (o.in)
записано число N — количество отрезков. В каж- дой из последующих строк заданы координаты отрезка.
Выходные данные. В выходной файл (o.out) за- писываются координаты концов отрезков (целые числа из диапазона Integer). Каждый отрезок в от- дельной строке.
Указание. Попытки решения задачи перебор- ными методами не имеют успеха. Сгенерировать все возможные подмножества множества из 500 элементов при любых эвристических приемах сокращения перебора не реаль- но, поэтому следовало сразу искать другое решение. Задача от- носится к классу задач, решаемых с помощью «жадных» алго- ритмов. Суть: сортируем отрезки по значениям правых концов,
а затем последовательно идем по отсортированным отрезкам и берем в качестве следующего отрезка такой первый отрезок, у которого правая граница больше левой границы текущего от- резка. Основной фрагмент реализации имеет вид:
Const
Var A:Array[0..NMax,1..2] Of Longlnt;
Procedure Solve;
Var
Пример.
0.
3 2
1 4
in
5 3
6 1
4 3
6

Избранные олимпиадные задачи по программированию 279
Begin
For
To N Do
If A[i,l]>t Then Begin
'
End; { *Если левая граница больше значения t, то
включаем отрезок в решение и присваиваем
переменной t значение правой границы
отрезка. *}
End;
Обоснуйте правильность его работы.
13.
Имеется ветка метро, станции которой прону- мерованы по порядку числами 1 (центр), 2, ..., N
Из центра (станция с номером 1) и самой дальней станции (номер
N) одновременно отправляются два поезда.
Требуется выяснить, где и когда произойдёт встреча, если движение поездов удовлетворяет следующим условиям:
• на каждой из станций, кроме первой и последней, поезда стоят М часов;
• поезда разгоняются и тормозят мгновенно;
• во время движения поезда имеют одну и ту же скорость V;
• в случае, если поезда встречаются на станции, выдать са- мое раннее время встречи.
Входные данные. В первой строке файла задано число V — скорость поезда (в км/час). Во второй строке задано число М. В третьей строке за-
Пример.
p.in
5 2.5 2.0
дано число N — количество станций. В четвёртой строке задан набор чисел где число яв- ляется расстоянием от станции с номером (£-1) до станции с номером i (в километрах). Все числа,
кроме N, вещественные.
Выходные данные. В выходной файл (p.out) тре- буется записать время встречи (в часах, с одной цифрой после точки) и расстояние от места встречи до центра (с одной циф- рой после точки).
Указание. Задача не требует знаний специальных алгорит- мов. Можно решать путем моделирования движений того и другого поездов. Однако есть более простой способ. Общее время в пути (t) подсчитать несложно — сумма времен остано- вок на станциях и время перемещений между станциями (ско- рость — постоянная величина). Время встречи поездов равно
t/2, если оно не совпадает с моментом остановки. При встрече на какой-то станции требуется сделать небольшое уточнение.

280
Избранные
задачи по программированию
Кстати, задача значительно усложняется, если скорость поез- дов непостоянна (разгон, торможение, остальное по- стоянная скорость). В этом случае необходимо уметь очень ак- куратно решать квадратные уравнения. Вернемся к нашей задаче. Рассмотрим, как обычно, пример:
N=3 и расстояния 10.0 и 7.0. Общее время в пути 22 единицы. Поло- вина этого значения 11. Но к этому моменту времени второй поезд стоит на станции уже 4 единицы времени, а первый — 1
единицу. Значит, время встречи 11-1 или 10 единиц времени.
14. Имеется N
ламп, пронумерованных от 1 до
N. Каждая лампа может иметь два состояния — включена, вы- ключена. Четыре кнопки позволяют управлять лампами следу- ющим образом:
• кнопка 1 — при нажатии все лампы изменяют свое состо- яние на противоположное;
• кнопка 2 — при нажатии изменяется состояние всех ламп, имеющих нечетные номера;
• кнопка 3 — при нажатии изменяется состояние ламп,
имеющих четные номера;
• кнопка 4 — при нажатии изменяется состояние всех ламп, имеющих номера т. е. 1, 4, 7, ...
Первоначально все лампы включены. Имеется счетчик С
(1<С<10000), который учитывает суммарное число нажатий всех кнопок.
Требуется по значению числа С и конечному состоянию не- которых ламп определить все возможные, конечные, различ- ные конфигурации N ламп.
Входные данные. Файл Input.txt содержит четыре строки:
• количество ламп
• значение счетчика С;
• номера тех ламп, которые в конечной конфигурации включены;
• номера тех ламп, которые в конечной конфигурации вы- ключены.
Номера ламп в третьей и четвертой строках записываются через пробел, списки номеров ламп заканчиваются числом - 1 .
Выходные данные. В файл записываются все воз- можные конечные конфигурации (без повторений), каждая —
в отдельной строке. Конфигурация — это строка длины N
(первый символ — состояние первой лампы,
— состояние лампы), где 0 означает, что лампа выключена, а 1 —
включена.

Избранные
задачи по программированию
281
Пример.
Input.Txt
10 1
7 -1 0000000000 0110110110 0101010101
Примечание
Количество ламп, о которых известно, что в ко- нечной конфигурации они включены, меньше или равно 2. Гарантируется, что существует хотя бы одна конечная конфигурация для каждого входного файла.
Указание. Заметим, что перебирать все вариантов, при
— бесполезное заня- тие, попытаемся упростить задачу. Во-первых,
последовательное действие любых двух кнопок,
например 1-2, эквивалентно их действию в противоположном порядке, т. е. 2-1 (коммутативность). Во-вторых, последовате- льное применение какой-либо кнопки два раза подряд не изме- няет состояние лампочек. Поэтому любое значение С, большее
4, уменьшается на 2. Итак, нечетные С, большие 4, заменяются на С, равное 3, а четные С, большие 5, на С, равное 4. Остается перебрать различные варианты конечных конфигураций при
С<4, их всего 15 (1; 2; 3; 4; 1,2; 1,3; 1,4; 2,3; 2,4; 3,4; 1,2,3;
1,2,4; 1,3,4;
1,2,3,4), что, безусловно, не
Необходимо только не забыть о том, что, например, при С, равном 3, следу- ет проверять и конфигурации, получаемые при С, равном 1.
15. «Звездная ночь». Посмотрите на ночное небо, где светя- щиеся звезды объединены в созвездия (кластеры) различных форм. Созвездие — это непустая группа рядом расположенных звезд, имеющих соседями звезды либо по горизонтали, либо по вертикали, либо по диагонали. Созвездие не может быть частью другого созвездия.
Созвездия на небе могут быть одинаковыми. Два созвездия являются одинаковыми, если они имеют одну и ту же форму независимо от их ориентации. В общем случае число возмож- ных для созвездия равно восьми, как показано на рисунке.
II 3500

282
Избранные олимпиадные задачи по программированию
Ночное небо представляется картой неба, которая, в свою очередь, является двумерной матрицей, состоящей из нулей и единиц. Элемент этой матрицы содержит цифру 1, если это звезда, и цифру 0 — в противном случае.
Для заданной карты неба отметить все созвездия, используя при этом маленькие буквы. Одинаковые созвездия должны быть отмечены одной и той же буквой; различные созвездия должны быть отмечены различными маленькими буквами.
Для того чтобы отметить созвездие, необходимо заменить каждую единицу в созвездии соответствующей маленькой бук- вой.
Входные данные. Входной файл с именем starry.in содержит в первых двух строках ширину W и высоту Н матрицы, соот- ветствующей карте неба. Далее в этом файле следует Н строк, в каждой из которых содержится W символов.
Выходные данные. Файл starry.out содержит ту же самую матрицу карты неба, что и файл starry.in, только созвездия в ней отмечены так, как описано в условии задачи.
Ограничения:
карты неба)<100,
карты неба)< 100, 0<Число созвездий<500, 0<Число различных
1<Число звезд в каждом созвездии<160.
Пример
23 15 1
0 0
0 0
0 1
0 0
0 0
0 0
0 0
0 1
1 0
0 0
0 0
0 0
0 0
0 0
0 0
1 0
0 0
0 0
1 0
0 0
0 1
0 0
0 1
0 0
0 0
0 0
0 0
0 1
0 0
0 1
1 0
0 0
1 0
1 1
0 0
0 0
1 0
0 1
0 0
1 0
0 0
0 0
1 0
0 0
0 0
0 0
0 1
0 0
0 0
0 0
0 0
0 0
0 0
0 0
1 1
1 0
0 1
0 1
1 0
1 0
0 0
0 0
0 0
0 0
1 1
1 1
1 1
0
1 1
1 1
1
0
0
0
1 1
1 1
0 1
0 1
0 0
0 1
0 0
0 0
0 0
0 0
0 0
1 0
1 0
1 0
1 1
1 1
1 0
0 0
0 1
0
0
0
1
0
1 0
0 0
1 0
0 0
0 1
1 1
1 1
0 1
0 1
0
1 0
1 1
0 0
0 0
0 0
0 1
0 0
0 1
0 0
0 1
0 0
0 0
0 0
1 1
1 1
1 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
1 1
0 0
0 0
0 0
1 0
0 1
1 1
0 0
1 0
0 0
0 1
1 0
0 0
0 0
1 0
1 1
0 0
0 0
0 1
0 0
0 0
0 1
0 1
1 0
0 0
0 0
1
0
0
0
0
1 0
0 0
1 0
0 0
0 0
1 1
0 0
0 0
0 0
1 1
0 0
0 0
0 1
0 0
0 0
1 0

6. Избранные
олимпиадные задачи
программированию
283
starry.out
0 0
0
b
0 0
0 0
0 0
0 0
0
a a
0 0
0 0
0 0
0 0
0 0
0 0
0
a
0 0
0 0
0
b
0 0
0 0
g
0 0
0
a
0 0
0 0
0 0
0 0
0
g
0 0
0
а а
0 0
0
е
0
f f
0 0
0 0
b
0 0
а
0 0
е
0 0
0 0
0
b
0 0
0 0
0 0
0 0
е
0 0
0 0
0 0
0 0
0 0
0 0
0 0
е е
е
0 0
d
0
d d
0
d
0 0
0 0
0 0
0 0
0
d d
d d
d d
0
с с
с с
с
0 0
0
d d
d d
0
d
0
с
0 0
0
с
0 0
0 0
0 0
0 0
0 0
с
0
b
0
с
0
с с
с с
с
0 0
0 0
с
0 0
0
с
0
с
0 0
0
с
0 0
0 0
с с
с с
с
0
с
0
b
0
с
0
f f
0 0
0 0
0 0
0
с
0 0
0
с
0 0
0
b
0 0
0 0
0 0
с с
с с
с
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0
d d
0 0
0 0
0 0
а
0 0
е е
е
0 0
d
0 0
0 0
а а
0 0
0 0
0
е
0
d d
0 0
0 0
0
а
0 0
0 0
0
е
0
d d
0 0
0 0
0
а
0 0
0 0
е
0 0
0
d
0 0
0 0
0
а а
0 0
0 0
0 0
d d
0 0
0 0
0
а
0 0
0 0
b
0
Это один из возможных вариантов выходного файла для представленного выше входного файла.
Указание. Пусть карта описывается массивом А
Of Byte; где максима- льный размер карты). Вместо 1, описывающей звезду созвез- дия, элементу А в процессе обработки будем присваивать код
(ASCII) соответствующей буквы. Попробуем «набросать» об- щую логику.
For i :=1
N Do
For j : =1
М Do
If A[i,j]=l Then Begin
созвездия, начиная с клетки (i,j), по прин-
ципу обхода в ширину. Результат в переменной Work Star
(описание созвездия) и в переменной d (фиксируется от-
клонение влево от координаты j)>,

<Получение всех симметричных созвездий. Проверка
совпадения найденного созвездия с ранее
Результат - код ASCII
Если совпадения не
было, то полученное созвездие запоминается>;
<Пометка полученного созвездия кодом
End;
Подумаем об используемой оперативной памяти. Максима- льный размер карты — 100*100. Одно созвездие может исполь-

284
Избранные олимпиадные задачи по программированию
зовать всю карту, т. е. при описании созвездия необходимо «за- кладывать» максимальный размер 10000. С другой стороны,
созвездий может быть 26, итого требуется 260000 байт. Цифра большая. Необходимо сокращать, использовать побитовое хра- нение описаний созвездий. Делим на 8 и получаем 32500 байт,
что уже допустимо.
Определим структуры данных и сделаем первое уточнение логики решения.
Const
размер карты.*}
различных созвездий. *}
код буквы а. *}
Dx: Array
.8] Of
0, 0, 1, 1,
{*Приращения, используемые
при обходе в ширину. *}
Dy:
.8] Of Integer=( 1,-1, 1,
0,-1, 1, 0,-1);
Type
0. . (MaxN+8) Div
Of
Byte;{*Карта отдельного созвездия,
используется побитовое хранение. *}
MasSt; N, M: Integer; End;
{*0писание созвездия. *}
Var A: Array [ 0.
0..MaxN+l] Of Byte ;
карты. *}
N, M:
карты.*}
Rs:
Of
для
хранения различных созвездий. *}
Sc: Integer;{*Число различных созвездий. *}
При таком определении структур данных основная процеду-
ра Solve имеет вид.
Procedure Solve;
Var i , j , d : Integer;
Star;
c: Byte;
Begin
For i:=l To N Do
For
M Do
If A[i, j]=l Then Begin
в ширину.
d - отклонение влево от начала точки
Стандартный обход в ширину
должен быть модифицирован так, чтобы
подсчитывался размер созвездия -
прямоугольник наименьшего размера,

6. Избранные
задачи по программированию
285
Пример.
input.txt
5 1
А
2
АВ
3 2
СА
2
ВА
data.txt
А
В
А
В
А
С
А
В
А
А
В
С
В
в который помещается
Кроме
того, требуется выполнять битовую
кодировку созвездия. *}
на совпадение
с ранее полученными созвездиями. *}
SetUp
созвездия
буквой алфавита. *}
End;
End;
Дальнейшее уточнение логики предоставим читателю. Са- мая трудоемкая её часть — проверка созвездий на совпадение.
16. «Самый длинный
Структура некоторых био- логических объектов представляется последовательностью их составляющих. Эти составляющие обозначаются заглавными буквами. Биологи интересуются разложением длинной после- довательности в более короткие последовательности. Эти корот- кие последовательности называются примитивами. Говорят,
что последовательность S может быть образована из данного множества примитивов Р, если сущест- вует п
в Р, таких, что их кон- катенация (сцепление)
равняется S. При конкатенации примитивы записываются последовательно без разделительных пробелов.
Некоторые примитивы могут встречаться в конка- тенации более одного раза, и не обязательно все примитивы должны быть использованы.
Например, последовательность АВАВАСАВААВ
может быть образована из множества примитивов
{А, АВ, ВА, СА, ВВС}. Первые символов строки S
будем называть префиксом строки S длины К.
Требуется написать программу, которая для за- данного множества примитивов Р и последовате- льности Т определяет длину максимального пре- фикса последовательности Т, который может быть образован из множества примитивов Р.
Входные данные расположены в двух файлах.
Файл input.txt описывает множество примитивов
Р, а файл data.txt содержит последовательность
Т, требующую проверки. Первая строка input.txt
содержит п — количество в множест- ве Р
Каждый примитив задан в двух последовательных строках. Первая из них содер- жит длину L примитива а вторая —
output.txt
11

286
Избранные
задачи по программированию
строку из заглавных букв (от 'А' до 'Z') длины L. Все п прими- тивов различны. Каждая строка файла data.txt содержит одну заглавную букву в первой позиции. Файл data.txt заканчивает- ся строкой с символом '.' (точка) в первой позиции. Длина по- следовательности не меньше 1 и не больше 500 000.
Выходные данные. В первую строку файла output.txt требу- ется записать длину максимального префикса последовательно- сти Т, который может быть образован из множества Р.
Указание. Введем переменную с именем типа для хранения значения длины максимального префикса.
Ответим на вопрос: как задействовать примитив в сравнениях?
Если сравнение начинается с первой позиции последовательно- сти символов, то понятно — примитивы начинаются с этой же буквы. А если нет? Мы в какой-то позиции последовательности с номером t. Новое подмножество примитивов для сравнения выбирается только в том случае, если МахРг равно
Это означает, что закончено сравнение по какому-то примитиву, он полностью входит в конкатенацию, и есть полное право под- ключать к процессу новое подмножество примитивов. Если не равно МахРг, то процесс сравнения символов последователь- ности продолжается только с символами ранее выделенных примитивов. В том случае, когда множество выделенных при- митивов пусто, обработка закончена. То, что мы нашли, — зна- чение МахРг — ответ задачи. А в какие моменты времени из- меняется значение МахРг? Как только заканчивается сравнение хотя бы с одним примитивом, изменяем значение
МахРг. Для хранения «активных» примитивов следует ввести структуру данных Р — массив из М строк и MaxN плюс один столбец
of Integer). Почему
Нет необ- ходимости хранить предысторию процесса сравнения на боль- шую глубину, ибо максимальная длина примитива М. В эле- менте же нулевого столбца Р фиксируем количество записей в соответствующую строку. С этой структурой данных следует предусмотреть следующие операции: вставка элемента (откры- тие нового примитива, перевод его в состояние «активный»);
исключение элемента (сравнение очередного символа активно- го примитива и строки дало отрицательный результат); сжатие данных (если действительно для хранения активных примити- вов выбран массив).
17. Дан текст, набранный символами одинаковой ширины
(включая пробелы). Длина строки при печати этим шрифтом на листе бумаги равна S. Назовем пустой последовательность про- белов между соседними словами в строке, а также от начала