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

Динамика - 04#23622

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

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

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

Счастливый номер#23595

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

Входные данные
На вход программы подается одно трехзначное число n \((100<=n<=999)\).

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

Примеры

№	Входные данные	Выходные данные
1	111	YES
2	112	NO

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

✓ 5 334✗ 6 444200лёгкаяВойти и решать

Свободное время#23594

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

Входные данные
Трехзначное число

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

Примеры

№	Входные данные	Выходные данные
1	111	NO
2	999	YES

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

✓ 5 147✗ 4 971200лёгкаяВойти и решать

Время года#23592

Вилли - сильный шахматист, но удача улыбается ему только в определенное время года. Получая приглашение сыграть в определенном турнире, Вилли хочет, чтобы сразу отображалось время года, в которое будет проходить турнир. Для этого он хочет написать программу. Сделайте это за него.
Напишите программу, которая получает с клавиатуры номер месяца и выводит название соответствующего ему времени года (winter, spring, summer, autumn) или сообщение об ошибке (error).

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

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

Примеры

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

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

✓ 4 727✗ 7 546200лёгкаяВойти и решать

Сжатие текста#23587

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

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

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

В первой строке входного файла задано целое число R - количество заменяемых последовательностей и целое число N - количество строк в исходном тексте (1<=N<=1000). Далее следуют R пар строк, описывающих возможные замены. Первая строка каждой пары содержит заменяемую последовательность, а вторая - заменяющий символ, являющийся большой или маленькой английской буквой. Различным заменяемым последовательностям соответствуют разные английские буквы (большие и маленькие буквы различаются). В следующих N строках записан текст, подлежащий сжатию. В этом тексте, также как и в заменяемых последовательностях, отсутствуют буквы английского алфавита.

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

В выходной файл вывести заархивированный текст.

Примечания

Символы перевода строки не заменяются (т.е. замены возможны только внутри строк). Длина каждой строки входного файла не превосходит 255 символов.

Пример входного файла

8 10

рхиватор

замен

ены

зам

быт

про

сжат

ом называется

Архиватором называется программа, предназначенная для сжатия данных за счет удаления

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

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

символов не встречаются, поэтому они могут быть использованы для замены часто

повторяющихся последовательностей символов.

Заданы последовательности, которые могут быть заменены некоторыми символами английского

алфавита, а также исходный текст, который следует сжать. Поскольку в исходном тексте эти

последовательности могут накладываться друг на друга, результат сжатия существенно зависит

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

Пример выходного файла

Аbg dграмма, предназначенная для fия данных за счет удаления

изhочной информации. В этой задаче вашей целью является разработка dстейшего

аbа текстов на русском языке. В таких текстах многие знаки стандартной таблицы

символов не встречаются, поэтому они могут hь использованы для Dы часто

повторяющихся последовательностей символов.

Заданы последовательности, которые могут hь DF некоторыми символами английского

алфавита, а также исходный текст, который следует fь. Поскольку в исходном тексте эти

последовательности могут накладываться друг на друга, результат fия существенно зависит

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

Задача на реализацию Разбор случаев

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

Assault#23586

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

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

Но Джерард не только согласился отвести свой флот из бухты Амбера, благодаря чему флоту Корвина удалось добраться до Амбера с целым и невредимым флотом, но и предоставил ему журнал с m записями, в котором в i-ой записи указано, что были перестроены сегменты с l_i по r_i, а также сказано, насколько изменилась укрепленность всех сегментов (укрепленность каждого сегмента на отрезке [li; ri] изменяется на одно и тоже значение t_i).

Корвин m раз предлагает выстрелить по сегментам стены с l по r из p кораблей. Известно, что брешь будет пробита, если на отрезке [l; r] есть хотя бы один сегмент с укрепленностью меньше p. Вы должны ответить ему, будет ли пробита брешь (вывести "YES"), или нет (вывести "NO").

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

На первой строке находятся числа n, m и k (1 <= n, k <= 100000, 1 <= m <= 10000) - количество сегментов, записей и запросов от Корвина соответственно.

На второй строке находятся числа a₁,..., a_n (0 <= a_i <= 10).

В следующих m строках содержатся числа l, r, t (1 <= l <= r <= n, -10 <= t <= 10).

В следующих k строках содержатся числа l, r, p (1 <= l <= r <= n, 1 <= p <= 1000).

Выходные данные
В i-ой строке выведите ответ на i-ый запрос Корвина.

Примеры

№	Входные данные	Выходные данные
1	10 3 3 123 398 287 190 76 15 407 312 323 659 4 9 -99 10 10 -82 4 10 76 9 10 32 5 6 283 4 4 983	NO YES YES

Дерево отрезков, RSQ, RMQ Префиксные суммы(минимумы, ...)

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

Двоичное дерево поиска 1#23571

Реализуйте сбалансированное двоичное дерево поиска.
ВНИМАНИЕ! Пользоваться vector и set из STL СТРОГО ЗАПРЕЩЕНО, однако рекомендуется стрессить ваше решение с ними для поиска багов.

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

В первой строке дано число n - количество операций с деревом. 1 <= n <= 100000.

Далее дается n строк – операции с деревом. В каждой строке находится одна из следующих операций:

1) insert x – добавить в дерево ключ x. Если ключ x уже в дереве, то ничего делать не нужно.

2) delete x – удалить из дерева ключ x. Если ключа x в дереве нет, то ничего делать не нужно.

3) exists x – если ключ х есть в дереве, то выведите “true”, иначе “false”.

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

Выведите последовательно результат выполнения всех операций exists. Каждый ответ нужно выводить в отдельной строке.

Пример:

Ввод	Вывод
6 insert 2 insert 5 insert 3 exists 3 exists 4 delete 5	true false

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

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

Вывод переменной - 5#23465

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

Пример

№	Входные данные	Выходные данные
1	2007	The next number for the number 2007 is 2008. The previous number for the number 2007 is 2006.

Ввод, вывод данных Линейные алгоритмы

✓ 545✗ 2 853400лёгкаяВойти и решать

Анализ цифр числа - 9#23453

В первой строке вводится целое чило n >=0
Вывести на экран количество нечетных цифр в нем

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

№ теста	Входные данные	Выходные данные
1	45545	3
2	44	0

Цикл for Цикл while

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

Сумма цифр числа#23452

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

The sum of the digits of number 123 is 6

Строки Цикл for

✓ 9 017✗ 34 593200лёгкаяВойти и решать

Декодирование сообщения#23418

По каналу связи передаётся последовательность слов в латинском алфавите {А, Е, Р}. Длина каждого слова не превосходит 10 букв, слова могут не быть осмысленными словами русского языка. Каждое слово передается в виде целого числа, полученного следующим образом:
1)      Сначала слово кодируется с помощью неравномерного двоичного кода с кодовыми словами: Е – 0; Р – 10; А – 11;
2)      К полученной двоичной последовательности справа приписывается цифра 1;
3)      Полученная двоичная цепочка переворачивается, то есть, из цепочки 01010111 получается 11101010;
4)      Искомое число N вычисляется в результате перевода двоичной цепочки, полученной на предыдущем шаге, в десятичную систему.

Например, символьная последовательность ААЕЕР будет преобразована в 11110010, затем (добавляем единицу в конец) в 111100101, а потом в число: 1 + 2 + 4 + 8 + 64 + 256 = 335. Отметим, что 335 = 1010011112.
Напишите программу, которая, получив на вход натуральное число, декодирует переданное сообщение и определяет, сколько раз в исходном слове встречаются гласные буквы. Считается, что входное число может быть представлено в виде значения целого типа в используемом языке программирования.

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

Пример выходных данных
АЕРАЕРР
4

Примечание. В этом примере: исходное слово: АЕРАЕРР. Кодовая двоичная последовательность: 110101101010, после добавления 1 справа получим: 1101011010101.

ЕГЭ_информатика ЕГЭ-04. Кодирование и декодирование информации

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

Уравнение с пропущенными цифрами#23416

Задано уравнение вида A+B=C, где A, B и C - неотрицательные целые числа, в десятичной записи которых некоторые цифры заменены знаками вопроса (?). Примером такого уравнения является ?2+34=4?. Требуется так подставить вместо знаков вопроса цифры, чтобы это равенство стало верным, либо определить, что это невозможно. Найти только одно из возможных решений.

Входные данные
Вводится строка, представляющая собой заданное уравнение без пробелов. Длина уравнения не превышает 80 символов.

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

Примеры

№	Входные данные	Выходные данные
1	`??2?4+9?=355`	`00264+91=355`

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

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

Шаблон и слово#23413

Требуется определить подходит ли заданное слово под заданный шаблон. Шаблон задается большими латинскими буквами, знаками "?" - любой символ, "*" - любая последовательность символов (даже пустая).

Входные данные
В первых двух строках записаны шаблон и слово: в одной из них записан шаблон - последовательность больших латинских букв, "?" и "*", в другой - слово, состоящее только из больших латинских букв (строки короче 100 символов).

Выходные данные
Вывести YES, если слово подходит, NO, если не подходит.

Примеры

№	Входные данные	Выходные данные
1	ABBCDA A*CDA	YES
2	AADAAVA ADAAA*	NO

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

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

Восстановление скобок#23412

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

Входные данные
Вводится строка, которая содержит заданный шаблон длиной не более 80 символов.

Выходные данные
Выведите искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2·10⁹.

Примеры

№	Входные данные	Выходные данные
1	`????(?`	`2`

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

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

*Удаление пробелов#23384

На вход подается одна строка текста (не больше 255 символов).

Нужно вывести эту же строку, удалив все парные пробелы (то есть, если где-то в строке идет подряд 2 или более пробелов, то в этом месте нужно оставить только один из них).

Примеры

№	Входные данные	Выходные данные
1	My name is Vasya...	My name is Vasya...

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

✓ 3 840✗ 8 690500лёгкаяВойти и решать

Перестановка слов#23383

На вход подается одна строка, в которой записаны фамилия и имя человека (разделенные ровно одним пробелом).

Выведите эту же информацию, однако сначала имя, а потом фамилию.

Пример

№	Входные данные	Выходные данные
1	Pupkin Vasya	Vasya Pupkin

Ввод, вывод данных Строки

✓ 7 286✗ 7 414100лёгкаяВойти и решать

День рождения#23382

На день рождения пришли N человек. В некоторый момент именинник решил, что пора устроить какую-нибудь игру. Он выяснил, что i-й человек согласен вступить в игру, если в ней уже принимают участие не менее A[i] и не более B[i] человек. Единожды вступив в игру, никто из нее

не выходит.

Требуется выяснить, может ли именинник установить такую

последовательность вступления в игру, что в итоге все

присутствующие станут ее участниками. (Сам именинник в игре участия

не принимает.)

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

Сначала вводится количество гостей N (1<=N<=100). Затем вводится

N пар чисел A[i] и B[i] (все эти числа из диапазона от 0 до N-1).

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

Если можно установить последовательность вступления гостей в игру,

чтобы в итоге все стали ее участниками, то нужно вывести номера гостей

в том порядке, в каком они могут вступать в игру. Если всех вовлечь

в игру не удастся, выведите одно число - 0.

Пример 1

Пример входного файла

4 4

0 3

1 4

1 3

2 2

Пример выходного файла

2 3 5 4 1

Пример 2

Пример входного файла

1 1

Пример выходного файла

Пример 3

Пример входного файла

0 0

Пример выходного файла

Жадный алгоритм Разбор случаев

—Войти и решать

Список#23381

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

Например, вместо

1,3,4,5,6,7,8,10,12,16,17,20,21,22,23,24

записывается

1,3-8,10,12,16-17,20-24

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

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

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

Выходные данные
Выведите в одной строке список номеров бракованных изделий в сокращенном виде. Интервалы должны разделяться запятой. В строке не должно быть пробелов.

Ограничения

1<=M<=N<=1000000.

Примеры

№	Входные данные	Выходные данные
1	10 5 1 3 5 7 9	1,3,5,7,9
2	40 16 1 3 4 5 6 7 8 10 12 16 17 20 21 22 23 24	1,3-8,10,12,16-17,20-24
3	11 11 1 2 3 4 5 6 7 8 9 10 11	1-11
4	10000 1 5	5

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

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

Два массива#23379

Даны два массива чисел. Требуется вывести те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве.

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

В первой строке ввода записано число N - количество элементов в первом массиве. Во второй строке - N чисел (элементы массива). В третьей строке записано число M - количество элементов во втором массиве. В четвертой строке - элементы второго массива.

Количество элементов каждого массива не превышает 100. Сами элементы по модулю не превышают 1000. Все числа целые.

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

Выведите те элементы первого массива, которых нет во втором.Элементы необходимо вывести в том порядке, в каком они идут в первом массиве.

Примеры

№	Входные данные	Выходные данные
1	7 3 1 3 4 2 4 12 6 4 15 43 1 15 1	3 3 2 12

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

✓ 4 036✗ 5 283300лёгкаяВойти и решать

Британские ученые (В, А', А)#23376

Согласно исследованиям британских ученых, люди способны воспринимать слова в тексте, если в каждом слове оставить на месте первую и последнюю буквы, а остальные перемешать произвольным образом; например, слово "программа" может быть прочитано даже если оно записано как

"пгрроммаа" или "пморгамра".

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

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

В первой строке записано одно целое число n (1 <= n <= 10⁵) - количество слов в словаре.

В следующих n строках записаны слова из словаря, по одному на строку. Гарантируется, что все слова в словаре различны.

В следующей строке записано одно целое число m (1 <= m <= 10⁵) - количество слов в тексте.

В следующих m строках записаны слова из текста, по одному на строку.

Каждое слово состоит только из строчных букв латинского алфавита; ни в какой строке ввода нет пробелов и других разделителей. Суммарная длина всех слов не превосходит 10⁵.

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

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

котором слова перечислены во вводе; следует выводить по одному ответу на строку.

Ввод	Вывод
4 bird sun lksh summer 4 brid snu sommer sis	YES NO NO NO

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

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