Имя входного файла input txt Имя выходного файла
 Скачать 87.29 Kb.
|
ЕГЭ B1
Некоторое сигнальное устройство за одну секунду передает один из трех специальных сигналов. Какое количество различных сообщений можно передать при помощи этого устройства за N секунд? Формат входных данных:Задано одно натуральное число N (1 ≤ N ≤ 20). Формат выходных данных:Выведите количество сообщений. Пример
Алгоритм решения задачи ЕГЭ В1 По условию задачи за одну секунду можно передать один из трех специальных сигналов. Сообщение передается N секунд. Необходимо найти число всех возможных сообщений, состоящих из трёх видов сигналов и передаваемое за N секунд. Для этого воспользуемся комбинаторной формулой для нахождения числа размещений с повторениями  . То есть для данной задачи количеством различных сообщений будет число 3N. Так как в Паскале нет реализации для функции nm, то для подсчёта числа 3N за линейное время можно воспользоваться свойством логарифмов  . Число а может быть любым, для удобства пусть оно будет равным числу е. Получим:  . Далее упростим полученное выражение, воспользовавшись свойством логарифма  . Получим:  . Эту формулу можно реализовать в Паскале, воспользовавшись функциями взятия экспоненты 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. Сейф
Вася был величайшим вором всех времен и народов. Однажды он решил ограбить банк. Чтобы открыть главный сейф, ему нужно вставить три определенных ключа в соответствующие замки сейфа. Только тогда дверь откроется. Вася уже украл у директора связку ключей, в которой точно есть три нужных. Теперь он хочет оценить, сколько времени в худшем случае ему понадобится на открывание сейфа, если он успевает проверить одну комбинацию за одну секунду. Формат входных данных:Задано одно натуральное число N (3 ≤ N ≤ 104) —количество ключей в связке. Формат выходных данных:Выведите время в секундах. Пример
Алгоритм решения задачи Сейф. По условию задачи даны N ключей. Необходимо найти количество размещений без повторений этих ключей по трём замкам сейфа. Для решения этой задачи воспользуемся комбинаторной формулой для нахождения числа размещений без повторений  . То есть решением данной задачи будет число  . Чтобы упростить реализацию решения, воспользуемся свойством факториала. Получим:  . Сократим выражение (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. Шашлыки
Вася с одноклассниками пошел на шашлыки. Ему поручили следить за мангалом. Через некоторое время он заметил, что шашлыки жарятся неравномерно. Поэтому он решил положить самые поджаристые шампура туда, где меньше жара и наоборот. За один раз Вася может поменять местами два шампура. Так как они очень горячие, он хочет сделать минимальное количество перемещений. Помогите Васе подсчитать наименьшее количество перемещений шампуров учитывая, что он заранее выбрал какой шампур куда надо положить. Формат входных данных:В первой строке задано одно натуральное число N (1 ≤ N ≤ 105). Во второй строке через пробел записаны N различных чисел — номера позиций, куда нужно переместить соответствующие шампура. Все номера являются натуральными числами, не превосходящими N. Формат выходных данных:Выведите минимальное количество перемещений. Пример
Алгоритм решения задачи Шашлыки. По условию задачи даны 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. Лист в линию
На уроке русского языка Вася от скуки решил раскрасить тетрадный лист в линию, который представляет собой прямоугольник размером W×H. На нем нанесены горизонтальные и наклонные линии, разбивающие лист на кусочки. Вася решил каждый кусочек раскрасить в уникальный цвет. Какое количество различных цветов понадобится Васе? Будем считать, что прямоугольник расположен в первой координатной четверти, причем левый нижний угол расположен в начале координат, а сторона длиной W параллельна оси абсцисс. Горизонтальные линии задаются ординатами точек пересечения прямых с осью OY, а наклонные — абсциссами точек пересечения прямых с осью OX. Наклонные линии составляют угол 45° с положительным направление оси OX (см. рисунок).  Формат входных данных:В первой строке заданы четыре натуральных числа: W, H, N, M (1 ≤ W, H ≤ 105, 0 ≤ N < H, 0 ≤ M < W + H). Во второй строке записано N чисел — ординаты точек пересечения горизонтальных линий с осью OY. В третьей строке записано M абсцисс точек пересечения наклонных линий с осью OX. Гарантируется, что все линии проходят через прямоугольник (отсекают какую-то не пустую часть) и нет двух одинаковых линий. Все числа целые. Формат выходных данных:Выведите количество различных цветов. Пример
Алгоритм решения задачи "Лист в линию". Выводим решения задачи в крайних случаях 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. |