Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Другие методич. материалы / Решения олимпиадных задач. Муниципальный этап.
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Информатика

Решения олимпиадных задач. Муниципальный этап.

библиотека
материалов

ЕГЭ B1



Имя входного файла

input.txt

Имя выходного файла

output.txt

Максимальное время работы на одном тесте

2 секунды

Ограничение по памяти

64 МБ

Некоторое сигнальное устройство за одну секунду передает один из трех специальных сигналов. Какое количество различных сообщений можно передать при помощи этого устройства за N секунд?

Формат входных данных:

Задано одно натуральное число N (1 ≤ N ≤ 20).

Формат выходных данных:

Выведите количество сообщений.

Пример

input.txt

output.txt

1

3

Алгоритм решения задачи ЕГЭ В1

По условию задачи за одну секунду можно передать один из трех специальных сигналов. Сообщение передается N секунд. Необходимо найти число всех возможных сообщений, состоящих из трёх видов сигналов и передаваемое за N секунд. Для этого воспользуемся комбинаторной формулой для нахождения числа размещений с повторениями hello_html_m412fc757.gif. То есть для данной задачи количеством различных сообщений будет число 3N. Так как в Паскале нет реализации для функции nm, то для подсчёта числа 3N за линейное время можно воспользоваться свойством логарифмов hello_html_m6d7ddd6c.gif. Число а может быть любым, для удобства пусть оно будет равным числу е. Получим: hello_html_m3d447ac7.gif. Далее упростим полученное выражение, воспользовавшись свойством логарифма hello_html_48089c88.gif. Получим: hello_html_m633ed1e3.gif. Эту формулу можно реализовать в Паскале, воспользовавшись функциями взятия экспоненты 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 ключей. Необходимо найти количество размещений без повторений этих ключей по трём замкам сейфа. Для решения этой задачи воспользуемся комбинаторной формулой для нахождения числа размещений без повторений hello_html_679d5d5f.gif. То есть решением данной задачи будет число hello_html_70176d5b.gif. Чтобы упростить реализацию решения, воспользуемся свойством факториала. Получим: hello_html_2c6392b1.gif. Сократим выражение (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 (см. рисунок).

hello_html_m2b07fdb.png

Формат входных данных:

В первой строке заданы четыре натуральных числа: WHNM (1 ≤ WH ≤ 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.

Автор
Дата добавления 07.02.2016
Раздел Информатика
Подраздел Другие методич. материалы
Просмотров170
Номер материала ДВ-426832
Получить свидетельство о публикации

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru

Похожие материалы

Включите уведомления прямо сейчас и мы сразу сообщим Вам о важных новостях. Не волнуйтесь, мы будем отправлять только самое главное.
Специальное предложение
Вверх