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

Космическая дорожная карта#42269

Дениска хочет отправиться в космическое путешествие на кораблях с варп-двигателями. Для этого он купил космическую дорожную карту. На первой открытой межгалактической варп-линии, управляемой МТК (Межзвездной транспортной компанией), есть N станций. i-я станция (1<=i<=N) от начальной станции называется S_i.
Обычные космические корабли останавливаются на всех станциях, в то время как варп-корабли (космические корабли с варп-двигателями) останавливаются только на M (M <= N) станциях, а j-я станция (1 <= j <= M) - это станция с именем T_j.
Здесь гарантируется, что T₁ = S₁ и T_M= S_N , то есть варп-корабли останавливаются как на начальной, так и на конечной станциях.
Дениска хочет прокатиться на варп-корабле. Для каждой из N станций определите, сможет ли Дениска попасть на эту станцию на варп-корабле.

Входные данные
Программа получает на вход три строки. Первая строка содержит два целых числа N и M (2 <= M <= N <=10⁵). Вторая строка содержит N различных слов S_i (1 <= i <= N, ), разделенных пробелом - название станций, на которых останавливаются обычные космические корабли. Третья строка содержит M различных слов T_j (1 <= j <= M, ), разделенных пробелом - название станций, на которых останавливаются варп-корабли. Все слова в третьей строке (T₁,...,T_M) получается путем удаления нуля или более строк из (S₁,...,S_N) и выстраиванием оставшихся слов в ряд, не меняя порядок.

Выходные данные
Выведите N строк. i-я строка (1<= i <=N) должна содержать Yes, если Дениска доберется на варп-корабле до i-й станции от начальной станции, иначе - No.

Примеры

№	Входные данные	Выходные данные
1	5 3 andoria kanda badjor betazed ueno andoria badjor ueno	Yes No Yes No Yes
2	7 7 a b c d e f g a b c d e f g	Yes Yes Yes Yes Yes Yes Yes

Множества

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

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

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

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

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

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

Примеры

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

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

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

Генератор степеней двойки#42259

Генератор степеней двойки работает следующим образом. Каждую секунду, начиная с первой, он печатает на экране все степени двойки, значение которых, не превосходит текущую секунду.
Пример первых чисел, которые выдает генератор:
1 1 2 1 2 1 2 4 ...

По заданному числу n, выведите на экран первые n чисел, которые напечатает на экране генератор.

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

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

Примеры

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

Вложенные циклы

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

3A+5B#42254

Многие натуральные числа можно представить в виде N = 3A + 5B, где A и B - целые неотрицательные числа. Например, 11=3x2+5x1, 20=3x0+5x4.

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

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

Выходные данные
Программа должна вывести два целых неотрицательных числа A и B, разделенных пробелом, если такие числа существуют. В противном случае выведите слово IMPOSSIBLE. Если решений несколько, выведите любое из них.

Примеры

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

Условный оператор

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

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

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

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

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

Примеры

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

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

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

Степень#42245

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

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

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

Примеры

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

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

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

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

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

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

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

Примеры

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

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

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

Утренняя пробежка#42240

В первый день спортсмен пробежал x километров, а затем он каждый день увеличивал пробег на 10% от предыдущего значения. По данному числу y определите номер дня, на который пробег спортсмена составит не менее y километров.

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

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

Примеры

№	Входные данные	Выходные данные
1	10 20	9

Цикл while

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

Примеры

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

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

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

Наименьший делитель#42236

Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель, отличный от 1.

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

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

Примеры

№	Входные данные	Выходные данные
1	25	5

Цикл for

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

Длина равных#42234

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

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

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

Примеры

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

Цикл while

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

Соревнование по шахматной композиции#42232

На соревнованиях по шахматной композиции каждому участнику дается 10 задач для решения. За каждую задачу можно получить от 0 до 5 баллов. За правильно решенную задачу участнику начисляется 5 баллов. Если задача решена не полностью или не верно, то участнику дается вторая попытка. В этом случае за задачу участник получает балл равный среднему баллу за две попытки, округленный по правилам математики.
Баллы выставляются по порядку от первой до последней решенной задачи.

Маленький Витя Ч., участвуя на своем первом в жизни соревновании, забыл сколько задач он решил. Витя Ч. помнит, что получил всего 10 оценок, а также сами оценки по порядку.
Определите сколько всего задач решил Витя Ч., за сколько задач он получил максимальный балл с первой попытки, а также общую сумму баллов, которую он набрал.

Входные данные
Программа получает 10 строк, в каждой из которых записано по одному неотрицательному числу от 0 до 5.

Выходные данные
Выведите в первой строке количество задач, которые Витя Ч. успел решить, во второй строке - количество задач, которые решил с первой попытки на максимальный балл, в третьей строке - общее количество набранных баллов.

Примеры

№	Входные данные	Выходные данные
1	2 5 2 5 0 5 5 2 5 5	6 2 25

Циклы

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

Соседние квадраты#42231

Существует сетка с H горизонтальными строками и W вертикальными столбцами. Пусть (i, j) обозначает квадрат в i-й строке сверху и в j-м столбце слева.
Найдите количество квадратов, которые имеют общую сторону с квадратом (R, C).

Квадрат (a, b) и квадрта (c, d), имеют одну общую сторону тогда и только тогда, когда |a-c|+|b-d|=1 (где |x| обозначает абсолютное значение x).

Входные данные
Програма получает на вход две строки. Первая строка содержит два целых числа H и W (1 <= H, W <= 10). Вторая строка содержит два целых числа R и C (1 <= H, W <= 10).

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

Примеры

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

Изображение сетки, для описанных выше примеров

Условный оператор

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

Большая шахматная доска#42230

Плитки выровнены по N горизонтальным строкам и N вертикальным столбцам. Каждая плитка имеет сетку с A горизонтальными рядами и B вертикальными столбцами. Все плитки образуют квадрат X с (A×N) горизонтальными строками и (B×N) вертикальными столбцами.
Для 1<= i, j<= N плитка (i, j) обозначает плитку в i-й строке сверху и в j-м столбце слева.

Каждый квадрат X окрашен следующим образом.

Каждая плитка представляет собой либо белую плитку, либо черную плитку.
Каждый квадрат в белой плитке окрашен в белый цвет; каждый квадрат в черной плитке окрашен в черный цвет.
Плитка (1, 1) - это белая плитка.
Две плитки, разделяющие одну сторону, имеют разные цвета. Плитка (a, b) и плитка (c, d), имеют одну общую сторону тогда и только тогда, когда |a-c|+|b-d|=1 (где |x| обозначает абсолютное значение x).

Распечатайте квадрат X в формате, указанном в формате.

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

Выходные данные
Выведите на экран (A×N) строк S₁,...,S_AxN, которые удовлетворяют следующим условиям.
Каждая из строк S₁,...,S_AxNпредставляет собой строку длины (B×N), состоящую из . и #.
Для каждого значения i и j (1<= i <= A×N,1 <= j <= B×N) j-й символ строки S_i является символом . ,если квадрат в i-й строке сверху и j-м столбце слева в квадрате X окрашен в белый цвет; символом #, если квадрат окрашен в черный цвет.

Примеры

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

Вложенные циклы

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

Мощный массив#41227

Имеется массив натуральных чисел a₁, a₂, ..., a_n. Рассмотрим некоторый его подмассив a_l, a_l + 1, ..., a_r, где 1 ≤ l ≤ r ≤ n, и для каждого натурального числа s обозначим через K_s число вхождений числа s в этот подмассив. Назовем мощностью подмассива сумму произведений K_s·K_s·s по всем различным натуральным s. Так как количество различных чисел в массиве конечно, сумма содержит лишь конечное число ненулевых слагаемых.

Необходимо вычислить мощности каждого из t заданных подмассивов.

Входные данные
Первая строка содержит два целых числа n и t (1 ≤ n, t ≤ 200000) — длина массива и количество запросов соответственно.
Вторая строка содержит n натуральных чисел ai (1 ≤ a_i ≤ 10⁶) — элементы массива.
Следующие t строк содержат по два натуральных числа l и r (1 ≤ l ≤ r ≤ n) — индексы левого и правого концов соответствующего подмассива.

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

Примеры:

Входные данные	Выходные данные
3 2 1 2 1 1 2 1 3	3 6
8 3 1 1 2 2 1 3 1 1 2 7 1 6 2 7	20 20 20

Алгоритм Мо Вывод формулы

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

Шаг вправо#40082

Есть 4 квадрата, нарисованных горизонтально в ряд.

Вам дана строка S длиной 4, состоящие из 0 и 1.
Если i-й символ S равен 1, в i-м квадрате слева есть человек;
если i-й символ S равен 0, в i-м квадрате слева нет человека.

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

Выведите результат в виде строки в том же формате, что и S. (Для наглядности см. пример ввода / вывода).

Входные данные
На вход подается строка S длиной 4, состоящие из 0 и 1.

Выходные данные
Выведите строку длиной 4. i-й символ должен быть равен 1, если в i-м квадрате слева после перемещения будет человек, и 0 в противном случае.

Примеры

№	Входные данные	Выходные данные
1	1011	0101
2	1111	0111

Строки

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

Слаймы#40063

У Громозеки есть A слаймов. Каждый раз, когда Громозека чихает, количество слаймов увеличивается в K раз. Какое минимальное количество раз Громозеке нужно чихнуть, чтобы получить B или больше слаймов?

Входные данные
На вход подается три целых положительных числа A, B (1 <= A <= B <= 10⁹), K (2 <= K <= 10⁹).

Выходные данные
Выведите на экран ответ на задачу

Примеры

№	Входные данные	Выходные данные
1	1 4 2	2
2	31 415926 5	6

Цикл while

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

Замена букв, исключая первую и последнюю#39831

Программа заменяет в строке s все буквы 'h' на 'H', кроме первого и последнего вхождения. Вставьте пропущенные строки.

Примеры

№	Входные данные	Выходные данные
1	`In the hole in the ground there lived a hobbit`	`In the Hole in tHe ground tHere lived a hobbit`

Задачи на процедуры и функции

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

Количество счастливых шестизначных#39829

Определите количество шестизначных «счастливых» чисел. «Счастливым» будем называть такое шестизначное число, в котором сумма его первых трех цифр равна сумме его последних трех цифр.
Заполните пропуски в программе.

Функция sum3(n) вычисляет сумму цифр трехзначного числа.
Функция happy(n) определяет является ли число n счастливым. Функция happy(n) для своей работы использует функцию sum3(n).

Задачи на процедуры и функции

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