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

Экзамен#27308

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

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

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

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

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

Примеры

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

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

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

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

СКОБКИ#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средняяВойти и решать

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

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

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

Примеры

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

Строки

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

Задача №4#24634

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

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

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

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

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

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

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

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

Примеры

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

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

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

Таймер#23405

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

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

В первой строке записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60.

Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 109, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, что то же самое, что 101:0 или 1:41:0.

А 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, что то же самое, что 101:41:40.

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

В ответе выведите в формате ЧЧ:ММ:СС время, когда прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол-во> days. Например, если сигнал прозвучит на следующий день - то +1 days.

Примеры

№	Входные данные	Выходные данные
1	01:01:01 48:0:0	01:01:01+2 days
2	01:01:01 58:119	02:01:00
3	23:59:59 1	00:00:00+1 days

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

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

Статистика#23404

Дан текст. Напишите программу, которая посчитает статистику - сколько раз встречается буква A, сколько - B и т.д. При этом большие и маленькие латинские буквы считать одинаковыми. В тексте могут быть сколь угодно длинные строки. Длина текста не превышает 100 Кб.

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

На вход подается текст, состоящий из английских букв (больших и маленьких), знаков препинания, цифр и т.д.

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

Выведите 26 строк. Каждая строка должна соответствовать латинской букве, буквы должны идти в алфавитном порядке.Каждая строка должна содержать сначала большую латинскую букву, которой она соответствует, пробел, символ - (тире), пробел и число: сколько раз буква встречается во входном файле.

Примеры

№	Входные данные	Выходные данные
1	Ab - a	A - 2 B - 1 C - 0 D - 0 <...здесь в выходном файле перечисляются все буквы...> Z - 0

Строки

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

Опять двойка (В, В')#23370

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

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

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

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

Выведите все целые положительные числа, не превосходящие n, в десятичной записи которых ровно две цифры 2. Числа следует выводить в порядке возрастания, по одному на строке.

Ввод	Вывод
179	22 122
1

Замечание

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

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

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

21941#21941

Если ячейке задается текстовый формат, то содержимое ячейки автоматически выравнивается

1. по центру
2. по ширине
3. по правому краю
4. по левому краю

Строки

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

21936#21936

Какой формат может содержать любую последовательность символов?

1. числовой
2. текстовый
3. денежный
4. процентный

Строки

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

Регистрация на олимпиаду#21818

Петя и Вася проводят олимпиаду по программированию. На нее пришло так много участников,

что для того, чтобы их всех зарегистрировать, Пете и Васе пришлось работать вдвоем.

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

а Петя и Вася заносят эту информацию в общую электронную таблицу. Так как участников много,

а времени на организацию так мало, Петя и Вася не успели договориться о формате записи данных

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

сначала его фамилию, затем имя, а затем — отчество, а Вася — сначала имя, затем отчество, а

затем — фамилию.

По окончании регистрации стало понятно, что для подведения итогов олимпиады использовать

данную таблицу невозможно: участнику будет неудобно себя искать. Было решено привести таблицу

к следующему виду:

• для всех участников сначала написана фамилия, затем имя, а затем — отчество;

• участники в таблице упорядочены лексикографически по фамилии.

Петя и Вася заметили, что фамилии у всех участников различны, а вот каждое имя встречается

хотя бы два раза. При этом никакое имя не является ни фамилией, ни отчеством никакого из

участников, аналогично никакие фамилия и отчество не совпадают.

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

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

В первой строке задано число n (2 ≤ n ≤ 1000) — общее число записей в электронной таблице.

Далее, в n строках записано по три слова s_1,i, s_2,i, s_3,i. Каждое из слов содержит от 1 до 20 латинских

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

одной из записей, сделанных Петей или Васей. Слова разделены одним пробелом.

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

Выведите n строк — электронную таблицу, в которой для каждого участника идет сначала

фамилия, потом имя, потом отчество, причем все записи отсортированы лексикографически.

Лексикографический порядок соответствует порядку в словарях: слова сначала сравниваются

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

алфавите, то это слово лексикографически меньше другого. Если же расхождение так и не найдено,

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

лексикографически меньше.

Пример
Ввод

Ivanov Ivan Ivanovich

Ivan Borisovich Petrov

Sergey Ivanovich Sidorov

Pavlov Sergey Borisovich

Вывод

Ivanov Ivan Ivanovich

Pavlov Sergey Borisovich

Petrov Ivan Borisovich

Sidorov Sergey Ivanovich

Использование сортировки Строки

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

1592#1592

Пользователь исправляет в текстовом редакторе текст. Когда курсор находился в начале второй строки текста, он нажал клавишу [BackSpace]. При этом все содержимое второй строки переместилось в конец первой строки. Это произошло потому что ...

1) произошел машинный сбой
2) пользователь стер невидимый символ "конец строки", который находился в конце первой строки
3) нажатие на клавишу [BackSpace] вызывает изменение автоматического форматирования текста
4) нажатие на клавишу [BackSpace] указывает текстовому редактору, что надо перейти к расположению текста в одну строку

Строки

800лёгкаяВойти и решать