Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Количество элементов, больших обоих соседей#42271

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

Входные данные

Сначала задано число N - количество элементов в массиве (1 <= N <= 10000). Далее через пробел записаны N чисел - элементы массива. Массив состоит из целых чисел.

Выходные данные

Необходимо вывести количество элементов массива, у которых два соседа и которые при этом строго больше обоих своих соседей.

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 4 5	0
2	5 2 3 2 4 3	2

Алгоритмы обработки Одномерные массивы

✓ 258✗ 296500лёгкаяВойти и решать

Спрятанная карта#42268

В колоде у Громозеки находятся карты, на которых написано по одному целому числу. Каждое число в колоде встречается ровно 4 раза.
Таким образом, в колоде имеются 4 карты с числом 1, 4 карты с числом 2, ..., 4 карты с числом N. Всего в колоде 4*N карт.

Громозека перетасовал эти карты, а затем спрятал одну из них и дал вам стопку оставшихся 4*N-1 карт. На i-й карте (1<= i <=4*N−1) из стопки написано целое число A_i.

Найдите целое число, записанное на карте, которую спрятал Громозека.

Входные данные
Программа получает на вход две строки. Первая строка содержит целое число N (1 <= N <= 10⁵). Вторая строка содержит 4*N-1 целых чисел A_i (1 <= Ai <= 4*N−1. 1<= i <=4*N−1). Для каждого k (1<=k<=N) существует не более 4 индексов i, таких, что A_i=k.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 2 3 3 2 2 1 1 1 2	3
2	1 1 1 1	1
3	4 3 2 1 1 2 4 4 4 4 3 1 3 2 1 3	2

Алгоритмы обработки Одномерные массивы

✓ 69✗ 151600лёгкаяВойти и решать

Кривая дракона#42263

Сегодня мальчик Саша на уроке математики узнал про фракталы. Учитель показывал так называемую «кривую дракона». Она представляет собой геометрическую фигуру, которая строится следующим образом: на первом шаге проводится отрезок из начала координатной плоскости в точку (0; 1). Далее на каждом шаге из конца фрактала повторяется уже нарисованная часть фигуры, повернутая на 90 градусов против часовой стрелки (см. рисунок).

После уроков Саша попробовал сам изобразить «кривую дракона», и теперь он хочет знать, в какой точке координатной плоскости он закончил рисовать фрактал, проделав описанные выше N шагов. Требуется написать программу, которая по заданному числу N определяет координаты конца фрактала после выполнения N шагов.

Входные данные
Вводится одно целое число N (1 <= N <= 30).

Выходные данные
Выведите два числа через пробел - координаты конца фрактала.

Примеры

№	Входные данные	Выходные данные
1	2	1 1
2	4	2 -2

Арифметические алгоритмы (Теория чисел)Циклы

✓ 24✗ 40600лёгкаяВойти и решать

Середина отрезка#42262

Громозека и Алиса играют в следующую игру. Изначально, они ставят на числовую прямую три точки в целые координаты. Затем, один из них стирает любую крайнюю точку и ставит ее посередине между двумя оставшимися в координату с целым числом. Если между оставшимися точками четное количество целых чисел, то можно поставить точку в любую из них.

Например, если изначально стояли точки в координатах 3, 6, 8, то первым ходом можно стереть точку с координатой 3 и поставить ее в координату 7. Или стереть точку с координатой 8 и поставить ее в координату 4 или 5.

Чтобы долго не думать, Громозека и Алиса решили, что на каждый ход они будут тратить не более двух секунд.

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

Входные данные
Программа получает на вход три целых числа A, B и C (1<=A < B < C <= 1000). Каждое число записано с новый строки.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	3 6 8	4

Целые числа Циклы

✓ 16✗ 371 000средняяВойти и решать

Количество элементов, равных максимальному#42260

Последовательность состоит из натуральных чисел и завершается числом 0. Определите, какое количество элементов этой последовательности, равны ее наибольшему элементу.

Входные данные
Вводится последовательность целых чисел, оканчивающаяся числом 0 (само число 0 в последовательность не входит, а служит как признак ее окончания).

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	5 4 8 8 8 0	3

Алгоритмы обработки Цикл while

✓ 135✗ 216600лёгкаяВойти и решать

Меню для школьника#42255

Питание школьника, при грамотной организации, должно обеспечивать содержание белков, жиров и углеводов в соотношении 10%:30%:60% (допускается погрешность +/- 1%). Детский лагерь составляет меню, состоящее из N различных продуктов. Для каждого продукта известна энергетическая ценность в белках (P), жирах (F) и углеводах (C), а также количество каждого вида продукта в меню (K).

Определите, является ли составленное меню сбалансированным или нет.

Входные данные
Программа получает на вход несколько строк. В первой строке записано число натуральное число N (N <= 100) количество различных продуктов. В каждой из следующих N строк записаны по 4 числа: P_i, F_i, C_i и K_i. Все числа вещественные, не превосходят 10³.

Выходные данные
Выведите YES, если меню сбалансированное, и NO в противном случае.

Примеры

№	Входные данные	Выходные данные
1	3 0 1 1 2 1 2 7 1 3 7 13 1	YES

Вещественные числа Циклы

✓ 51✗ 262800средняяВойти и решать

Последняя ненулевая факториала#42251

Для заданного натурального N найдите последнюю ненулевую цифру числа N!.

Входные данные
Программа получает на вход целое число N (0 <= N <= 10⁶).

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	8	2
2	10	8

Остатки теория чисел Цикл for

✓ 22✗ 176900средняяВойти и решать

1/0!+1/1!+1/2!+...#42247

По данному натуральному числу N найдите сумму чисел \(1 + {1\over {1!}} + {1 \over {2!}} + {1 \over {3!}}+... + {1 \over {N!}}\). Количество действий должно быть пропорционально N.

Входные данные
Программа получает на вход натуральное число N.

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

Примеры

№	Входные данные	Выходные данные
1	1	2

Вычисление по заданной формуле Цикл for

✓ 76✗ 639700средняяВойти и решать

Геометрическая прогрессия#42246

По данному действительному числу a и натуральному n вычислите сумму \(1+a+a^2+...+a^n\), не используя формулу суммы геометрической прогрессии. Время работы программы должно быть пропорционально n.

Входные данные
Программа получает на вход два неотрицательных числа. В певрой строке записано действительное (вещественное) число a, во второй - целое число n.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	2 2	7

Линейные алгоритмы Цикл for

✓ 77✗ 796800средняяВойти и решать

Степень#42245

Напишите программу, вычисляющую \(2^N\).

Входные данные
Программа получает на вход натуральное число N (N<=30).

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	4	16

Быстрое возведение в степень Цикл for

✓ 115✗ 266300лёгкаяВойти и решать

Водолей#42244

У исполнителя “Водолей” есть два сосуда, первый объемом A литров, второй объемом B литров, а также кран с водой. Водолей может выполнять следующие операции:

Наполнить сосуд A (обозначается >A).
Наполнить сосуд B (обозначается >B).
Вылить воду из сосуда A (обозначается A>).
Вылить воду из сосуда B (обозначается B>).
Перелить воду из сосуда A в сосуд B (обозначается как A>B).
Перелить воду из сосуда B в сосуд A (обозначается как B>A).

Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью опустошается, либо второй сосуд полность наполняется.

Входные данные
Программа получает на вход три натуральных числа A, B, N, не превосходящих 10⁴.

Выходные данные

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

Количество операций в алгоритме не должно превышать 10⁵. Гарантируется, что если задача имеет решение, то есть решение, которое содержит не более, чем 10⁵ операций.

Примеры

№	Входные данные	Выходные данные
1	3 5 1	>A A>B >A A>B
2	3 5 6	Impossible

Цикл while Циклы

✓ 29✗ 225900средняяВойти и решать

Программа для Громозеки#42243

Когда Громозека держит в руках сразу две печеньки с числами, он сразу пробует преобразовать большее число в меньшее. При преобразовании он использует только две команды: “Вычесть 1” и “Разделить на 2”, первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное, иначе происходит ошибка. Громозека любит, чтобы преобразование происходило как можно быстрее. Помогите Громозеке составить последовательность команд, при которой из большего числа получится меньшее, причем за наименьшее количество команд.

Входные данные
Программа получает на вход два натуральных числа A и B (по одному числу в строке). A >= B.

Выходные данные
Выведите последовательность команд преобразования. Каждая команда должна выводиться в отдельной строке. Первая команда обозначается, как -1, вторая команда как :2.

Примеры

№	Входные данные	Выходные данные
1	`21 2`	`-1 :2 :2 -1 :2`

Жадный алгоритм Задачи на моделирование

✓ 155✗ 344600лёгкаяВойти и решать

Номер числа Фибоначчи#42242

Дано натуральное число A > 1. Определите, каким по счету числом Фибоначчи оно является, то есть выведите такое число n, что f_n=A. Если A не является числом Фибоначчи, выведите число -1.

Входные данные
Программа получает на вход натуральное число.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	8	6
2	10	-1

Рекуррентные последовательности Цикл while

✓ 4✗ 1900средняяВойти и решать

Двоичный логарифм#42239

По данному натуральному числу N выведите такое наименьшее целое число k, что \(2^k >= N\).

Входные данные
Программа получает на вход натуральное число N.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	10	4

Двоичная система счисления Цикл while

✓ 55✗ 167400лёгкаяВойти и решать

Степени двойки#42237

По данному числу N распечатайте все целые степени двойки, не превосходящие N, в порядке возрастания. Операцией возведения в степень пользоваться нельзя!

Входные данные
Программа получает на вход натуральное число.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	`30`	`1 2 4 8 16`

Двоичная система счисления Цикл while

✓ 11✗ 10700средняяВойти и решать

Список квадратов#42235

Выведите все точные квадраты натуральных чисел, не превосходящие данного числа N.

Входные данные
На вход подается натуральное число N.

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

Цикл for Цикл while

✓ 50✗ 142500лёгкаяВойти и решать

Разность времен#41231

Даны значения двух моментов времени, принадлежащих одним и тем же суткам: часы, минуты и секунды для каждого из моментов времени. Известно, что второй момент времени наступил не раньше первого. Определите, сколько секунд прошло между двумя моментами времени.

Входные данные
Программа на вход получает три целых числа — часы, минуты, секунды, задающие первый момент времени и три целых числа, задающих второй момент времени.

Выходные данные
Выведите число секунд между этими моментами времени.

Примеры

№	Входные данные	Выходные данные
1	1 1 1 2 2 2	3661
2	1 2 30 1 3 20	50

Вывод формулы Целые числа

✓ 296✗ 287400лёгкаяВойти и решать

Лабораторные столы#41230

На кафедру "Прикладной информатики" университета N в новом учебном году набрали три группы первокурсников. Для практических занятий необходимо оборудовать новую аудиторию лабораторными столами. За каждым таким столом могут сидеть не более четырех студентов, причем все студенты обязаны быть из одной группы. Аудитория имеет возможность одновременно разместить студентов сразу трех групп одновременно.
Определите минимальное количество столов, которые необходимо закупить.

Входные данные
Программа получает на вход три натуральных числа (по одному числу в строке): количество студентов каждой из трех групп.

Выходные данные
Выведите ответ на задачу.

Примеры

№	Входные данные	Выходные данные
1	15 20 24	15

Вывод формулы Целые числа

✓ 1 999✗ 2 948300лёгкаяВойти и решать

Инверсии на отрезке#41229

Дана перестановка из n элементов.
Ответьте на m запросов про число инверсий для подотрезка перестановки от l до r.
Инверсией называется пара индексов i, j такая, что i < j и a_i > a_j, где a_i - это i-й элемент перестановки.

Входные данные:
В первой строке задано число n (1 <= n <= 10⁵).
Во второй строке задана перестановка из n элементов (элементы перестановки - попарно различные целые числа от 1 до n).
В третьей строке задано число m (1 <= m <= 10⁵).
В последующих m строках содержится по два числа l и r - границы запроса (1 <= l, r <= n).

Выходные данные:
Выведите m строк - ответы на данные запросы.

Примеры:

Входные данные	Выходные данные
5 4 5 2 3 1 3 1 3 3 5 1 5	2 2 8
6 5 2 4 3 1 6 3 4 6 2 5 1 5	1 4 8

Алгоритм Мо Дерево отрезков, RSQ, RMQ

✓ 14✗ 28900средняяВойти и решать

XOR и любимое число#41228

У Эвана есть любимое число k и массив a_i длины n. Теперь он просит вас ответить на m запросов.

Для каждого запроса, задаваемого парой чисел l и r, требуется найти количество пар целых чисел i и j таких, что l ≤ i ≤ j ≤ r и xor чисел a_i, a_i + 1, ..., a_j равен k.

Входные данные:
В первой строке даны целые числа n, m и k (1 ≤ n, m ≤ 10⁵, 0 ≤ k ≤ 10⁶) — длина массива, количество запросов и любимое число Эвана соответственно.
Во второй строке записаны n целых чисел ai (0 ≤ a_i ≤ 10⁶) — имеющийся у Эвана массив.
Дальше идут m строк. В i-й строке записаны числа l_i и r_i (1 ≤ l_i ≤ r_i ≤ n), определяющие i-й запрос.

Выходные данные:
Выведите m строк, ответы на запросы в порядке их появления во входных данных.

Примеры:

Входные данные	Выходные данные
6 2 3 1 2 1 1 0 3 1 6 3 5	7 0
5 3 1 1 1 1 1 1 1 5 2 4 1 3	9 4 4

Алгоритм Мо Префиксные суммы(минимумы, ...)

✓ 3✗ 01 100средняяВойти и решать