Решения олимпиадных задач. Муниципальный этап.
ЕГЭ B1
Имя входного файла
input.txt
Имя выходного файла
output.txt
Максимальное время работы на одном тесте
2 секунды
Ограничение по памяти
64 МБ
Некоторое сигнальное устройство за одну секунду передает один из трех специальных сигналов. Какое количество различных сообщений можно передать при помощи этого устройства за N секунд?
Формат входных данных:
Задано одно натуральное число N (1
· N
· 20).
Формат выходных данных:
Выведите количество сообщений.
Пример
input.txt
output.txt
1
3
Алгоритм решения задачи ЕГЭ В1
По условию задачи за одну секунду можно передать один из трех специальных сигналов. Сообщение передается N секунд. Необходимо найти число всех возможных сообщений, состоящих из трёх видов сигналов и передаваемое за N секунд. Для этого воспользуемся комбинаторной формулой для нахождения числа размещений с повторениями 13 QUOTE 1415. То есть для данной задачи количеством различных сообщений будет число 3N. Так как в Паскале нет реализации для функции nm, то для подсчёта числа 3N за линейное время можно воспользоваться свойством логарифмов 13 QUOTE 1415. Число а может быть любым, для удобства пусть оно будет равным числу е. Получим: 13 QUOTE 1415. Далее упростим полученное выражение, воспользовавшись свойством логарифма 13 QUOTE 1415. Получим: 13 QUOTE 1415. Эту формулу можно реализовать в Паскале, воспользовавшись функциями взятия экспоненты exp(x) и натурального логарифма ln(x).
Код на Паскаль.
program egeb1;
var
n:int64;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
read(input,n);
write(output,round(exp(n*ln(3))));
close(input);
close(output);
end.
Сейф
Имя входного файла
input.txt
Имя выходного файла
output.txt
Максимальное время работы на одном тесте
2 секунды
Ограничение по памяти
64 МБ
Вася был величайшим вором всех времен и народов. Однажды он решил ограбить банк. Чтобы открыть главный сейф, ему нужно вставить три определенных ключа в соответствующие замки сейфа. Только тогда дверь откроется.
Вася уже украл у директора связку ключей, в которой точно есть три нужных. Теперь он хочет оценить, сколько времени в худшем случае ему понадобится на открывание сейфа, если он успевает проверить одну комбинацию за одну секунду.
Формат входных данных:
Задано одно натуральное число N (3
· N
· 104) количество ключей в связке.
Формат выходных данных:
Выведите время в секундах.
Пример
input.txt
output.txt
3
6
Алгоритм решения задачи Сейф.
По условию задачи даны N ключей. Необходимо найти количество размещений без повторений этих ключей по трём замкам сейфа. Для решения этой задачи воспользуемся комбинаторной формулой для нахождения числа размещений без повторений 13 QUOTE 1415. То есть решением данной задачи будет число 13 QUOTE 1415. Чтобы упростить реализацию решения, воспользуемся свойством факториала. Получим: 13 QUOTE 1415. Сократим выражение (n–3)! в числителе и знаменателе, получим: n*(n–1)*(n–2). Данную формулу можно реализовать средствами Паскаля и получить линейное время работы программы.
Код на Паскаль.
program statistics;
var
n:int64;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
read(input,n);
write(output,n*(n-1)*(n-2));
close(input);
close(output);
end.
Шашлыки
Имя входного файла
input.txt
Имя выходного файла
output.txt
Максимальное время работы на одном тесте
2 секунды
Ограничение по памяти
64 МБ
Вася с одноклассниками пошел на шашлыки. Ему поручили следить за мангалом. Через некоторое время он заметил, что шашлыки жарятся неравномерно. Поэтому он решил положить самые поджаристые шампура туда, где меньше жара и наоборот.
За один раз Вася может поменять местами два шампура. Так как они очень горячие, он хочет сделать минимальное количество перемещений. Помогите Васе подсчитать наименьшее количество перемещений шампуров учитывая, что он заранее выбрал какой шампур куда надо положить.
Формат входных данных:
В первой строке задано одно натуральное число N (1
· N
· 105). Во второй строке через пробел записаны N различных чисел номера позиций, куда нужно переместить соответствующие шампура. Все номера являются натуральными числами, не превосходящими N.
Формат выходных данных:
Выведите минимальное количество перемещений.
Пример
input.txt
output.txt
4 1 4 3 2
1
5 4 2 1 3 5
2
Алгоритм решения задачи Шашлыки.
По условию задачи даны N шампуров и N мест для них. Создадим массив а размеров от 1 до максимального значения N, то есть до 105, где индекс ячейки будет обозначать номер места для шашлыка. Запишем в этот массив данные по условию числа, обозначающие номера мест, которые должны занимать шашлыки после всех перестановок. Для решения этой задачи используем следующий алгоритм. В цикле с предусловием (пока переменная i меньше либо равна N) пройдём по массиву а от начала до конца. На каждой итерации цикла будем проверять единственное условие: соответствует ли номер места, занимаемого шашлыком на текущем этапе (i) месту, которое он должен занимать (a[i]). Если это условие истинно, то переходим к следующему по порядку месту для шашлыка (inc(i)). Если же условие ложно, то необходимо поместить данный шашлык на определённое для него место (a[i]). Для этого поменяем текущий шашлык с шашлыком, занимающим его место, нарастив при этом счётчик количества перестановок cnt. В этом случае переходить к следующему месту не следует, так как может оказаться, что шашлык, перемещенный на текущую позицию, так же не лежит на своём месте и потребуется ещё одна перестановка. Именно по этой причине мы используем цикл с предусловием, а не цикл по счётчику. После завершения цикла мы получим отсортированный по возрастанию массив целых чисел, а в переменной счётчика количества перестановок (cnt) будет находиться ответ на данную задачу. Таким образом, программа содержит один цикл по счётчику, который используется для записи исходных данных, и один цикл с предусловием, используемый для анализа входных данных и получения ответа на поставленную задачу. Отсюда получим, что время выполнения данного алгоритма является линейным.
Код алгоритма на Паскаль.
program chachlyk;
var
n,i,akk,sch,flag:longint;
a:array [1..100000] of longint;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
read(input,n);
for i:=1 to n do
read(input,a[i]);
flag:=0;
while(flag=0)do begin;
flag:=1;
for i:=1 to n do
if a[i]<>i then begin
akk:=a[i];
a[i]:=a[a[i]];
a[akk]:=akk;
inc(sch);
flag:=0;
end;
end;
write(output,sch);
close(input);
close(output);
end.
Лист в линию
Имя входного файла
input.txt
Имя выходного файла
output.txt
Максимальное время работы на одном тесте
1 секунда
Ограничение по памяти
64 МБ
На уроке русского языка Вася от скуки решил раскрасить тетрадный лист в линию, который представляет собой прямоугольник размером WЧH. На нем нанесены горизонтальные и наклонные линии, разбивающие лист на кусочки. Вася решил каждый кусочек раскрасить в уникальный цвет. Какое количество различных цветов понадобится Васе?
Будем считать, что прямоугольник расположен в первой координатной четверти, причем левый нижний угол расположен в начале координат, а сторона длиной W параллельна оси абсцисс. Горизонтальные линии задаются ординатами точек пересечения прямых с осью OY, а наклонные абсциссами точек пересечения прямых с осью OX. Наклонные линии составляют угол 45° с положительным направление оси OX (см. рисунок).
[ Cкачайте файл, чтобы посмотреть картинку ]
Формат входных данных:
В первой строке заданы четыре натуральных числа: W, H, N, M (1
· W, H
· 105, 0
· N < H, 0
· M < W + H). Во второй строке записано N чисел ординаты точек пересечения горизонтальных линий с осью OY. В третьей строке записано M абсцисс точек пересечения наклонных линий с осью OX. Гарантируется, что все линии проходят через прямоугольник (отсекают какую-то не пустую часть) и нет двух одинаковых линий. Все числа целые.
Формат выходных данных:
Выведите количество различных цветов.
Пример
input.txt
output.txt
6 4 2 1 1 3 1
6
Алгоритм решения задачи "Лист в линию".
Выводим решения задачи в крайних случаях m =0 и n=0. Дале подсчитываем количество секторов левее очередной наклонной линии.
Код алгоритма на Паскаль.
program list;
var
input,output:text;
w,h,n,m,i,j,kolvoab,sektor,kolvor: int64;
absciss: array [1..200000] of int64;
ordinat: array [1..100000] of int64;
begin
assign(input,'input.txt');
assign(output,'output.txt');
reset(input);
rewrite(output);
read(input,w,h,n,m);
for i:=1 to n do
read(input,ordinat[i]);
for i:=1 to m do
read(input,absciss[i]);
if m=0 then
write(output,n+1)
else begin
if n=0 then
write(output,m+1)
else begin
kolvor:=n;
for i:=n downto 1 do begin
kolvoab:=0;
for j:=1 to m do begin
if ordinat[i]>w-absciss[j] then begin
inc(kolvoab);
dec(kolvor);
end
else
sektor:=((kolvoab+1)*(kolvor+1))+sektor;
end;
end;
write(output,sektor);
end;
end;
close(input);
close(output);
end.
Фђ Заголовок 1ђ Заголовок 215