- •Оценка эффективности алгоритмов
- •Целочисленная арифметика
- •Дано натуральное число. Выяснить является ли оно палиндромом, то есть читается справа налево и слева направо одинаково
- •Дано натуральное число. Выяснить соотношение между количествами двоек и пятерок в этом числе
- •Найти самую большую и самую маленькую цифры данного натурального числа
- •Выяснить образуют ли цифры натурального числа возрастающую последовательность
- •Формат выходного файла
- •Формат входного файла
- •Формат выходного файла
- •Формат входного файла
- •Формат входного файла
- •Формат выходного файла
- •Длинная арифметика
- •Выходные данные
- •Задачи Задача 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)
- •Формат входного файла
Формат входного файла
Файл содержит целое число S (1 <= S <= 81).
Формат выходного файла
Файл должен содержать единственное число – значение миллиардной Функции Камиля в точке S.
Пример
Input.txt |
Output.txt |
1 |
10 |
var a,b:array[0..9,-100..100]of longint;
f:array[0..10]of longint;
c:array[0..9,0..9]of longint;
s,s1:longint;
ans:longint;
procedure init;
begin
read(s);
fillchar(a,sizeof(a),0);
if s=1 then ans:=10 else ans:=0;
end;
procedure solve;
var i,j,k,q,w:longint;
begin
if ans<>0 then exit;
f[0]:=1;
for i:=1 to 9 do
f[i]:=f[i-1]*i; вычисляем факториал
for i:=1 to 9 do
for j:=1 to i do
c[i,j]:=f[i] div(f[j]*f[i-j]); вычисляем c(n,k)
for i:=0 to 9 do c[i,0]:=1;
for q:=1 to 9 do begin
for i:=0 to 9 do a[i,0]:=1;
fillchar(b,sizeof(b),0);
for i:=1 to 9 do
for j:=1 to s do
for k:=1 to i do begin
if a[i-k,j-q*k]<>0 then
if j-q*k=0 then b[i,j]:=b[i,j]+c[i-1,k-1]*a[i-k,j-q*k]
else begin
b[i,j]:=b[i,j]+c[i,k]*a[i-k,j-q*k];
for w:=i-k-1 downto 1 do
if a[w,j-q*k]<>0 then begin
b[i,j]:=b[i,j]+c[i-1,k-1]*a[w,j-q*k]
end;
end;
end;
for i:=1 to 9 do
for j:=1 to s do
a[i,j]:=a[i,j]+b[i,j];
end;
for i:=1 to 9 do
ans:=ans+a[i,s];
end;
procedure out;
begin
write(ans);
end;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
init;
solve;
out;
close(input); close(output);
end.
Задачи Задача 56 Уравнение
Те кто решает олимпиадные задачи знает, что числа Фибоначчи появляются в решении совершенно неожиданно, после долгих поисков, как подарок судьбы. В нашей задаче они появятся в самом начале. Найдите количество целочисленных решений (x, y) уравнения Fnx+Fmy=c, где Fn и Fm n-е и соответственно m-е числа Фибоначчи, а с - целое число, для которых точки с координатами (x, y) принадлежат прямоугольнику, стороны которого параллельны осям координат и левая верхняя вершина имеет координаты (x1, y1), а правая нижняя (x2, y2). Точка считается принадлежащей прямоугольнику, если она находится на его границе или внутри прямоугольника.
Справка для тех, кто не знаком с числами Фибоначчи:
N |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
Fn |
0 |
1 |
1 |
2 |
3 |
5 |
8 |
13 |
Входные данные:
В первой строке два натуральных числа n и m, разделенных пробелом (1n,m17).
Во второй строке целое число с -106 c 106.
В третьей строке четыре целых числа, разделенных пробелом x1, y1, x2, y2.
( -106 x1, y1, x2, y2 106).
Выходные данные:
одно целое число- количество искомых точек.
Пример:
Input.txt |
Output.txt |
1 2 2 0 4 7 1
|
3 |
Если просто пробежать от x1 до x2, перебирая все целые числа, то мы не успеем по времени. Идея решения в следующем. Движемся от x1 вправо перебирая последовательно целые числа и проверяя их на принадлежность заданной прямой. Для этого мы вычисляем y и проверяем является ли он целым числом. Запоминаем найденное значение x3. Движемся дальше пока не найдем еще одно такое значение x4. на всех остальных отрезках длиной x4-x3 количество нужных точек будет таким же. Теперь мы шагаем с длиной шага равной x4-x3, то есть гораздо быстрее.
x1 x3 x4 xi x2
Для этого случая, добежав до точки xi, остается пройти отрезок от xi до x2.
Возможных случаев пересечения прямо и прямоугольника может быть несколько. Остается только нарисовать все случаи, понять разницу и написать программу.
задачи
Задача 57 Последовательность Фибоначчи
Дана последовательность натуральных чисел. Найти минимальное из тех чисел последовательности, номера которых являются числами Фибоначчи. (Числа Фибоначчи F1=1, F2=1, при N>2 FN =FN-1+FN-2
Входной файл Input.txt представляет собой последовательность целых чисел из диапазона -2147483648 .. 2147483647. Длина последовательности - не менее 1 и не превышает 10000 чисел. Любые два числа разделены одним или несколькими пробелами и(или) одним или несколькими символами перевода строки.
Выходной файл Output.txt должен содержать одно число - минимальное из тех чисел последовательности, номера которых являются числами Фибоначчи.
Пример:
Input.txt |
Output.txt |
6 4 10 2 13 11 30 8 9 -1 |
4 |
Program Posled_F;
Var
PrevF1, PrevF2, nextF, curnum : Word;
minval, curval : longint;
Begin
assign (input,'input.txt'); reset (input);
assign (output, 'output.txt'); rewrite (output);
read (MinVal);
prevF1 := 1; prevF2 := 1;
nextF := 2;
curnum := 2; текущий номер числа последовательности
While Not SeekEof do
Begin
Read (curval); считываем очередное число последовательности
If curnum = nextf then
Begin
prevF1 := prevF2;
prevF2 := nextF;
nextF := PrevF1 + PrevF2;
If curval < minval then minval := curval;
End;
Inc (curnum);
End;
Write (minval);
End.
задачи
Задача 58 Теорема Цеккендорфа
Чудаков на свете много. Один чудак- миллионер купил остров и решил выпустить свои деньги под названием фантики. Когда-то он занимался теорией чисел и очень любил теорему Цеккендорфа ( каждое натуральное число имеет единственное представление в виде суммы чисел Фибоначчи, в которой два соседних числа Фибоначчи никогда не используются.), поэтому решил выпустить деньги номиналом совпадающими с числами Фибоначчи и приказал кассиру платить зарплату своим сотрудникам этими купюрами, причем так, чтобы выполнялось условие теоремы Цекендорфа и купюра каждого номинала встречалась в выплаченной сумме один раз. У кассира возникла проблема: как выплатить сумму в N рублей. Помогите кассиру.
Дано натуральное число N (1N1018 ). Представить его в виде суммы N=Fk1+Fk2+…Fkr , где Fi число Фибоначчи и в этой сумме нет двух рядом стоящих чисел из последовательности чисел Фибоначчи и одинаковых чисел из этой последовательности.
Справка для тех, кто не знаком с числами Фибоначчи:
-
N
0
1
2
3
4
5
6
7
Fn
0
1
1
2
3
5
8
13
Входные данные: одно натуральное число N – размер зарплаты.
Выходные данные: Несколько чисел Фибоначчи, дающие в сумме число N. Все числа разделены пробелом и выписаны в порядке возрастания.
Пример:
-
Input.txt
Output.txt
2
2
Алгоритм решения следующий. 90 чисел Фибоначчи забиваем в массив констант. Все они умещаются в тип int64. Ищем в этом массиве наибольшее число Фибоначчи меньшее данного и запоминаем его. Вычетаем из данного числа найденное и получаем туже задачу, но с меньшим числом. И делаем так до тех пор пока само число не станет числом Фибоначчи. При получении следующего числа надо проверять не является ли оно соседним в последовательности Фибоначчи с найденным на предыдущем шаге.
program cekkendor2;
{$APPTYPE CONSOLE}
{$O-}
uses
SysUtils;
const f:array[1..90]of int64=(1,1,2,3,5,8,13,21,
34,55,89,144,233,377,610,987,
1597,2584,4181,6765,10946,17711,28657,46368,
75025,121393,196418,317811,514229,832040,1346269,2178309,…
3524578,5702887,9227465,14930352,24157817,39088169,63245986,102334155,
165580141,267914296,433494437,701408733,1134903170,1836311903,2971215073,4807526976,7778742049,12586269025,20365011074,32951280099,53316291173,86267571272,139583862445,225851433717,365435296162,591286729879,956722026041,1548008755920,2504730781961,4052739537881,6557470319842,10610209857723,17167680177565,27777890035288,44945570212853,72723460248141,117669030460994,190392490709135,308061521170129,498454011879264,806515533049393,1304969544928657,2111485077978050,3416454622906707,5527939700884757,8944394323791464,14472334024676221,23416728348467685,37889062373143906,61305790721611591,99194853094755497,160500643816367088,259695496911122585,420196140727489673,679891637638612258,1100087778366101931,
1779979416004714189,2880067194370816120);
var
i,j,m,k:int64;
a:array[1..30] of int64;
s,n:int64;
t,r:integer;
begin
assign(input,'input.txt'); reset(input);
assign(output,'output.txt'); rewrite(output);
read(n);
m:=1;
r:=0;
repeat
i:=90;
while (f[i]>n)and(i>1) do dec(i); ищем нужное число Фибоначчи
if f[i]=n если само число стало числом Фибоначчи
then begin inc(r);a[r]:=f[i]; break;end запоминаем его и выходим из цикла
else
begin inc(r);a[r]:=f[i]; n:= n-f[i]; end; иначе уменьшаем данное число
until (f[i]<n)or(i=1);
for t:=r downto 1 do выводим результат
write(a[t],' ');
close(output);
end.
задачи
Задача 59 Номера страниц нет решения
Любознательный наборщик подсчитал количество литер, потребовавшихся для набора всех номеров страниц в книге. Вы должны по найденному им числу определить, сколько было в этой книге страниц.
