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

Тильда-омега-лямбда-исчисление#27311

Тильда-омега-лямбда-исчисление - ещё более инновационная разработка "British Scientists, Inc" в сфере функционального программирования. Его отличие от омега-лямбда-исчисления только в возможности ставить квадратные и фигурные скобки. Планировались также скобки в форме слоников, но стандарт ЮНИКОД у компании изменить не получилось.

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

Напомним, иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм gg, если нет - в терм wp.

Примеры

№	Входные данные	Выходные данные
1	main{izzy[lol](ttt)}	gg

Конечные автоматы Строки

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

Омега-лямбда-исчисление#27310

Омега-лямбда-исчисление - инновационная разработка "British Scientists, Inc" в сфере формальной логики. Любое выражение омега-лямбда-исчисления состоит из круглых скобок и термов (термом может быть любая последовательность из букв латинского алфавита).

Иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм gg, если нет - в терм wp.

На вход подаётся омега-лямбда-выражение длиной не более 10⁷ символов. Нужно вывести результат его иззи-редукции.

Примеры

№	Входные данные	Выходные данные
1	a(b(xx)f(g(x))m(y))	gg

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

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

Экзамен#27308

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

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

В первой строке подаётся N (\(1 <= N <= 6\)) - количество сообщений Чарльза в подозрительный день. В следующих N строках находятся скобочные последовательности суммарной длины не больше \(10^6\). Обратите внимание, что способ составить из них ПСП может всё-таки существовать - Вы могли его просто не заметить.

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

Выведите "True", если Чарльз не соврал, и есть способ собрать правильную скобочную последовательность, добавив ещё одно сообщение. Выведите "Liar", если это не так.

Примеры

№	Входные данные	Выходные данные
1	2 ((()()) ))))))	True

Разбор случаев Строки

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

Censoring#27298

Фермер Джон купил подписку журнала Good Hooveskeeping для своих коров. К сожалению, последний номер содержит неподходящую статью - как приготовить бифштекс. ФД не хочет, чтобы его коровы её читали.

ФД взял текст журнала, создал строку S длиной не более чем 10^5 символов. У него есть список слов t_1, t_2, ..., t_N, которые он хочет удалить из S. Поэтому ФД находит ближайшее вхождение слова из списка T (то есь с наименьшим индексом) и удаляет его из S. Затем он продолжает это процесс опять, пока в S не останется слов из T. Заметим, что удаление слова может создавать новое вхождение свлоа из T, которое не существовало ранее.

ФД заметил, что слова из списка T обладают таким свойством, что никакое из них не является подстрокой другого слова из T. В частности, это означает, что ранее вхождение слова из T в S всегда определено однозначно. Пожалуйста, помогите ФД определить финальное содержание строки S.

INPUT FORMAT:

Первая строка содержит S. Вторая строка содержит N - количество удаляемых слов. Последующие N строк содержат строки t_1, t_2, ..., t_N. Каждая строка содержит только маленькие латинские буквы (a..z) и суммарная длина всех строк не превысит 10^5.

OUTPUT FORMAT:

Строка S после всех удалений. Гарантируется, что S не станет пустой.

Ввод	Вывод
begintheescapexecutionatthebreakofdawn 2 escape execution	beginthatthebreakofdawn

Строки Структуры данных Хеш

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

Palindromic Paths#27294

Ферма Джона представлена решёткой N×N полей (1≤N≤500). Каждое поле представлено символом латинского алфавита. Например:

ABCD

BXZX

CDXB

WCBA

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

Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N, и последующие N строк содержат N строк решётки, описывающей поля. Каждая строка содержит N символов в интервале A..Z.

ФОРМАТ ВЫВОДА:

Выведите количество различных путей Беси, формирующих палиндромы по модулю 1,000,000,007.

Ввод	Вывод
4 ABCD BXZX CDXB WCBA	12

Примечание:

Беси может сделать следующие палиндромы:

1 x "ABCDCBA"

1 x "ABCWCBA"

6 x "ABXZXBA"

4 x "ABXDXBA"

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

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

Bovine Genomics#27218

У Фермера Джона NN коров с пятнами и NN коров без пятен. Пройдя курс генетики, ФД убеждён, что пятна у коров вызваны мутацией генов.

За большие деньги ФД зафиксировал геномы своих коров. Каждый геном это строка длиной MM, состоящая из символов A, C, G, T. Когда он выписал все геномы у него получилась такая таблица, N=3 и M=8:

Позиция : 1 2 3 4 5 6 7 8

Пятнистая корова 1: A A T C C C A T

Пятнистая корова 2: A C T T G C A A

Пятнистая корова 3: G G T C G C A A

Корова без пятен 1: A C T C C C A G

Корова без пятен 2: A C T C G C A T

Корова без пятен 3: A C T T C C A T

Посмотрев внимательно на эту таблицу, он заметил, что последовательность от позиции 2 до позиции 5 успешна, чтобы объяснять пятнистость. То есть, рассматривая символы в этих позициях (2…5), ФД может предсказать какие из его коров пятнистые, а какие нет. Например, если он видит символы GTCG в этих позициях, он знает, что корова будет пятнистая.

Помогите ФД определить длину кратчайшей последовательности позиций, которая может объяснить пятнистость.

ФОРМАТ ВВОДА:

Первая строка ввода содержит N (1≤N≤500) и M (3≤M≤500). Каждая из N следующих строк содержит по M символов. Эти символы описывают геномы пятнистых коров. Следующие N строк описывают геномы коров без пятен. Никакая пятнистая корова на имеет точно такой же геном, как корова без пятен.

ФОРМАТ ВЫВОДА:

Пожалуйста, выведите длину кратчайшей последовательности позиций, достаточной для объяснения пятнистости. Последовательность позиций объясняет пятнистость, если по ней можно предсказывать абсолютно точно пятнистая или нет любая из коров ФД.

Ввод	Вывод
3 8 AATCCCAT ACTTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT	4

Множества Строки Хеш

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

Consonant Fencity#27117

There are two kinds of sounds in spoken languages: vowels and consonants. Vowel is a sound, produced with an open vocal tract; and consonant is pronounced in such a way that the breath is at least partly obstructed. For example, letters a and o are used to express vowel sounds, while letters b and p are the consonants (e.g. bad, pot).

Some letters can be used to express both vowel and consonant sounds: for example, y may be used as a vowel (e.g. silly) or as a consonant (e.g. yellow). The letter w, usually used as a consonant (e.g. wet) could produce a vowel after another vowel (e.g. growth) in English, and in some languages (e.g. Welsh) it could be even the only vowel in a word.
In this task, we consider y and w as vowels, so there are seven vowels in English alphabet: a, e, i, o, u, w and y, all other letters are consonants.

Let’s define the consonant fencity of a string as the number of pairs of consecutive letters in the string which both are consonants and have different cases (lowercase letter followed by uppercase or vice versa). For example, the consonant fencity of a string CoNsoNaNts is 2, the consonant fencity of a string dEsTrUcTiOn is 3 and the consonant fencity of string StRenGtH is 5.

You will be given a string consisting of lowercase English letters. Your task is to change the case of some letters in such a way that all equal letters will be of the same case (that means, no letter can occur in resulting string as both lowercase and uppercase), and the consonant fencity of resulting string is maximal.

Input
The only line of the input contains non-empty original string consisting of no more than 10⁶ lowercase English letters.

Output
Output the only line: the input string changed to have maximum consonant fencity.

Input	Output
consonants	CoNsoNaNts
destruction	dEsTrUcTiOn
strength	StRenGtH

Конструктив Строки

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

СКОБКИ#27114

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

Приоритет	Операции
1 (наибольший)	*, /
2	+, -
3	&
4	^
5 (наименьший)	\|

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

Ввод	Вывод	Замечания
a+(b*c)	a+b*c	(у ‘*’ приоритет выше, чем у ‘+’, поэтому она и так выполняется первой,- скобки лишние);
((a+b)+(c+d))	a+b+(c+d)	(Скобки вокруг всего выражения допустимы, но никогда не влияют на порядок вычисления внутри. Поскольку ассоциативность всех операций слева направо, первые внутренние скобки лишние, а вторые – нет, без них выражение было бы эквивалентно (((a+b)+c)+d));
((a)+b)&c^d	a+b&c^d	(скобки вокруг переменной всегда лишние).
(((a)&b^c\|((d))))	a&b^c\|d
a	a

Формат входного файла:
Одна строка, содержащая исходное математическое выражение не длиннее 100 символов.
Формат выходного файла:
Одна строка с математическим выражением без лишних скобок.

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

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

Алгоритмизация и программирование#27032

Дана исходная последовательность цифр: 1234
Задан алгоритм преобразования последовательности, на каждом шаге которого выполняются следующие операции:
1. В конец последовательности, имеющейся перед выполнением шага, дописывается ее копия, но развернутая зеркально (цифры записываются в обратном порядке).
2. В конце получившейся последовательности удаляется количество цифр, равное номеру шага выполнения алгоритма.

Ниже приведены результаты выполнения первых двух шагов алгоритма:
1: 1234432
2: 123443223443

Определите, какие цифры будут на A-ой, B-ой и C-той позиции от начала последовательности, которая получилась после выполнения 8-ого шага алгоритма. В ответе укажите через пробел три цифры: сначала цифру, которая стоит на А-ой позиции, затем цифру, которая стоит на В-ой позиции и затем цифру, которая стоит на С-той позиции. A, B и C задаются с клавиатуры.

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

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

Пароль#26999

Антон вводит пароль. Артур подглядывает за Антоном и записывает последовательность клавиш, которые тот нажимает. Иногда Артур не разбирает клавишу и пишет вместо неё символ «*». Артур знает, что пароль Антона является сочетанием (без пробелов) его часто произносимых слов.

Каждое слово может присутствовать в пароле любое количество раз, в том числе 0. Артур решил восстановить пароль Антона. Какое минимальное количество вариантов ему потребуется перебрать?

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

В первой строке находятся два числа N и K (1 <= N <=1000,1 <=K <= 10). Во второй строке находится строка из N символов - последовательность, которую записал Артур. Последовательность может содержать строчные буквы латинского алфавита и знак «*».

Далее идут K строк, которые обозначают часто произносимые слова Антона. Каждое слово состоит не более чем из 10 строчных латинских букв. Других символов в словах нет.

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

Если количество вариантов не более 10⁹, выведите это количество. Иначе выведите единственную строку «MNOGO».

Ввод	Вывод
12 3 r*mm** mama mila ramu	4
10 8 ********** a b c d e f g h	MNOGO

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

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

На связи#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средняяВойти и решать

Арифметическое выражение-3#24676

Напишите программу, которая вычисляет выражение, состоящее из трех чисел, трех знаков арифметических операций (допускаются знаки «+», «–», «*» и «/») и круглых скобок. На вход подается символьная строка, представляющая собой арифметическое выражение. Все числа - целые. Операция «/» выполняется как целочисленное деление.

Примеры

№	Входные данные	Выходные данные
1	2*(3+45)+4	100
2	2*3/(5-2)	2

Строки

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

Арифметическое выражение-1#24675

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

Примеры

№	Входные данные	Выходные данные
1	12+3+45	60
2	12-45+3	-30

Строки

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

Разбор URL на части#24660

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

Входные данные
В первой строке задается URL адрес. В начале и в конце строки лишних пробелов нет.

Выходные данные
Необходимо вывести каждую часть URL адреса с новой строки.

Примеры

№	Входные данные	Выходные данные
1	C:/Photo/2013/Pokhod/vasya.jpg	C: Photo 2013 Pokhod vasya.jpg
2	http://chelyabinsk.74.ru/text/newsline/258041618673664.html	http: chelyabinsk.74.ru text newsline 258041618673664.html

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

✓ 4 140✗ 4 045400лёгкаяВойти и решать

И.О. Фамилия#24659

Ввести имя, отчество и фамилию. Преобразовать их к формату «инициалы-фамилия».

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

Выходные данные: необходимо вывести модифицированную строку.

Примеры

№	Входные данные	Выходные данные
1	Inav Ivanovich Ivanov	I. I. Ivanov

Строки

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

Сколько слов в предложении#24658

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

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

Выходные данные: необходимо вывести одно число - количество слов в предложении.

Примеры

№	Входные данные	Выходные данные
1	Vasja poshel guljat	3

Строки

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

Самое длинное слово#24657

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

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

Выходные данные: необходимо вывести самое длинное слово и количество символов в нем. Если таких слов несколько, то вывести первое из них.

Примеры

№	Входные данные	Выходные данные
1	Vasja poshel guljat	poshel 6

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

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

Фамилия И.О.#24656

Ввести имя, отчество и фамилию. Преобразовать их к формату «фамилия-инициалы».

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

Выходные данные
Необходимо вывести модифицированную строку.

Примеры

№	Входные данные	Выходные данные
1	Sergey Petrovich Ivanov	Ivanov S.P.

Строки

✓ 7 434✗ 8 018200лёгкаяВойти и решать

Замена букв#24655

Ввести с клавиатуры символьную строку и заменить в ней все буквы «a» на «b» и все буквы «b» на «a» (заглавные на заглавные, строчные на строчные).

Входные данные
В первой строке задается строка без пробелов.

Выходные данные
Необходимо вывести модифицированную строку.

Примеры

№	Входные данные	Выходные данные
1	aabbAABBccCC	bbaaBBAAccCC

Обработка текста Строки

✓ 8 041✗ 14 042300лёгкаяВойти и решать

Задача №4#24634

Входные данные	Выходные данные
What is your name?	My name is Naruto Uzumaki!
What is your name???	My name is Naruto Uzumaki!!!

(с) Егор Курбатов, 10и

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

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