- •Оценка эффективности алгоритмов
- •Целочисленная арифметика
- •Дано натуральное число. Выяснить является ли оно палиндромом, то есть читается справа налево и слева направо одинаково
- •Дано натуральное число. Выяснить соотношение между количествами двоек и пятерок в этом числе
- •Найти самую большую и самую маленькую цифры данного натурального числа
- •Выяснить образуют ли цифры натурального числа возрастающую последовательность
- •Формат выходного файла
- •Формат входного файла
- •Формат выходного файла
- •Формат входного файла
- •Формат входного файла
- •Формат выходного файла
- •Длинная арифметика
- •Выходные данные
- •Задачи Задача 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)
- •Формат входного файла
Решение
Для начала заметим, что длины удочек никак на ответ не влияют. Наша задача, фактически, состоит в следующем: требуется найти количество разложений K в сумму N различных натуральных чисел. Вычтем из наименьшего числа в разложении 1, у второго по величине - 2, и т.д., из N-ого - N. Заметим, что таким образом мы споставляем каждому разложению K на N неравных натуральных множителей разложение числа L = K-N(N+1)/2 в сумму N целых неотрицательных, не обязательно неравных, чисел. Если у нас получилось L<0, то количество вариантов равно нулю.
Обозначим это количество через aL,N. Выведем рекуррентное соотношение на aL,N. Заметим, что все разложения разбиваются на две группы:
разложения, в которых хотя бы одно из чисел равно 0;
разложения, в которых все числа больше нуля.
Если мы из разложения первого типа выкинем член, равный нулю, то мы получим уже разложение числа L (сумма ен менялась) на N-1 слагаемое. Следовательно, количество разложений первого типа равно aL,N-1. С разложениями второго типа поступим иначе: вычтем из каждого слагаемого в разложении по 1. В результате, мы получим разложение числа L-N на N слагаемых. Значит, разложений второго типа ровно aL-N,N. Итак, мы получили рекуррентное соотношение:
aL,N=aL,N-1 + aL-N,N
Остается добавить, что a0,N = 1 для любого N и aL,1=1 для любого L. С помощью этих соотношений легко написать программу, которая будет решать данную задачу. Вычисляем элементы этого массива последовательно.
динампрогрзадачи
Задача 31 Палиндромы
Непустая строка называется палиндромом, если она одинаково читается как слева направо, так и справа налево. Пусть задана строка S, состоящая из N прописных букв латинского алфавита. Вычеркиванием из нее некоторых букв нужно получить палиндром.
Требуется написать программу, определяющую, сколько существует способов вычеркивания из заданной строки некоторого (возможно пустого) набора букв, чтобы оставшаяся строка была палиндромом. Способы, отличающиеся порядком вычеркивания символов, считаются одинаковыми.
Входные данные:
В единственной строке входного файла INPUT.TXT записано N букв слова S (1 <= N <=60).
Выходные данные:
В единственной строке выходного файла OUTPUT.TXT должно содержаться найденное число способов.
Пример входного и выходного файла
-
INPUT.TXT
OUTPUT.TXT
BAOBAB
22
program palindrom;
var i, j, k, l, n, p, sum : integer;
a : array[1..60,1..60l] of byte; a[i,j] – количество способов вычеркивания с i по j
s : string; позиции
begin
assign(input,'input.txt’);reset(input);
assign(output,'output.txt'); rewrite(output);
readLn(s);
n := length(s);
fillchar(a,sizeof(a),0);
for i:=1 to n do a[i,i]:=1;
for k:=1 to n do заполняем массив
for i:=1 to n-k do перебираем позиции
begin
j:=i+k;
if s[i] = s[j] если символы совпадают
then sum := a[i+1,j] + a[i,j-1] + 1
else sum := a[i+1,j] + a[i,j-1] - a[i+1,j-1] ;
end;
write(a[1,n]);
close(input); close(output);
end.
динампрогрзадачи
Задача 32 График работы
Нанимая на работу нового охранника, директор фирмы вручил ему список из N–1 интервала времени [t1; t2], [t2; t3], ... , [tN – 1; tN] и предложил самому составить график его дежурств. Охраннику разрешается выбрать в качестве рабочих смен любые промежутки времени [tk ; tm] (k m), удовлетворяющие следующим требованиям:
1) первый и последний интервалы [t1; t2] и [tN – 1; tN] он должен отработать обязательно;
2) после окончания очередной смены охранник должен отдыхать в течение интервала из списка, следующего за этой сменой.
Требуется разработать программу для составления графика, при котором суммарное время работы охранника было бы минимальным.
Формат входных данных:
Первая строка входного файла содержит одно целое N — общее количество моментов времени в списке (2 N 5000). Каждая i-ая из последующих N строк содержит по одному целому числу ti (0 ti 60 000).
Формат выходных данных:
Первая строка выходного файла должна содержать одно число — суммарное время работы охранника. Следующие строки содержат по два разделенных пробелом числа, определяющих моменты начала и конца каждой смены.
Пример:
Input.txt |
Output.txt |
5 2 5 12 14 20
|
11 2 5 12 20
|
Идея решения. Использование схемы динамического программирования.
program gvozdiki;
const nmax=5000;
var d,k,n,i,j:integer;
a:array[1..nmax] of longint;
b:array[0..nmax] of longint;
procedure init;
var p:integer;
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 i:=1 to n-1 do сортируем времена по возрастанию
for j:=i+1 to n do
begin
if a[i]>a[j] then
begin
p:=a[i];
a[i]:=a[j];
a[j]:=p;
end;
end;
close(input);
end;
function min(x,y:integer):integer; находит минимальное из двух чисел
begin
if x<y then min:=x
else min:=y;
end;
procedure solve; решение
begin
b[0]:=0; фиктивный самый меньший момент времени
b[1]:=60000; расстояние от фиктивного до первого =
бесконечности
for i:=2 to n do перебираем моменты времен
begin
b[i]:=min(b[i-1],b[i-2])+a[i]-a[i-1]; выбираем минимальный из двух возможных
end; промежутков
end;
procedure out;
begin
write(b[n]); close(output);
end;
begin init; solve; out;end.
динампрогрзадачи
Задача 34 О распиле палки решения нет
Дан отрезок (палка) [0,N], который нужно распилить в помеченых местах L1 , L2, ... , Lk. Числа N, Li — натуральные, 1 <= N <= 1000000, 1 <= k <= 200, 0 < Li < N. Числа Li разные. За один раз мы можем распилить один отрезок на два и заплатить за это цену, равную его длине. Сделайте распилы в помеченых местах, заплатив за это минимальную цену.
Эта задача решается методом динамического программирования. Идея динамического программирования заключается в двух моментах
параметризация задачи, то есть введение множества задач, запараметризованного одним или несколькими целочисленными параметрами, так что при максимальном значении параметров мы получаем ту задачу, которую нам нужно решить, а при маленьких значениях параметров получаем простые задачи, для которых мы можем сразу дать ответ
хранение в памяти вычисленных ответов для множества задач, и использование их при поиске ответов на задачи с большими значениями параметров
В нашем случае мы вводим такое параметрическое множество:
задача A[i][j] есть "найти минимальную цену распила палки [Li,Lj] во всех её внутренних метках
Таких задач ( k * (k-1) ) /2. Обозначим a[i][j] ответ на задачу A[i][j], а именно
a[i][j] есть минимальная цена распила палки [Li,Lj]
Нас интересует только элементы матрицы a[i][j] (массива) с j > i.
Понятно, что на диагонали и на второй диагонали матрицы стоят нули. Заполним остальные ячейки массива a "плюс бесконечностью" (в программе это будет просто очень большое число, например N*k + 1).
После этого диагональ за диагональю будем вычислять элементы массива a.
