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

Ферма Джона представлена решёткой из N×N полей(2≤N≤18), каждое из которых помечено буквой алфавита. Например,

ABCD

BXZX

CDXB

WCBA

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

Пожалуйста, помогите Беси определить количество различных палиндромов, которые она сможет сформировать во время своего путешествия. Различные способы формировать один и тот же палиндром следует учитывать только один раз. Например, в примере выше имеется несколько способов сформировать палиндром ABXZXBA, однако существует всего 4 различных палиндрома, которые Беси может сформировать ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.

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

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

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

Выведите количество различных палиндромов, которые Беси может сформировать.

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

meet in the middle Перебор

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

Экзамен#27308

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

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

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

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

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

Примеры

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

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

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

Кубическое уравнение#27291

Даны четыре действительных числа: A, B, C, D. Найдите все корни уравнения Ax³+Bx²+Cx+D=0. Известно, что все корни этого уравнения не превосходят по абсолютной величине 1000. Известно, что любые два корня этого уравнения различаются не менее, чем на 10^-6.

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

Программа получает на вход четыре действительных числа: A, B, C, D. Любые из этих четырех чисел, но не все одновременно, могут быть равны 0.

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

Программа должна вывести от 0 до 3 действительных чисел: корни данного уравнения в порядке возрастания. Кратные корни должны быть выведены только один раз. Значения корней необходимо выводить с точностью до 6 знаков после точки.

Ввод	Вывод
0 0 1000 -1	0.001

Бинарный поиск значения функции Бинарный поиск по ответу

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

The Lost Cow#27223

Фермер Джон потерял свою корову Беси и хочет её найти.

К счастью через ферму ведёт только одна длинная дорога и и ФД знает, что Беси находится в некоторой точке на этой дороге. Если мы рассмотрим эту дорогу как числовую прямую, ФД сейчас находится в точке x, а Беси сейчас находится в точке y (неизвестной ФД). Если бы ФД знал, где Беси, то бы мог идти прямо к ней, пройдя расстояние |x−y|. К несчастью, сейчас темно, и ФД ничего не видит. Единственный способ, которым он может найти Беси - ходить вперёд и назад, пока не наткнётся на Беси.

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

Рекомендуемая стратегия такова: двинуться в позицию x+1, затем изменить направление движения на противоположное и перейти в позицию x−2, затем в позицию x+4 и т.д., двигаясь "большим зигзагом", каждый раз двигаясь в два раза дальше от своей первоначальной позиции, чем в прошлый раз. Такой подход гарантирует, что он пройдёт в худшем случае 9 раз прямое расстояние от себя до Беси |x−y|. И это - наименьшее число, гарантируемое в худшем случае.

ФД хочет проверить это утверждение. Вам даны x и y, вычислите общее расстояние пройденное в поиске по описанному выше алгоритму "большой зиг-заг", пройденное до момента находки Беси.

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

Единственная строка ввода содержит два различных разделённых одним пробелом целых числа x и y. Оба числа в интервале 0…1,000.

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

Выведите одну строку, содержащую расстояние пройденное ФД до достижения Беси.

Ввод	Вывод
3 6	9

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

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

Bovine Genomics №2#27221

У Фермера Джона есть N коров с пятнами и N коров без пятен. Как генетик, ФД уверен, что пятна на его коровах вызваны мутацией коровьего генома.

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

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

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

Пятнистая корова 2: G A 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 G T T G C A ... T

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

Посмотрев внимательно на эту таблицу он предположил, что позиции 2 и 4 могут отвечать за пятнистость. Поскольку, глядя на символы в этих позициях, ФД может предсказать, какая из его коров пятнистая, а какая - нет (например, если он видит G и С - значит, корова не пятнистая).

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

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

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

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

Вычислите количество множеств из трёх различных позиций, которые могут объяснять пятнистость. Множество из трёх различных позиций может объяснять пятнистость, если пятнистость может быть предсказана абсолютно точно для популяции коров ФД, при анализе этих трёх позиций генома.

Ввод	Вывод
3 8 AATCCCAT GATTGCAA GGTCGCAA ACTCCCAG ACTCGCAT ACTTCCAT	22

Вывод формулы Перебор

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

Paired Up#27220

Фермер Джон обнаружил, что корову легче доить, если рядом есть другая корова для моральной поддержки. Поэтому он хочет разбить M своих коров (M <= 10⁹, M - чётное) на M/2 пар. Каждую из этих пар он помещает в отдельное стойло, и все пары коров доятся одновременно.

Каждая из коров даёт различное количество молока. Если коровы в паре дают по A и B литров молока, то для дойки этой пары требуется A+B единиц времени.

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

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

Первая строка ввода содержит N (1 <= N <= 100000). Каждая из следующих N строк содержит два целых числа x и y, указывающих, что у ФД есть x коров с производством молока по y (1 <= y <= 10⁹) литров. Сумма всех x-ов есть M- общее количество коров.

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

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

Примеры

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

"Два указателя"Жадный алгоритм

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

Перестановки#27214

Сколько существует трехразрядных шестнадцатеричных чисел, для которых будут одновременно выполняться следующие три условия:

1. Шестнадцатеричные цифры в записи числа упорядочены по невозрастанию.

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

3. Любое шестнадцатеричное число, образованное перестановкой цифр этого числа и переведенное в двоичную систему счисления, также будет содержать в двоичной записи не менее 5-ти единиц подряд.

Перебор Системы счисления

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

Транспортировка#27126

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

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала школы. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. Нато, чтобы довезти кружки от завода-изготовителя до ЛКШ,остаётся всего 24 часа.

Заказ на 10000000 экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

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

В первой строке находятся числа n (1≤n≤500) и m - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих m строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до n. При этом завод по производству кружек имеет номер 1, а ЛКШ - номер n. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик - 3 тонны.

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

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

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

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

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

Все возрастающие последовательности длины k из чисел 1..n#27093

По данным числам N и K выведите все возрастающие последовательности длины K из чисел 1..N в лексикографическом порядке.

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

Заданы 2 числа: N и K (1 ≤ K,N ≤ 100). Для всех тестов верно, что число требуемых последовательностей не превышает 5000.

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

Необходимо вывести все возрастающие последовательности длины K из чисел 1..N в лексикографическом порядке. Последовательности выводятся по одной в строке, числа внутри последовательностей разделяются пробелами.

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

Рекурсивный перебор Сочетания

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

Построить из строки следующую анаграмму#27091

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

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

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

Примеры

№	Входные данные	Выходные данные
1	4 aab aba baa aaa	aba baa aab aaa

Комбинаторика Перестановки

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

Кузнечик и лягушки#27082

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

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

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

Входная строка содержит натуральные числа N и K , разделённые пробелом. Гарантируется, что 1 <= N, K <= 32 . Во второй строке записано число лягушек L ( 0 <= L <= N - 2 ). В третьей строка записано L натуральных чисел: номера столбиков, на которых сидят лягушки (среди них нет столбиков с номерами 1 и N ).

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

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

Примеры

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

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

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

Огромное число#27070

Вася получил длинную последовательность из цифр следующим образом. Он брал подряд натуральные числа, начиная с 1, переводил их в четверичную систему счисления и записывал результаты перевода друг за другом. Вот начало этой последовательности:
123101112132021222330313233100…
Вася остановился только тогда, когда дописал в конец последовательности четверичную запись числа 1023₁₀. Затем он представил, что это одно большое число, записанное в четверичной системе счисления, и перевел его в шестнадцатеричную систему счисления.

Определите, какая шестнадцатеричная цифра стоит в этом числе на a-ой позиции, считая слева направо от начала числа. В ответе укажите эту шестнадцатеричную цифру.

Задача на реализацию Системы счисления

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

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

Гриша пишет дипломную работу на тему автостоянок в Берляндии. В ходе дипломной работы ему потребовалось решать следующую задачу.

Машины в Берляндии представляют собой отрезки длинной l. Автостоянка представляет отрезок на прямой [0;M]. В точке 0 и точке M находятся стены. В некоторых точках Xi этого отрезка могут стоять машины, то есть левая граница отрезка, образующего машину, находится в точке Xi. Уже стоящие на стоянке машины не пересекаются, но могут стоят вплотную друг к другу или к стене.

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

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

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

В первой строке записаны четыре целых неотрицательных числа n, M, l и b (0 ≤ n ≤ 100, 1 ≤ M ≤ 100000, 1 ≤ l ≤ 100000, 0 ≤ b ≤ 100000) — количество автомобилей на стоянке, длина стоянки, длина автомобиля в Берляндии и необходимое расстояние от границ приехавшего автомобиля до ближайшего препятствия.

В следующей строке находятся n неотрицательных чисел Xi (Xi < M) — точки, в которых располагаются левые границы машин.

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

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

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

Если не существует машины, которую можно было бы поставить, удовлетворяя все условия, выведите 0.

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

Ввод	Вывод	Примечание
4 21 1 1 7 12 3 16	1
4 30 3 1 24 5 11 18	1
2 20 3 1 7 10	0	В данном примере машины стоят вплотную, и между ними нельзя поставить никакую машину.

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

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

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

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

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

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

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

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

Если не существует машины, которую можно было бы поставить, удовлетворяя все условия, выведите 0.

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

Ввод	Вывод
4 21 1 1 7 12 3 16	2
4 30 3 1 24 5 11 18	3
2 20 3 1 7 10	5

Задачи на моделирование Использование сортировки реализация

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

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

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

Ваша задача — написать программу, которая определит время следующего резервного копирования после начала смены Ильи Филипповича. Считается, что резервное копирование происходит мгновенно. Таким образом, если Илья Филиппович заступает в момент резервного копирования, считается, что оно происходит уже в его смену.

Формат входного файла

На вход программе подается строка, в которой находится время заступления Ильи Филипповича в формате hh:mm:ss, где hh обозначает часы в 24-часовом формате, mm — минуты, а ss — секунды. Гарантируется, что время корректно.

Формат выходного файла

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

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

Ввод	Вывод
12:55:00	13:00:00
00:00:00	00:00:00
18:30:03	19:00:00

Дата и время Задачи на моделирование

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

Пираты!#27043

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

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

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

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

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

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

В первой строке записано натуральные числа N и M (1 <= N, M <= 1 000 000) количество строк и столбцов на игровом поле.

Во второй строке записано натуральное число K (1 <= K <= 500) количество пиратских баз.

В следующих K строках записаны пары чисел R_i , C_i (1 <= R_i <= N, 1 <= C_i <= M) координаты пиратских баз (строка, столбец).

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

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

Система оценки

Решения, верно работающие при N, M 6<=500, будут набирать не менее половины баллов.

Ввод	Вывод
10 10 4 2 2 5 3 5 9 8 8	3

Замечание

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

Двумерные массивы Использование сортировки

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

S.L.O.T.#27023

Вчера знаменитый певец S.L.O.T. исполнил на концерте свой лучший трек "10 марта" и множество других. Дамир ОЧЕНЬ захотел на этот концерт и уже купил билеты, как вдруг понял, что до концерта всего час, а ему нужно доехать до места проведения концерта (естественно, на трамвае).

Трамвай необходимое расстояние преодолевает за 59 минут. Будем считать, что концерт проводится на трамвайной остановке, то есть Дамир вполне на него успевает, но ему подходит только ему подходят лишь трамваи, номера которых являются перестановками от 1 до n. При этом он только что увидел, как с его остановки уезжает трамвай с номером p. Однако Дамир - великий эстет, и он хочет сесть на трамвай, номер которого равен следующей перестановке после p. Поскольку трамваи подходят к его остановке мнгновенно, на концерт любимого исполнителя он успеет в любом случае.

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

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

В первой строке вводится число n - количество чисел в перестановке в номере трамвая

Во второй строке ЧЕРЕЗ ПРОБЕЛ!! вводится n чисел, которые задают p - номер трамвая, который только что отошёл от остановки Дамира

Третья строка содержит k - количество трамваев, которые скоро подъедут к остановке Дамира (гарантируется, что один из трамваев подходит Дамиру)

Далее идут k строк, которые содержат по n чисел через пробел - номера трамваев

(n <= 7, k <= 5)

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

выведите порядковый номер трамвая, который подходит Дамиру (если таких несколько, выведите наименьший из них, то есть порядковый номер того искомого трамвая, который подъедет к остановке Дамира раньше).

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

Комбинаторика Перестановки

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

Сложные пароли#27022

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

Ввод:
в первой строке вводится n - количество слов и наборов цифр, в следующих n строках вводятся слова / наборы цифр. (n<20, длина строк не превышает 20).

Вывод:
Необходимо вывести все возможные перестановки слов и наборов цифр, если это невозможно, вывести "unreal".

Ввод	Вывод
3 cat 123 215	123cat215 215cat123

(с) Вероника Пеутина

Комбинаторика Простые задачи на перебор реализация

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

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