- •Оценка эффективности алгоритмов
- •Целочисленная арифметика
- •Дано натуральное число. Выяснить является ли оно палиндромом, то есть читается справа налево и слева направо одинаково
- •Дано натуральное число. Выяснить соотношение между количествами двоек и пятерок в этом числе
- •Найти самую большую и самую маленькую цифры данного натурального числа
- •Выяснить образуют ли цифры натурального числа возрастающую последовательность
- •Формат выходного файла
- •Формат входного файла
- •Формат выходного файла
- •Формат входного файла
- •Формат входного файла
- •Формат выходного файла
- •Длинная арифметика
- •Выходные данные
- •Задачи Задача 52 Иностранные земли
- •Входные данные.
- •Выходные данные.
- •Формат входного файла
- •Формат выходного файла
- •Задачи Задача 56 Уравнение
- •Решение
- •Одномерные массивы
- •Базовые задачи на массивы
- •Задача 15 Сокращение одночленов
- •Входные данные:
- •Задача 16 Школьный субботник
- •Входные данные:
- •Входные данные:
- •Выходные данные:
- •Примеры
- •Задача 27 Решение систем линейных уравнений на Pascal
- •Двумерные массивы
- •Описание массива
- •Способы создания массива
- •Задачи:
- •Задача 5 Малыш играет в "Морской бой 2" Малыш играет в "Морской бой". Поле для игры представляет собой квадрат
- •Входные данные
- •Выходные данные
- •Задача 26 Шарик в лабиринте
- •Примечание
- •Задача 27 Блохи
- •В первой строке входного файла Input.Txt находится 5 чисел, разделенных пробелом: n, m, s, t, q.
- •Входные данные
- •Выходные данные
- •Примеры
- •Задача 34 Магический квадрат
- •Формат входного файла
- •Формат выходного файла
- •Входные данные
- •Выходные данные
- •Входные данные
- •Выходные данные
- •Рекурсия
- •Комбинаторика
- •2.5. Генерация комбинаторных объектов
- •Множество всех подмножеств
- •Перестановки
- •Размещения
- •Перестановки с повторениями
- •Сочетания с повторениями
- •Перебор
- •Символ o()
- •Отсечение по времени
- •Рассмотрим несколько олимпиадных задач.
- •Шарик в лабиринте
- •Задача 1. Шарик в лабиринте
- •Задача 3 Цепочка слов
- •Входные данные
- •Выходные данные
- •Примеры
- •Формат входного файла
- •Формат выходного файла
- •Примеры
- •Динамическое программирование
- •Задача 8 Гвоздики
- •Задача 13 Лесенки
- •Задача 18 Свинья-копилка
- •Входные данные
- •Выходные данные
- •Задача 13 Лесенки Лесенкой называется набор кубиков, в котором каждый более верхний слой содержит кубиков меньше, чем предыдущий.
- •Задача 18 Свинья-копилка
- •Формат входного файла:
- •Формат выходного файла:
- •Примеры
- •Решение
- •Входные данные:
- •Выходные данные:
- •Формат входа
- •Формат выхода
- •Задача 39 Лесенка-2
- •Входные данные
- •Выходные данные
- •Примеры
- •Системы счисления
- •Задача 11 Троичная сбалансированная система счисления
- •Алгоритм перевода
- •Процедуры и функции для работы с символами и строками
- •Определить количество слов в строке
- •Получите строковой массив из всех слов данной строки
- •Получите строковой массив из всех слов данной строки и
- •Получите строковой массив из всех слов данной строки и
- •Составьте программу, определяющую, является ли введенное слово изображением числа
- •Введите 2 целых числа. Преобразуйте числа в две строки, объедините их в одну строку и выведите результат на экран.
- •Вычислите длину самого короткого и самого длинного слов в строке
- •Подсчитайте количество букв в каждом слове данной строки
- •Дана строка. Определить количество слов этой строки, в которых есть ровно две буквы «е»
- •Составьте программу, удаляющую все лишние пробелы из введенной строки
- •Напишите программу, сортирующую символы введенной с клавиатуры строки в порядке возрастания их номеров в ascii-таблице. Например, если введено: 'cba', в результате надо получить ‘abc’.
- •В тексте, состоящем из маленьких латинских букв , подсчитайте количество гласных букв
- •Заданы фамилия, имя и отчество учащегося, разделенные пробелом. Напечатайте его фамилию и инициалы.
- •Сложное слово состоит из двух частей одинаковой длины и соединительной гласной. Найдите обе части этого слова.
- •Вычеркните из слова х те буквы, которые встречаются в слове z
- •Подсчитайте число различных букв в слове
- •Даны два слова. Составьте программу, определяющую можно или нет из букв слова а составить слово в.
- •Даны два слова. Являются ли они анаграммами
- •Является ли данная строка палиндромом?
- •Задача 4. Сокращение одночленов
- •Входные и выходные данные
- •Это чисто техническая задача на аккуратное программирование.
- •Задача 6 Текст
- •Входной файл Input.Txt в первой строке входного файла находится 5 чисел,разделенных пробелом: n, m, s, t, q.
- •Бинарные деревья. Алгоритм HeapSort
- •Поиск в глубину в графе
- •Алгоритм Флойда поиска кратчайших расстояний и кратчайших путей
- •Бинарные деревья. Алгоритм HeapSort
- •Графызадачи Двоичная куча
- •Примеры задач, которые решаются с помощью двоичной кучи
- •Поиск максимального потока методом Форда-Фалкерсона на Pascal
- •Графызадачи Поиск сильно связанных компонент на Pascal
- •Поиск точек раздела, мостов и двусвязных компонент
- •Идеи алгоритмов
- •Точки раздела
- •Двусвязные компоненты
- •Задача 21 Моя Столица
- •Вычислительная геометрия
- •3. Уравнение прямой 2
- •4. Уравнение прямой проходящей через точку м(х0у0)
- •Формат входного файла
Формат входного файла
Первая строка содержит число N (1<=N<=24) – количество деталей в конструкторе. Следующие N строк содержат описания деталей: каждая строка содержит непустую последовательность различных заглавных латинских букв, обозначающих метки разъемов детали.
Формат выходного файла
Первая строка должна содержать число K. Вторая строка должна содержать K чисел, разделенных пробелами – номера деталей, которые Петя может использовать для сборки конструкции. Числа следует выводить в порядке возрастания.
Примеры
Input.txt |
Output.txt |
6 ABD EG GE ABE AC BCD |
5 1 2 3 5 6 |
1 ABC |
0 |
4 AB X A B |
3 1 3 4 |
Сокращенное условие:
Из латинских букв некоторым (см.подробное условие) образом строится последовательность. Требуется написать программу, которая по заданному числу N находит символ, который стоит на N-ом месте в последовательности, получившейся после 26-го шага.
Формат входных данных:
Входной файл Input.txt содержит в первой строке число N (1<=N<226).
Формат выходных данных:
В выходном файла Ootput.txt записывается символ, стоящий в позиции N получившейся последовательности.
Пример
Input.txt |
Output.txt |
4 |
w |
Задачу надо решать методом перебора с возвратом. Этот метод использовался в задаче "Последовательность". Надеюсь, что все будет понятно после прочтения программы.
var
k : integer;
n, p : longint;
inp, out : text;
begin
assign(inp,'input.txt'); reset(inp);
assign(out,'output.txt'); rewrite(out);
readln(inp,n);
p:=2; for k:=2 to 25 do p:=p*2;
k:=0;
while n>1 do
begin
k:=k+1;
if n>p then n:=n-p else n:=n-1;
p:=p div 2
end;
writeln(out,chr(ord('z')-k));
close(out)
end.
переборзадачи
Задача 10 Арифметическая прогрессия
В арифметической прогрессии было 10 вещественных чисел. Два из них были утеряны, остальные перепутаны. Найти всевозможные варианты восстановления утерянных чисел и вывести каждый вариант в новой строке.
program C4 ;
var a:array[1..8] of real;
i,j,k: integer;
d,p:real;
begin
assign(input,'in.txt') ;
reset (input);
assign(output,'out.txt');
rewrite(output);
k:=0;
for i:=1 to 8 do read(a[i]);
for i:=1 to 7 do сортировка
for j:=i+1 to 8 do
if a[i]>a[j]
then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
end;
d:=maxint;
for i:=1 to 7 do
if d>a[i+1]-a[i] then d:=a[i+1]-a[i]; находим разность прогрессии
for i:=1 to 7 do считаем сколько раз выполняется
if a[i+1]-a[i]=d then inc(k); равенство a[i+1]-a[i]=d
if k=7 если 7 раз, то
then утерянные числа могут стоять
begin
writeln(a[1]-2*d,' ',a[1]-d); два в начале
writeln(a[8]+d,' ',a[8]+2*d); два в конце
writeln(a[1]-d,' ',a[8]+d); одно в начале и одно в конце
end;
if k=6 если 6 раз, то
then
for j:=1 to 7 do ищем место пропущенного числа
begin
if a[j+1]-a[j]=2*d могут быть два случая
then
begin
writeln(a[1]-d,' ',a[j]+d); пропущенное число стоит перед первым и в
середине на j месте
writeln(a[j]+d,' ',a[8]+d); halt пропущенное число стоит в середине на j месте
и после последнего
end;
if a[j+1]-a[j]=3*d если пропущены два соседних внутри массива
then
begin writeln(a[j]+d,' ',a[j]+2*d);halt end; выводим их
end;
end.
переборзадачи
Задача 10 Вычеркивание чисел
а) Из последовательности, состоящей из N чисел, вычеркнуть минимальное количество элементов так, чтобы оставшиеся образовали строго возрастающую последовательность.
б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, одной пары соседних элементов ( одного "разрыва" возрастающей подпоследовательности).
Например: A=(1,2,3,2,4,3,4,6);
Искомая подпоследовательность (1,2,3,2,3,4,6)
Разрыв подчеркнут. ---
б) Из заданной числовой последовательности A[1..N] вычеркнуть минимальное число элементов так, чтобы в оставшейся подпоследовательности каждый последующий элемент был больше предыдущего кроме, быть может, m пар соседних элементов ( возрастающая подпоследовательность с m "разрывами").
а). Пусть К(L,i) обозначает множество возрастающих подпоследовательностей длины L, которые составлены из элементов с номерами от 1 до i-1. Понятно, что их может быть очень много. Однако их число можно существенно сократить, воспользовавшись следующим фактом: из двух цепочек длины L более перспективной будет цепочка, у которой величина последнегоэлемента меньше, так как ее может продолжить большее числоэлементов. Пусть S(L,i) - это именно такая самая перспективная цепочка длины Lс минимальным по величине последним элементом, а S(i) – это множество всех цепочек S(L,i) со всевозможными L. Понятно, что в S(i) содержится не более i-1 цепочек (с длинами 1,...,i-1). Пусть мы знаем S(i). Для того, чтобы определить, какие цепочки может продолжать i-й элемент,достаточно знать последние элементы перспективных цепочек.
Для этого удобно завести массив адресов АДР последних элементов перспективных цепочек длины 1,2,...,n. При этом легко понять, что последний элемент перспективной цепочки длины s не превышает последнего элемента перспективной цепочки длины s+1. Следовательно, для очередного i-го элемента достаточно найти только максимальную длину перспективной цепочки, для которой он будет последним. Понятно, что это будет цепочка максимальной длины, последний элемент которой меньше текущего элемента. Учитывая упорядоченность последних элементов перспективных цепочек, поиск можно сделать дихотомией. При присоединении i-го элемента к какой-нибудь цепочке длины p ее длина увеличивается на 1, a ее последним элементом становится элемент i. При этом множество S(i+1) совпадает с S(i) за исключением одной цепочки
S(p+1,i+1) = S(p,i) сцепленная с i-ым элементом. Для хранения цепочек удобно хранить для каждого элемента номер элемента, который ему предшествует в цепочке.
Другое решение этой задачи:
Заведем 3 массива длины N: в массиве A[1..N] помещаются сами числа последовательности. Элемент B[i] имеет значение длины максимальной возрастающей подпоследовательности, завершающейся элементом A[i], а величина C[i] есть индекс предшествующего элементу A[i] элемента в этой максимальной последовательности (A[i]=0 есть такого элемента нет).
Если N=1, то A[1] и есть искомая подпоследовательность. При этом B[1]=1, C[1]=0. Предположим, что мы заполнили массивы A,B и C от начала до элемента M-1. Попытаемся обработать элемент A[M]. Просматривая массив A от 1 до M-1-го элемента мы ищем такое A[k], что одновременно
1) A[k]<A[M],
2) B[k] максимально.
Очевидно, что для того, чтобы получить максимальную по длине подпоследовательность, заканчивающуюся A[M], этот элемент надо приписать к подпоследовательности с последним элементом A[K]. Получаем, что B[M]=B[K]+1, C[M]=K.
Пусть мы обработали все N элементов массива A. Находим максимальный элемент массива B, пусть это будет B[K]. По построению это длина максимальной подпоследовательности.
Выписываем эту подпоследовательность: полагаем j:=k; печатаем элемент A[j]; так как предшествующий в последовательности элемент имеет индекс C[j], то делаем присваивание j:=C[j], распечатываем этот элемент и т.д., до тех пор, пока j не станет 0 (т.е. мы дошли до начала последовательности).
Запись алгоритма:
for i:=2 to N do B[i]:=0;
C[1]:=0; B[1]:=1; Max:=1; IndexMax:=1;
for i:=2 to N do
for j:=1 to i-1 do
if (A[j]<A[i]) AND (B[i]<B[j]+1)
then begin
C[i]:=j;
B[i]:=B[j]+1;
if B[i]>Max
then begin Max:=B[i]
IndexMax:=i
end;
while IndexMax<>0 do begin
writeln(A[Index-Max]);
IndexMax:=C[IndexMax]
end;
В программе в переменной Max хранится максимальная найденная до сих пор длина подпоследовательности, в IndexMax находится индекс последнего элемента этой подпоследовательности.
Структура данных, каждый элемент которой (в данном случае A[i]) содержит ссылку (в этой задаче C[i]) на предыдущий элемент (или, если требуется, на последующий элемент) называется однонаправленным списком. Если у элемента есть ссылка как на предыдущий, так и на последующий за ним элемент, то список двунаправленный (его можно реализовать, используя не один массив для индексов, а два).
б). Частный случай пункта в).
в). Заведем матрицу С[0..m+1,1..n]. В ней i-тая строка будет хранить информацию о последовательностях с i-1 разрывами; j-ый элемент в этой строке есть длина самой длинной подпоследовательности элементов "хвоста" массива А ( от j-го элемента до n-го), начинающейся в j-ой позиции и с не более чем i-1 разрывом.
Правило заполнения матрицы:
Заполним нулевую строку нулями (чтобы можно было заполнить первую строку по общему алгоритму). Для каждого номера строки i от 1 до m+1 выполнить следующие действия:
Для j-го элемента массива A (j изменяется от n до 1) находим максимальную по длине подпоследовательность, которую можно присоединить к этому элементу так, чтобы получить подпоследовательность максимальной длины с не более чем i-1 разрывом. Для этого мы:
1) ищем элемент A[k] последовательности A, больший A[j], стоящий в массиве A правее j-го элемента и с максимальным С[i,k];
2) затем просматриваем элементы i-1 -ой строки матрицы С, начиная с j+1 -го и до конца, и находим C[i-1,s] - максимальный из них;
3) сравниваем C[i-1,s] с С[i,k]. Больший из них (обозначим его C[row,col]), увеличенный на 1, запоминаем в C[i,j]. Это и будет длина максимальной подпоследовательности, начинающейся в позиции j, с не более чем i-1 разрывом.
4) Запоминаем индексы row и col элемента массива C, предшествующего C[i,j], в ячейках X[i,j] и Y[i,j] соответственно.
После окончания цикла максимальный элемент m+1 -ой строки матрицы C и есть максимальная длина возрастающей подпоследовательности с m разрывами. Выписать всю подпоследовательность можно следующим образом: для каждого элемента подпоследовательности в массивах X и Y хранится информация о предшественнике. Мы, начиная с максимального элемента m+1 -ой строки матрицы C, восстанавливаем всю подпоследовательность.
Обоснование алгоритма:
Пусть мы знаем C[i-1,j] для всех j от 1 до n и для некоторого i, а также C[i,k] для k от j+1 до n. Мы хотим вычислить C[i,j].
Для j-го элемента массива А существует максимальная по длине подпоследовательность с не более чем i-1 -им разрывом, начинающаяся с A[j]. Второй элемент (обозначим его A[k]) этой максимальной подпоследовательности (если он, конечно, есть) может быть
1) больше, чем A[j]. Тогда мы находим его среди элементов, обладающих следующими свойствами:
а) k>j,
б) C[i,k] максимальный (т.е. мы присоединяем к A[j] максимальную по длине подпоследовательность с не более чем i-1 разрывом, формируя подпоследовательность опять не более чем с i-1 разрывом);
2) меньше или равный, чем A[j]. Тогда мы ищем его среди элементов, обладающих следующими свойствами:
а) k>j;
б) C[i-1,k] максимальный (т.е. мы присоединяем максимальную подпоследовательность с не более чем i-2 -мя разрывами, формируя подпоследовательность с не более чем i-1 разрывом).
Полученная подпоследовательность получается максимальной длины, так как длина подпоследовательности, начиная с A[k], максимальная.
Упоминавшиеся выше индексы row и col, которые запоминаются в X[i,j] и Y[i,j] соответственно, обозначают
col - индекс следующего за A[j] элемента в максимальной по длине подпоследовательности, начинающейся в позиции j и имеющей не более i-1 разрыва;
row-1 - максимальное количество разрывов в подпоследовательности, начинающейся в A[col].
const max=100; {максимальная длина массива A}
var
sw,l,i,j,k,n,m,maxind,swind:integer;
c:array [0..max,1..max] of integer;
x,y:array [1..max,1..max] of integer;
a,b:array [1..max] of integer;
begin
readln(n);
for i:=1 to n do
read(a[i]);
readln(m);
fillchar(c,sizeof(c),0); fillchar(x,sizeof(x),0);
fillchar(y,sizeof(y),0);
for i:=1 to m+1 do
for j:=n downto 1 do
begin
c[i,j]:=1;
for k:=j+1 to n do
if (a[k]>a[j]) and (c[i,k]>=c[i,j]) then
begin
c[i,j]:=c[i,k]+1;
x[i,j]:=k;
y[i,j]:=i;
end;
for k:=j+1 to n do
if c[i-1,k]>=c[i,j] then
begin
c[i,j]:=c[i-1,k]+1;
x[i,j]:=k;
y[i,j]:=i-1;
end;
end;
maxind:=1;
for i:=1 to n do
if c[m+1,i]>c[m+1,maxind] then
maxind:=i;
l:=c[m+1,maxind];
j:=maxind;i:=m+1;k:=1;
while (c[i,j]<>1) do
begin
b[k]:=j; inc(k); в массив b выписываем индексы элементов
максимальной по длине подпоследовательности
sw:=x[i,j]; в прямом порядке
i:=y[i,j];
j:=sw;
end;
b[k]:=j;
for i:=1 to k do write(a[b[i]],' ');
writeln;
writeln(1);
end.
переборзадачи
Задача 13 Замечательные числа
Назовем целое число N замечательным, если для него справедливо равенство (*)
N2=(N – 1)2 + M2, где М – целое число. Даны два целых числа А и В. Найти количество замечательных чисел из диапазона [A,B] включительно. Например, в диапазоне [1,10] таких чисел два, а именно числа 1 и 5.
Входные данные: во входном файле содержатся два целых числа А и В (1<=A<=B<=109), разделенных пробелом.
Выходные данные: в выходной файл записать количество замечательных чисел из заданного диапазона.
Пример:
-
Input.txt
Output.txt
1 10
2
Эта задача на сокращение перебора.
Упрощаем равенство (*), получим 2*N-1= M2 . В левой части этого равенства находится нечетное число, следовательно, М тоже нечетное и принадлежит отрезку от 1 до квадратного корня из числа 2*N-1. Так как максимальное значение N равно В, то правая граница отрезка, содержащего М равна квадратному корню из числа 2*1000000000-1. Увеличим ее и возьмем равную квадратному корню из числа 2*1000000000.
program zad1;
{$APPTYPE CONSOLE}
uses
SysUtils;
const eps = 1e-10;
var m,a,b,sq,n,a1,b1:integer;
kol:integer;
begin
reset(input,'input.txt'); rewrite(output,'output.txt');
read(a,b);
kol:=0;
for m:=1 to trunc(sqrt(2000000000)) do перебираем М
if m mod 2 = 1 then если М нечетное
begin
n:=(m*m+1) div 2; вычисляем N
if (n>=a)and(n<=b) then inc(kol); и проверяем принадлежность N отрезку
end;
writeln(kol);
close(input); close(output);
end.
переборзадачи
Задача 14 Симметричные последовательности
Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:
1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.
Входные данные: в первой строке содержится число N - количество элементов исходной последовательности. Во второй строке записано N чисел, разделенных пробелом - элементы этой последовательности. 1 ≤ N ≤ 100, элементы последовательности - натуральные числа от 1 до 9.
Выходные данные: в первой строке число M - минимальное количество элементов, которое надо дописать к последовательности, во второй строке M чисел, которые надо дописать к последовательности.
Пример :
-
Input.txt
Output.txt
9
1 2 3 4 5 4 3 2 1
0
5
1 2 1 2 2
3
1 2 1
5
1 2 3 4 5
4
4 3 2 1
Алгоритм понятен из пояснений к программе.
program zad2;
var a,b:array[1..300]of integer;
i,j,n,k:integer;
function check:boolean; проверяет последовательность на симметричность
var i:integer;
begin
result:=false;
for i:=1 to n+k do
if b[i]<>b[n+k-i+1] then exit;
result:=true;
end;
begin
assign(input,'input.txt'); reset(input);
assign (output,'output.txt'); rewrite(output);
read(n); считываем массив
for i:=1 to n do read(a[i]);
for k:=0 to n do перебираем все возможные добавления
begin
fillchar(b,sizeof(b),0); очищаем массив b
b:=a; копируем массив а в массив b
for i:=n+1 to n+k do добавляем в массив b К чисел
b[i]:=a[n+k-i+1];
if check then проверяем массив на симметричность
begin
writeln(k); если получили симметричную последовательность, то
for i:=n+1 to n+k do выводим количество добавленных чисел и сами числа
write(b[i],' ');
close(input); close(output);
halt(0); прерываем работу программы
end;
end;
close(input); close(output);
end.
переборзадачи
К оглавлению
