Ускова О.Ф., Горбенко О.Д. и др. Олимпиадные задачи по программированию. Лучшие решения. Часть 1
Подождите немного. Документ загружается.
Формат выходных данных
Ответом должно быть слово Yes или No (Yes – выражения
тождественно равны , No – выражения тождественно не равны ).
Пример файлов входных и выходных данных
INPUТ.ТХТ OUTPUT.TXT
a+b*(c+d) Yes
b*d+a+b*c
Задача 16. «АБРАКАДАБРА»
Последовательность из латинских букв строится следующим
образом . На первом шаге она пуста . На каждом последующем
шаге последовательность удваивается, после чего к ней слева
дописывается очередная буква латинского алфавита (а, b, с, … ).
Ниже приведены первые шаги построения последовательности :
пустая последовательность
Шаг 1. а
Шаг 2. bаа
Шаг 3. сbааbаа
Шаг 4. dсbааbаасbааbаа
. . . . . . . . .
Задача состоит в том , чтобы по заданному числу N
определить символ, который стоит на N-ом месте в
последовательности , получившейся после 26-го шага.
Технические требования
Входной файл: INPUT.ТХТ
Выходной файл: О UTPUТ.ТХТ
Ограничение времени : 20 секунд
Формат входных данных
Во входном файле записано одно натуральное число N
(1<=N<2
26
).
Формат выходных данных
Запишите в выходной файл символ, стоящий в позиции N
получившейся последовательности .
Пример файлов входных и выходных данных
INPUТ.ТХТ OUTPUT.TXT
4 w
Следующая задача предлагалась на тренировочном туре
четвертьфинала мирового первенства студентов по
программированию ACM NEERC в 1996 году.
Задача C «Анализ сортировки»
Ниже приведен алгоритм MSort, который сортирует заданный
массив A из N целых чисел. Этот метод сортировки называется
сортировкой слиянием . Массив A разбивается на две части ,
которые сортируются по отдельности этим же методом . Затем
отсортированные половины сливаются в один отсортированный
массив.
Имя файла исходных данных: INPUT.TXT
Имя выходного файла : OUTPUT.TXT
Время тестирования: 10 секунд на каждый тест
Требуется написать программу, которая для заданного N (1<
=N< =50.000.000) находит:
1) Максимальное количество операторов cравнения "if A[i]<
A[j]", которое может выполнить алгоритм MSort.
2) Строит пример массива A, на котором достигается
максимальное число сравнений (только для N< =10.000). Все
элементы массива A должны быть различными и находиться в
диапазоне от 1 до N, т.е . массив A должен содержать перестановку
чисел 1,2, ..., N.
Входные данные
Файл исходных данных содержит число N.
Выходные данные
Вывести в выходной файл максимальное количество
сравнений и значения элементов массива A[1], A[2], ..., A [N]. Если
N >10000, то выходной файл должен содержать только
максимальное количество сравнений. Все числа в выходном файле
разделяются пробелами и (или ) символами перевода строки .
Пример 1 файла исходных данных INPUT.TXT:
3
Выходной файл OUTPUT.TXT для примера 1:
3
2 1 3
Пример 2 файла исходных данных INPUT.TXT:
10001
Выходной файл OUTPUT.TXT для примера 2:
123631
АЛГОРИТМ MSort:
| algorithm MSort (N: integer; var A: integer array [1..N]);
| var Help: integer array [1..N];
|
| procedure Make (u, v: integer);
| var i, j, m, k: integer;
| begin
| if u < v then
| m := (u+v) / 2; (* деление нацело с округлением в
сторону нуля
*)
| call Make (u, m);
| call Make (m+1, v);
| i := u; j := m+1; k := u;
| while (i<=m) and (j<=v) do
| (* !!! ОПЕРАТОР СРАВНЕНИЯ *)
| if A[i]<A[j] then Help [k] := A [i]; i := i+1;
| else Help [k] := A [j]; j := j+1;
| end if;
| k := k+1;
| end while;
| while i<=m do Help [k] := A [i]; i:=i+1; k:=k+1; end while;
| while j<=v do Help [k] := A [j]; j:=j+1; k:=k+1; end while;
| for i = u to v do A [i] := help [i]; end for;
| end if;
| end Make;
|
| begin
| call Make (1, N);
| end MSort;
3. ЗАДАЧИ С КОММЕНТАРИЯМИ И РЕШЕНИЯМИ
Задача 1. «Монеты».
Задача была предложена на Красноярской краевой олимпиаде
школьников, а также на Воронежской городской студенческой
олимпиаде 2000 года. Одним из призеров олимпиады был студент 3
курса факультета прикладной математики и механики Максим
Сергеевич Ефремов. Ниже приводится его вариант решения
задачи.
1. Условие задачи .
В сундуке у мистера Z имеется N монет. На следующий год
мистер Z взял из сундука M монет. В каждый следующий год
мистер Z добавлял в сундук столько монет, сколько у него было
два года назад . Известно, что на X-й год в сундуке мистера Z было
Y монет. Требуется определить, сколько монет было в сундуке
изначально, и сколько монет мистер Z взял на второй год .
Формат ввода:
файл Input.txt содержит числа X и Y.
Формат вывода
файл Output.txt содержит числа N и M.
2. Алгоритм решения.
Алгоритм решения - чисто математический. Рассмотрим
последовательность чисел
А(1), А(2), .. , А(n),..,
где А(k) - число монет в сундуке на k-й год . Из условия задачи
получаем
A(1)=N,
A(2)=N-M,
A(3)=2N-M,
A(4)=3N-2M,
A(5)=5N-3M,
A(6)=8N-5M,
........
A(X)=F(X)N-F(X-1)M=Y,
........
где F(n) - последовательность чисел Фибоначчи , которые
определяются рекуррентными соотношениями
F(1) = 1,
F(2) = 1,
F(K) = F(K-1)+F(K-2), K>2.
Вполне очевидно, что для нахождения M и N достаточно найти
целочисленное решение уравнения
F(X)N - F(X-1)M = Y. (*)
Такое уравнение, вообще говоря, имеет счетное множество
решений. Однако в дан ном случае это множество конечно,
поскольку A(n)>=0 для всех n и
A(K)>=A(K-2), для K>2,
а значит и
M<=N<=Y. (**)
3. Программная реализация.
Программная реализация сводится к нахождению
целочисленного решения уравнения (*) при условии выполнения
(**). Программа находит все возможные варианты ответа или
выдает сообщение о том , что решения нет.
Program Money;
Var
F:Text;
X,Y:Integer;
Procedure Init; {ввод из файла }
Begin
Assign(F,'Input.txt');ReSet(F);
ReadLn(F,X,Y);
Close(F)
End;
Function GetValue(K:Integer):Integer; {получение F(k)}
Var I,A,B,C:Integer;
Begin
If K<=2 Then GetValue:=1
Else
Begin
A:=1;B:=1;
For I:=3 To K Do
Begin
C:=B;
B:=B+A;
A:=C
End;
GetValue:=B
End
End;
Procedure Run; {решение уравнения}
Var
M,N:Integer;
A,B:Integer;
T:Boolean; {флаг разрешимости уравнения: true-если
решение есть}
Begin
Assign(F,'Output.txt');ReWrite(F);
A:=GetValue(X);
B:=GetValue(X-1);
T:=False;
For N:=1 To Y Do
For M:=0 To N Do
If A*N-B*M=Y Then
Begin
T:=True;
WriteLn(F,N,' ',M)
End;
If Not T Then WriteLn(F,'Задача не имеет решения!');
Close(F)
End;
Begin
Init;
Run
End.
Задача 2. "Функция "
Задача была предложена на Московской олимпиаде школьников
в 1981г. и на олимпиаде первокурсников факультета ПММ в 1998г .
Ниже приводится программа, разработанная Олегом
Викторовичем Гладышевым , который сейчас обучается на 4-м
курсе факультета ПММ ВГУ.
1. Условие задачи .
Функция F(n) для целых неотрицательных n определена так:
F(0)=0, F(1)=1, F(2n) = F(n), F(2n+1)=F(n)+F(n+1).
Для данного N найти и напечатать F(n). Обязательное условие: N
столь велико , что недопустимо заводить массив из N чисел.
2. Алгоритм решения.
Основная идея алгоритма заключается в том , что при
разложении f(2n+1) на f(n) и f(n+1) мы должны вычислить 2
значения функции. Либо n, либо n+1 окажется нечетным и для его
вычисления понадобится опять вычислять 2 значения функции. А
для четного аргумента еще одно. На первый взгляд , кажется, что
теперь нам надо вычислить значения F для 3 аргументов, но на
самом деле 2 из
них (аргументов) всегда совпадут! То есть кол-во вычислений
функции на каждом шаге не увеличивается.
Пример:
F(26) = F(13) = F(6)+F(7) = F(3)+F(3)+F(4) = 2F(3)+F(4) =
=2(F(1)+F(2))+F(2) = 2F(1)+3F(2) = 5F(1) = 5
3. Программная реализация
Program func; {Автор: Гладышев О.В.}
var
c, {Текущий четный аргумент}
nc, {Текущий нечетный аргумнт}
kc, {Коэффициент при четном аргументе }
knc, {Коэффициент при нечетном аргументе }
n:LongInt;
{В переменной c всегда должен быть четный аргумент, а в nc -
нечетный. Эта процедура меняет местами значения переменных c и
nc, если это необходимо}
Procedure Correct;
var Temp:LongInt;
Begin
if odd(c) then
Begin
Temp:=c;
c:=nc;
nc:=Temp;
Temp:=kc;
kc:=knc;