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

На связи#26983

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

Владимир, как истинный программист, решил заменить все цифры в своем сообщении на их названия на английском языке:

0 - zero
1 - one
2 - two
3 - three
4 - four
5 - five
6 - six
7 - seven
8 - eight
9 - nine

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

Формат ввода

В единственной строке введена строка s — сообщение Владимира для Даши. Строка может содержать любые символы с ASCII-кодами от 32 до 126. Длина строки не превосходит 4 × 10⁶.

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

Выведите измененное сообщение Владимира, в котором каждая цифра заменена на её название на английском языке.

Пример

Ввод	Вывод
Dashka, I love you!!! <3	Dashka, I love you!!! <three

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

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

Пути в музее#26978

Болик добрался до музея, здание которого представляет собой квадрат N × N, разбитый на N² равных квадратных залов. Вход в музей расположен в левом нижнем зале, а Лёлик ждет Болика в правом верхнем. Из каждого зала можно пройти в соседний с ним зал (два зала называются соседними, если у них есть общая стена).

Теперь Болик хочет определить сколько возможных путей до Лёлика у него есть. Конечно, его интересуют только пути кратчайшей длины.

Формат ввода

На вход подается одно натуральное число N (2 ≤ N ≤ 22).

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

Выведите единственное натуральное число — количество различных путей наименьшей длины.

Пример

Ввод	Вывод
3	6

Динамическое программирование: один параметр Комбинаторика

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

Достать шоколадку#26977

Лёлик пришел в школу и решил подкрепиться шоколадкой. Он подошел к автомату с шоколадками и с удивлением обнаружил, что на него поставили защиту от первоклассников. А именно, для того, чтобы достать шоколадку, необходимо решить уравнение ax + b = c. Программа безопасности просит ввести целую часть корня этого уравнения, слово NO, если корней нет, или INFINITY, если корней бесконечно много. Чтобы ежедневно покупать шоколадки, Лёлик решил написать программу для решения уравнения, но не смог. А вы сможете?

Формат ввода

На вход подаются три действительных числа, разделенных пробелом: a, b, и c. Все числа по модулю не превышают 10⁹.

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

Выведите решение уравнения. Решением может являться либо целое число - целая часть корня уравнения,корня уравнения, либо слово NO, если корней нет, либо INFINITY, если корней бесконечно много.

Пример

Ввод	Вывод
2 3 0	-2

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

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

Поход в музей#26976

Лёлик наконец решил просветиться, и пошел в музей. В музее ему так понравилось, что он решил позвать туда своего друга Болика. Болик захотел присоединиться к своему другу, однако ему нужно доехать на автобусе №154 до метро, затем проехать три станции на метро, после чего проехать на автобусе №93 до музея. Помимо этого Болику нужно купить билет в музей. Теперь Болик хочет посчитать сколько денег ему нужно, чтобы встретиться с Лёликом в музее.

Известно, что проезд на автобусе стоит a рублей, в метро b рублей, а вход в музей стоит c рублей.

Формат ввода

На вход подаются три натуральных числа, разделенных пробелом: a, b, и c. Все числа не превышают 10⁹.

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

Выведите единственное натуральное число — сумму, которую должен иметь Болик.

Пример

Ввод	Вывод
10 30 50	100

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

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

Числа Фибоначчи#25962

Числа Фибоначчи определяются рекуррентной формулой:

\(F_0 = F_1 = 1, \\ F_n = F_{n-1} + F_{n-2}, \text{ при}\ n \ge 2\)

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

В единственной строке входных данных записано натуральное число n (\(1<=n<=45\)).

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

Вывести одно n-е число Фибоначчи - F_n.

Примеры

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

Динамическое программирование Рекуррентные последовательности

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

Двоичный поиск#25959

Реализуйте алгоритм бинарного поиска.

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

В первой строке входных данных содержатся натуральные числа N и K (\(0<N,\ K <= 100000\)). Во второй строке задаются N элементов первого массива, отсортированного по возрастанию. В третьей строке – K элементов второго массива.
Элементы обоих массивов - целые числа, каждое из которых по модулю не превосходит \(10^9\).

Формат выходных данных
Требуется для каждого из K чисел вывести в отдельную строку "YES", если это число встречается в первом массиве, и "NO" в противном случае.

Алгоритмы поиска Бинарный поиск в массиве

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

Хакер Василий#25958

Хакер Василий получил доступ к классному журналу и хочет заменить все свои минимальные оценки на максимальные. Напишите программу, которая заменяет оценки Василия, но наоборот (все максимальные - на минимальные).

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

Дано количество оценок Василия (не больше 100), затем сами оценки.

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

Требуется вывести исправленные оценки в том же порядке.

Ввод	Вывод
5 1 3 3 3 4	1 3 3 3 1
8 5 4 2 2 4 2 2 5	2 4 2 2 4 2 2 2

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

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

Это Бомба#24906

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

Инструкция:

Посчитайте числовой код для числа на дисплее соответственно приведённым правилам и введите его. Применяется первое подошедшее правило:

1. Если число <= 2, то числовой код равен 1.

2. Если число заканчивается на 7, то нужно отнять от него 5. Посчитайте числовой код для нового числа и прибавьте 1.

3. Если число делится на 4 без остатка, его числовой код равен сумме кодов для числа,делённого на 4 и числа, делённого на 2.

4. Во всех остальных случаях к числу нужно прибавить 1. Посчитайте числовой код для нового числа и прибавьте 2.

Какой числовой код нужно ввести Мише?

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

В единственной строке содержится одно число от 1 до 10⁸, которое отображается на дисплее.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

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

Выведите в ответ одно число, которое Мише нужно срочно ввести.

Ввод	Вывод
1	1
10	12

Динамическое программирование: один параметр Рекурсия

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

Легкая, вариант -2#24902

В Берляндии каждый автомобиль имеет регистрационный номер. Автомобильные номера в Берляндии имеют следующий вид: LDDLDDL, где символ L обозначает строчную латинскую букву, а D цифру.

Филипп устроился работать в службу регистрации автомобильных номеров. По своей неопытности в первый же день работы Филипп разлил на стопку номеров кофе. У некоторых номеров оказался залит второй блок цифр (цифры на позициях 5 и 6).

Филипп считает, что все номера в Берляндии уникальны, поэтому он хочет быстро подобрать все залитые цифры, так чтобы среди всех номеров не было двух одинаковых. Задача показалась ему нерешаемой, и он попросил вас помочь ему.

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

В первой строке записано натуральное число n, не превосходящее 1000 — количество номеров в стопке.

В следующих n строках находятся n регистрационных номеров, в i+1-й строке i-й номер, в описанном выше формате. На месте залитых цифр находятся знаки вопросов.

Гарантируется, что знаки вопроса могут находиться только на месте цифр из второго блока цифр, причем либо на позициях обеих цифр, либо ни на одной из позиций.

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

Первая строка должна содержать NO, если в стопке были одинаковые номера. Иначе первая строка должна содержать YES, а далее n строк должны содержать номера из стопки — по одному в каждой строке, причем i+1-я строка должна содержать i-й номер. Номера должны удовлетворять принятому в Берляндии формату в том же порядке, что и во входном файле.

Если ответов несколько — разрешается вывести любой.

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

Пример входных и выходных данных

Ввод	Вывод
4 a10a10c a30b??c a30b??c x70r??r	YES a10a10c a30b10c a30b22c x70r37r
3 a00b10c a00b10c c02y03x	NO
2 a99a??b a99a??b	YES a99a11b a99a22b

Задача на реализацию Простые задачи на перебор

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

Тяжелая, вариант-2#24897

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

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, ранее которого не может быть начато выполнение этой задачи.

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

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел a_i (1 ≤ a_i ≤ n) — для каждой работы номер дня, ранее которого не может быть начато выполнение этой задачи. Числа отделены друг от друга одним пробелом.

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

Выведите одно число — количество различных допустимых расписаний выполнения задач.

Пример входных и выходных данных

Ввод	Вывод
5 2 4 4 2 1	4

Комбинаторика Теория расписаний

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

Легкая, вариант -2#24896

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

Сотрудник, имеющий порядковый номер один, является главой фирмы. У каждого из всех остальных сотрудников имеется один непосредственный начальник — сотрудник фирмы, имеющий меньший порядковый номер.

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

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

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит n-1 натуральное число — номера непосредственных начальников сотрудников с номерами от 2 до n в соответствующем порядке. Числа отделены друг от друга одним пробелом. Гарантируется, что номер непосредственного начальника очередного сотрудника меньше номера самого сотрудника.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

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

Пример входных и выходных данных

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	4

Деревья Поиск компонент связности

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

Динамика - 05#24855

Исполнитель Громозека выполяет некоторые действия с числом на экране. Громозека знает всего три команды, которым присвоены номера:
1. Прибавить 1
2. Прибавить 2
3. Прибавить 4
Сколько существует программ, для которых при исходном числе 5 результатом является число 19 и при этом траектория вычислений не содержит число 13?

ЕГЭ_информатика ЕГЭ-13. Динамическое программирование

1 000средняяВойти и решать

24801#24801

Составьте таблицу истинности логического выражения
¬A /\ (B /\ C)

В ответе укажите строку, образованную результирующим столбцом таблицы, при просмотре таблицы сверху вниз

Логика Таблицы истинности

1 000средняяВойти и решать

Рассадка зверей#24764

Сегодня Колобок созвал всех волков и лис к себе в гости на чаепитие. Чаепитие пройдет за круглым столом, за которым всего n мест. Колобок хочет рассадить зверей по-особенному — так, чтобы волки не сидели только с волками, а лисы только с лисами. Поэтому для каждого места он записал одно целое число — сколько лис должно сидеть на расстоянии не более d от этого места, включая это место.

Два места находятся на расстоянии не более d, если между ними встречаются не более d−1 места при движении по или против часовой стрелки от одного к другому. Таким образом, для заданного места всего существует 2d + 1 место, находящееся на расстоянии не более d от него.

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

Входные данные
В первой строке находятся два натуральных числа n, d (3 ≤ n ≤ 10⁵ , 3 ≤ 2d+1 ≤ n) — количество мест за круглым столом и расстояние d. В следующей строке находятся n неотрицательных целых чисел ai (0 ≤ a_i ≤ 2d+1) — количество лис на расстоянии не более d от этого места, включая это место. Информация о местах перечислена в порядке их следования по кругу.

Выходные данные
Если решения не существует, выведите «NO», иначе в первой строке выведите «YES», а в следу- ющей n чисел: 1 в том случае, если на этом месте сидит лиса, и 0, если на этом месте сидит волк. Если ответов несколько, разрешается вывести любой.

Ввод	Вывод
5 1 2 2 1 2 2	YES 1 0 1 0 1
9 2 3 4 4 3 3 2 2 2 2	YES 1 0 1 1 1 0 0 0 1
6 1 3 3 3 3 3 1	NO

Дерево отрезков, RSQ, RMQ НОД и алгоритм Евклида

1 300средняяВойти и решать

Постройка забора#24762

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

Забор представляет собой многоугольник ненулевой площади, сторонами которого являются доски. Пилить или ломать доски нельзя. Например, из трех досок с длинами 10, 11 и 12 можно построить забор, а из четырех досок с длинами 100, 1, 2 и 3 — нельзя.

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

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

Формат входного файла
В первой строке входного файла находится одно натуральное число n (1 ≤ n ≤ 4000) — количе- ство досок. Во второй строке дано n чисел li (1 ≤ l_i ≤ 4000) — длины досок.

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

Ввод	Вывод
3 10 11 12	1
4 100 1 2 3	0
4 5 5 5 5	5

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

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

Тяжелая, вариант-1#24759

Известно, что организации необходимо выполнить n задач, пронумерованных натуральными числами от одного до n. На выполнение каждой задачи требуется ровно один день, и в каждый день может быть выполнена только одна задача. Таким образом, на выполнение всех задач потребуется n дней, а расписание выполнения задач выглядит как назначение определенного дня на выполнение каждой задачи. Для каждой задачи известно также число a_i — номер дня, не позднее которого эта задача должна быть выполнена.

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

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

В первой строке находится натуральное число n (1 ≤ n ≤ 8) — количество задач, которые необходимо выполнить.

Следующая строка содержит n натуральных чисел a_i (1 ≤ a_i ≤ n) — для каждой работы номер дня, не позднее которого она должна быть выполнена. Числа отделены друг от друга одним пробелом.

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

Выведите одно число — количество различных допустимых расписаний выполнения задач.

Пример входных и выходных данных

Ввод	Вывод
5 2 4 4 2 5	4

Комбинаторика Теория расписаний

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

Легкая, вариант-1#24758

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

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

В первой строке находится натуральное число n (2 ≤ n ≤ 100) — количество сотрудников в фирме.

Следующая строка содержит одно натуральное число x (1 ≤ x ≤ n) — номер отправляемого в командировку сотрудника.

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

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

Пример входных и выходных данных

Ввод	Вывод
9 1 2 1 4 4 2 7 8 2	5

Деревья Поиск компонент связности

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

Легкая, вариант-1#24754

Вы занимаетесь разработкой системы по продаже билетов на поезда. Несмотря на то, что поезда ходят по множеству различных маршрутов, вы будете работать только с одним из них. Маршрут рассматриваемого поезда состоит из n остановок: маршрут начинается в первой из них, а заканчивается в n-й, соответственно. Всего в поезде имеется m мест для пассажиров.

Эта система будет использоваться для продажи билетов пассажирам. При покупке билета пассажир указывает номер станции L, на которой он хочет сесть на поезд и номер станции R, на которой он хочет сойти с поезда. Если у одного пассажира есть билет до станции S, а другой хочет купить билет от станции S, то они друг другу не мешают: второй может занимать только что освободившееся место первого. Система должна сообщить пассажиру следующую информацию:

«YES», если в поезде есть свободные места. В этом случае пассажир покупает один билет с L-й по R-ю станцию.
«NO», если подходящих свободных мест нет. В этом случае пассажир билет не покупает.

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

В первой строке находятся натуральные числа n (2 ≤ n ≤ 100), m (1 ≤ m ≤ 100) и k (1 ≤ k ≤ 100) — число станций в маршруте поезда, максимальное число пассажиров в поезде и число обращений обращений пассажиров к системе покупки билетов.

Следующие k строк содержат по два натуральных числа L_i и R_i (1 ≤ L_i < R_i ≤ n) — начальная и конечная станции в i-м обращении к системе.

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

Для каждого обращения к системе в своей строке выведите её ответ: YES или NO.

Пример входных и выходных данных

Ввод	Вывод
5 2 4 1 4 1 3 2 5 3 5	YES YES NO YES

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

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

Топологическая сортировка#24753

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

Входные данные: В первой строке содержатся два натуральных числа n и m (1≤n≤10⁵, 1≤m≤10⁵) — количество вершин и рёбер в графе соответственно. Далее в m строках перечислены рёбра графа. Каждое ребро задаётся парой чисел — номерами начальной и конечной вершин соответственно (нумерация вершин начинается с 1).

Выходные данные: Вывести любую топологическую сортировку графа в виде последовательности номеров вершин. Если граф невозможно топологически отсортировать, требуется вывести −1.

Примеры

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

Обход в глубину Топологическая сортировка

✓ 719✗ 1 848600лёгкаяВойти и решать

Тяжелая, вариант-2#24741

Мальчик Филя прочитал в одном научном журнале, что не так давно астрономы открыли новую планету, на которой как и на Земле существует жизнь. Ученые уже установили связь с ее жителями и успели выяснить, что эта планета обращается вокруг своей оси за другое время, поэтому сутки здесь длятся не 24 часа. На ней, так же как и на Земле, время измеряется часами, минутами и секундами. Но количество минут в часе, и секунд в минуте не совпадает с привычными земными.

А именно: в одном часе A минут, в одной минуте B секунд. Также, в одних сутках на этой планете X часов, Y минут Z секунд. То есть когда часы должны показать момент времени X:Y:Z, они показывают 0:0:0, и с этого момента начинается отсчет новых суток

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

Филя увлекается нумерологией, поэтому его интересует вопрос: сколько хороших моментов времени на часах этой планеты будет показано с момента времени H1:M1:S1 до момента времени H2:M2:S2 включительно. Филя называет момент времени хорошим, если в нем не содержится цифры c, то есть ни один из дисплеев не содержит (с учетом вышеописанных правил) цифру c.

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

В первой строке находятся два натуральных числа A, B (1 ≤ A, B ≤ 50) — количество минут в часе и секунд в минуте.
В следующей строке находятся три целых числа X, Y, Z (0 ≤ X ≤ 50, 0 ≤ Y < A, 0 ≤ Z < B) — количество часов, минут и секунд в сутках. Гарантируется, что X, Y, Z одновременно не равны нулю.
В следующей строке находятся три целых числа H1, M1, S1— стартовое время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
В следующей строке находятся три целых числа H2, M2, S2— конечное время время. Гарантируется, что это время, которое часы могут отобразить в течении суток.
Обратите внимание, что моменты времени могут находиться в разных сутках. Также обратите внимание, что моменты времени могут совпадать. В этом случае в интервале находится единственный момент времени.
В следующей строке находится цифра c (0 ≤ c < 10).

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

Требуется вывести одно число — количество хороших моментов времени с H1:M1:S1 до H2:M2:S2 включительно.

Пример входных и выходных данных

Ввод	Вывод
3 2 5 0 0 0 0 0 1 0 0 3	7
4 2 3 1 1 1 0 0 0 0 0 0	6
50 50 24 0 0 3 0 0 18 15 0 7	26956

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

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