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

Слова из слова#21958

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

Примеры

№	Входные данные	Выходные данные
1	informacia forma	YES
2	informacia moloko	NO

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

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

Редкие буквы#21957

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

Примеры

№	Входные данные	Выходные данные
1	processor informacia	penfm

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

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

Мама мыла раму#21956

Дано предложение. Выведите его на экран в обратном порядке.

Примеры

№	Входные данные	Выходные данные
1	mama myla ramu	ramu myla mama

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

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

А роза упала на лапу Азора#21955

Дано предложение. Вывести слово YES, если предложение является палиндромом (после удаления всех пробелов) и NO - в противном случае.

Примеры

№	Входные данные	Выходные данные
1	A ROZA UPALA NA LAPU AZORA	YES
2	POT KAK POTOP	NO

Одномерные массивы Строки

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

Ремонт асфальта#21954

Улица М. города Д. печально известна среди местных жителей качеством дорожного покрытия. В этом тяжело винить ремонтные службы: пожалуй, они следят за этой улицей даже слишком тща- тельно. Проблема в том, что каждый без исключения ремонт улицы выглядит следующим образом: бригада рабочих выбирает некоторый участок улицы единичной длины и меняет асфальт только на нём, причём тип асфальта на этом участке в результате может отличаться от типов асфальта на других участках, что, разумеется, усложняет проезд по улице.

Вы, как коренной житель города Д. и программист по призванию, решили использовать свои профессиональные навыки на благо общества и облегчить жизнь своим соседям по улице М. А именно, вы решили создать сайт, содержащий актуальную информацию о непроходимости улицы. Прежде всего, вы заметили, что улица разбита на N идущих друг за другом участков единичной длины. По странному совпадению бригада рабочих всегда выбирает для ремонта ровно один из таких участков и целиком меняет тип асфальта на нём. Затем вы пронумеровали эти участки от 1 до N и собрали информацию о типе асфальта на каждом из участков — числа t1, t2, . . . , tN (ti — номер типа асфальта на i-м участке, согласно Государственному реестру дорожных покрытий). Наконец, вы определили непроходимость улицы как минимальное количество непрерывных непересекающихся отрезков c одинаковым типом асфальта, на которые она разбивается. Например, непроходимость улицы 110111 равна 3, потому что она состоит из трёх участков 11, 0 и 111, а идеальная улица 2222 имеет непроходимость, равную 1.

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

Формат входных данных
Первая строка входного файла содержит единственное натуральное число N — количество участ- ков дороги (1 <= N <= 100 000). Следующая строка содержит N целых чисел t1, t2, . . . , tN — исходные типы асфальта участков дороги (|ti | <= 109 ). Третья строка содержит единственное натуральное число Q — количество сообщений от жителей об обновлении дорожного покрытия (1 <= Q <= 100 000). Каждая из следующих Q строк содержит очередное сообщение. i-е сообщение представляет собой пару целых чисел pi , ci — номер ремонтируемого участка дороги и новый номер типа асфальта на этом участке (1 <= pi <= N, |ci | <= 109 ). Участки дороги нумеруются от 1 до N в порядке задания их исходного типа асфальта во второй строке входного файла.

Формат выходных данных
Выведите Q строк. i-я строка (1 <= i <= Q) должна содержать единственное целое число — величину непроходимости улицы после первых i обновлений дорожного покрытия.

Примеры

Ввод	Вывод
5 2 2 2 2 2 5 1 2 2 3 4 3 3 1 3 3	1 3 5 5 3
7 1 1 2 3 2 2 1 3 2 2 4 2 6 9	5 3 4

Замечание
Рассмотрим подробнее второй тестовый пример. Изначально улица 1123221 состоит из 5 отрезков с одинаковым типом асфальта: 11, 2, 3, 22, 1 и, соответственно, имеет непроходимость, равную 5 (её не нужно выводить в выходной файл).
После первого ремонта улица станет выглядеть как 1223221 и всё ещё будет состоять из 5 участ- ков, но других: 1, 22, 3, 22, 1. Поэтому её непроходимость равна 5, и первое число в выходном файле равно 5.
После второго ремонта улица будет состоять из 3 участков: 1, 22222, 1, так что второе число в выходном файле — 3.
После третьего ремонта получим 4 участка: 1, 2222, 9, 1, соответственно, третье и последнее число в выходном файле — 4.

Задача на реализацию Структуры данных

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

Британские учёные и Василий#21951

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

Вдохновившись исследованием британских учёных о восприятии человеком текста, Вася решил, что современная письменность нуждается в серьёзном упрощении. В частности, в лексиконе Васи все слова состоят только из букв a, b и c. Кроме того, память у Васи плохая, поэтому Вася помнит лишь слова, которые содержат не более L букв.

Более того, с тех пор как наш юный друг пролил кофе на свой любимый ноутбук, он не утруждает себя нажатием клавиши пробел (объясняя это тем, что и отсутствие пробелов в тексте совершенно не мешает его пониманию). Однако остальные клавиши клавиатуры работают исправно, что позволяет Васе набирать все известные ему слова без единой орфографической ошибки.

Британские учёные очень заинтересовались исследованиями Васи. Они вступили с молодым учё- ным в активную переписку, однако, получив очередное Васино сообщение были несколько озадачены тем, что же он имел ввиду. Так как разобраться они так и не смогли, а очередное революционное открытие уже было проанонсировано в СМИ, они решили как-то оценить уровень гениальности автора. Для этого они решили понять, а из какого минимального количества слов может состоять словарный запас Василия?

Формат входных данных
В первой строке входных данных содержится целое число L — максимальная длина слова, кото- рое может содержаться в лексиконе Васи (1 <= L <= 10 000). В следующей строке содержится непустое сообщение, полученное учеными. Длина сообщения не превосходит 20 000 символов.

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

Пример
Ввод:
3
ababaabab

Вывод:
2
aba
ab

Замечание
В первом примере из условия одним из возможных способов проинтерпретировать Васино сооб- щение является: ab aba ab ab.

Z-функция. Префикс-функция Строки

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

Максимум из четырех чисел#21914

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

АЛГОРИТМ

Оформите ввод четырех значений переменных с клавиатуры (каждое число записано в отдельной строке).
Присвойте значение переменной mx первой из четырех переменных.
Если значение, находящееся в переменной mx меньше значения второй переменной, то замените значение переменной mx на значение второй переменной.
Если значение, находящееся в переменной mx меньше значения третьей переменной, то замените значение переменной mx на значение третьей переменной.
Если значение, находящееся в переменной mx меньше значения четвертой переменной, то замените значение переменной mx на значение четвертой переменной.
Выведите значение переменной mx на экран.

Следуя данному алгоритму, напишите программу.

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

Выходные данные
Выведите одно число - максимальное число среди введенных чисел.

Линейные алгоритмы Условный оператор

✓ 9 264✗ 15 420200лёгкаяВойти и решать

Укладка плитки#21902

В процессе ремонта в Лаборатории Информационных Технологий строителям необходимо заменить поврежденные напольные плитки в коридоре лаборатории, который имеет размер 2 × n метров. В распоряжении строителей есть неограниченный запас плиток двух размеров: 1 × 2 метра и 1 × 1 метр. При этом плитки размером 1 × 2 метра перед укладкой разрешается поворачивать на 90 градусов и размещать как вдоль, так и поперек коридора.

Строители уже начали ремонт и уложили в некоторых местах пола коридора k плиток размером 1 × 1. Для завершения ремонта прорабу необходимо подготовить план дальнейших работ. Для этого ему надо решить, каким образом уложить плитки на места, где они еще не уложены. Это можно сделать различными способами и прораб хочет перебрать все варианты и выбрать самый удачный. Перед тем как это сделать, прораб хочет знать, какое количество вариантов ему придется рассмотреть. Это число требуется найти по модулю 10⁹ + 7.

Требуется написать программу, которая по заданной длине коридора n и расположению плиток, которые уже уложены, определяет количество способов укладки плиток на оставшиеся места. Ответ необходимо вывести по модулю 10⁹ + 7.

Формат входного файла
Первая строка входного файла содержит два целых числа: n — длину коридора и k — количество уже уложенных единичных плиток (1 ≤ n ≤ 100 000, 0 ≤ k < 2n). Последующие k строк содержат по два целых числа xi и yi , которые задают позиции уже уложенных единичных плиток, i-я плитка уложена на xi-м метре коридора в yi-м ряду (1 ≤ xi ≤ n, 1 ≤ yi ≤ 2).

Формат выходного файла
Выходной файл должен содержать одно целое число — количество способов укладки плиток в коридоре, взятое по модулю 10⁹ + 7.

Ввод	Вывод
2 0	7
3 0	22
3 1 2 1	8

Динамическое программирование по профилю Динамическое программирование: один параметр

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

Вычисление арифметических выражений#21882

Постфиксная запись представляет собой такую запись алгебраического выражения, в которой сначала записываются операнды, а затем – знак операции. Например, для выражения a + b * c постфиксная запись будет a b c * +.

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

Входные данные
На вход подается символьная строка. Знак / в записи означает целочисленное деление.

Выходные данные
Выведите на экран результат выражения.

Примеры

№	Входные данные	Выходные данные
1	5 3 + 7 4 - *	24

Разбор выражений Стек

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

Скобки#21877

Напишите программу, которая проверяет правильность расстановки скобок в арифметическом выражении. Используются скобки трёх типов: ( ), [ ] и { }.

Входные данные
На вход подается строка.

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

Примеры

№	Входные данные	Выходные данные
1	(5+7)[5+{(4+3)[9-6]+7}-8]	Yes
2	[(2+3)	No

Задача на реализацию Стек

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

Раскраска отрезков#21847

У Джона Доу есть n отрезков на прямой. Отрезок (a, b) (a < b) — это множество точек x, таких, что a < x < b. Говорят, что отрезки (a1, b1) и (a2, b2) пересекаются, если существует такая точка c, что a1 < c < b1 и a2 < c < b2.

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

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

Пусть количество способов покрасить отрезки равно x. Выведите остаток от деления x на 10⁶ + 3.

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

В первой строке записано целое число n (1 ≤ n ≤ 10⁵) — количество отрезков у Джона. В следующих n строках находится описание отрезков. В i-й из них записано два числа li и ri (0 ≤ li < ri ≤ 10⁹) — координаты концов i-го отрезка.

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

Выведите остаток от деления x (количество способов покрасить отрезки) на 10⁶ + 3.

Примеры тестов

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

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

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

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

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

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

Примечание

Тесты поделены на группы, но оцениваются отдельно.

n ≤ 3 — 10 баллов
n ≤ 15 — 30 баллов
n ≤ 100 — 20 баллов
ai ≤ 10⁶ — 20 баллов
Без дополнительных ограничений — 20 баллов

Использование сортировки Сканирующая прямая

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

Разности#21846

У Джона Доу есть массив a из n элементов. Джон хочет найти величину , то есть сумму квадратов разностей элементов массива по всем возможным парам i, j.

Например для массива {1, 2, 3} такая величина будет равна (1 - 1)2 + (1 - 2)2 + (1 - 3)2 + (2 - 1)2 + (2 - 2)2 + (2 - 3)2 + (3 - 1)2 + (3 - 2)2 + (3 - 3)2 = 0 + 1 + 4 + 1 + 0 + 1 + 4 + 1 + 0 = 12

Найдите остаток от деления S на 10⁸.

Напомним, как работать с остатками от деления. Остаток от деления числа a на число b обозначим как . Верны следующие соотношения:

(для a ≥ b).

К примеру, вы хотите посчитать величину . Перемножить эти три числа в стандартном типе данных вам не удастся, но можно воспользоваться первым соотношением и посчитать сначала Теперь можно перемножить получившееся число и 107 + 3 и получить .

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

В первой строке записано целое число n (1 ≤ n ≤ 10⁶) — количество элементов массива. Во второй строке через пробел записаны n целых чисел a1, ..., an (1 ≤ a_i ≤ 10⁹).

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

Выведите остаток от деления S на 10⁸.

Примеры тестов

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

3
1 2 3

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

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

5
100 1 9 1 3

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

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

2
1000000000 1

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

Примечание

Тесты поделены на несколько групп, но оцениваются отдельно.

n, a_i ≤ 1000 – 10 баллов
n ≤ 5000 – 10 баллов
n ≤ 10⁶ a_i≤ 5000 – 30 баллов
Без дополнительных ограничений — 50 баллов

Например, если вы решили задачу для n ≤ 5000 и произвольных a_i вы получите 20 баллов (первая и вторая группы).

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

✓ 2✗ 1141 200средняяВойти и решать

Стоимость покупок#21842

Кролик Клевер хочет написать программу, которая бы помогала ему рассчитывать стоимость покупок в магазине. Кролик хочет купить себе b морковок по n рублей каждая. Помогите ему составить такую программу.
Составьте программу по следующему алгоритму:
1. задайте значения целочисленным переменным b и n с клавиатуры (каждое значение записано в отдельной строке);
2. напишите оператор вывода, который выведет на экран, сколько рублей придется заплатить Кролику.

Примеры

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

Ввод, вывод данных Целые числа

✓ 18 376✗ 42 577100лёгкаяВойти и решать

Жизнь#21839

Дмитрий работает биологом и недавно открыл новый вид бактерий, которые живут в необычных условиях — в таблицах размером 10 на 10 ячеек. Табличные бактерии состоят из нескольких живых клеток. Дмитрий вычислил, что бактерия существует по следующим правилам:

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

Соседями ячейки являются ближайшие ячейки по горизонтали (справа и слева), по вертикали (снизу и сверху), а также по четырём диагоналям. Таким образом, у ячейки может быть максимум 8 соседей.

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

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

Ввод состоит из 10-ти строк. Каждая строка содержит в себе 10 символов. Символ '#' означает, что в соответствующей ячейки находится живая клетка бактерии, а символ '.' означает, что ячейка пуста.

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

Необходимо вывести таблицу 10 на 10 — изображение бактерии в следующий момент времени.

Алгоритмы обработки Задача на реализацию

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

Твоя игра#21837

В интеллектуальном шоу «Твоя игра» принимают участие 3 человека. Им даются 5 тем, каждая из которых содержит по 5 вопросов стоимостью 100, 200, 300, 400 и 500 баллов. Если игрок правильно отвечает на вопрос, то к его текущей сумме прибавляется стоимость вопроса, если же он допускает ошибку, то от его суммы стоимость вопроса отнимается. При этом у игрока может оказаться отрицательная сумма баллов.

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

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

В первой строке находится три последовательности символов, разделённые пробелом — имена участников. Имя начинается с заглавной буквы, остальные буквы являются строчными. Имя участника содержит не более 10 и не менее 2 букв, все буквы латинские.

В следующих строках содержится информация о сыгранном вопросе. Сперва идёт имя участника, отвечавшего на вопрос, а через пробел — полученная им сумма баллов. Если количество баллов положительно, то ответ оказался правильным, если же отрицательно, то игрок ошибся. Гарантируется, что разыгранное количество вопросов каждой стоимости (100, 200, 300, 400 и 500) не превосходит 5. Также гарантируется, что во время игры будет разыгран хотя бы один вопрос.

В последней строке находится надпись «GAME OVER», означающая, что игра окончена и больше вопросов не будет.

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

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

Ввод:

Artur Dmitry Fedor

Artur -500

Dmitry 400

Fedor 100

Artur 400

Fedor 200

Fedor 100

Artur 500

GAME OVER

Вывод:

-500 0 0

-500 400 0

-500 400 100

-100 400 100

-100 400 300

-100 400 400

400 400 400

Задача на реализацию Задачи на моделирование

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

Числа без цифры 8#21836

Напишите функцию, определяющую есть ли в записи числа цифры 8.

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, подсчитывает количество чисел, в записи которых нет цифры 8
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно число, количество чисел, в записи которых нет цифра 8

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 22 94 66 18 18	3
2 21 46	2

Задача на реализацию Строки

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

Число с максимальной первой цифрой#21833

Напишите функцию, вычисляющую первую цифру числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальной первой цифрой
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100)
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно число, у которого первая цифра максимальна среди всех чисел, если таких чисел несколько, то необходимо вывести число, которое встретилось в последовательности раньше

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 43 22 11 56 10	56
2 14 22	22

Алгоритмы обработки Задачи на процедуры и функции

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

Число с максимальной суммой цифр#21832

Напишите функцию, вычисляющую сумму цифр числа

Используя данную функцию, напишите программу, которая среди n натуральных чисел, вводимых с клавиатуры, выводит на экран число с максимальной суммой цифр
Входные данные:
в первой строке вводится число n - количестве чисел (n<=100),
далее идут n строк по одному натуральному числу в строке
Выходные данные:
программа должна вывести одно число, в котором сумма цифр максимальна среди всех чисел

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию!).

Пример

Ввод	Вывод
5 43 22 11 56 10	56
2 34 12	34

Алгоритмы обработки Задачи на процедуры и функции

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

Кратность 11#21831

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

Используя данную функцию, напишите программу, которая запрашивает у пользователя число n (0<=n<=100000) и выводит на экран фразу multiple of 11, если число кратно 11 и фразу not multiple of 11, если число не кратно 11

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию или функция вычисляет кратность не по приведенному алгоритму!).

Пример

Ввод	Вывод
1	not multiple of 11
11	multiple of 11

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

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

Кратность 9#21830

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

Используя данную функцию, напишите программу, которая запрашивает у пользователя число n (0<=n<=100000) и выводит на экран фразу multiple of 9, если число кратно 9 и фразу not multiple of 9, если число не кратно 9

Количество баллов за задачу уточняется после ручной проверки (и будет снижено, в случае если вы не используете функцию или функция вычисляет кратность не по приведенному алгоритму!).

Пример

Ввод	Вывод
3	not multiple of 9
9	multiple of 9

Задачи на процедуры и функции Условный оператор

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