Типы данных

21 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Звезда в Отеле#91275

Как известно, в Отеле скучно не бывает: то фуршет, то номерки какие-то загадочные. А вот сейчас, для гостей опять подготовили нечто невероятное: приезжает Звезда.

Звезды — народ причудливый, вот например, Звезда, приехавшая в Отель, боится больших скоплений людей, поэтому поклонников на автограф-сессии будет принимать в специальном кабинете и только по одному, все же остальные гости будут ожидать в зале. И все бы хорошо, человечество давно придумало очереди, только вот во время сессии проходит фуршет, поэтому все разбредутся по залу и никакой очереди в ее привычном понимании устроить не получится и САО (служба администрирования очередей) решила обратиться к вам.

Вас просят написать систему учета людей, которая должна уметь выводить номер текущего первого в очереди гостя, добавлять людей в очередь и удалять из нее. Но мало того, что неразбериха с фуршетом, САО ещё и по неизвестной нам причине поощряет использование знакомств и связей в личных корыстных целях (в народе <<блат>>): если в зал приходит человек \(x\), то он хочет найти своего друга \(y\) и, если \(y\) находится в зале, то \(x\) в очереди становится прямо за ним, иначе \(x\) помещается системой в конец очереди. Также может произойти такое, что гостю надоело ждать и тогда он просто уходит из зала ожидания и исключается из очереди.

Конечно, обработка событий по видео-камерам — увлекательный процесс, но САО решили, что проще будет дать уже готовую последовательность данных. Итак, вашей системе нужно обрабатывать следующие запросы:

  1. in x y — в зал фуршета приходит гость с номером \(x\), который дружит с гостем номер \(y\). Если \(y\) уже находится в очереди, то \(x\) встает за ним, иначе в конец. Стоит отметить, что гости очень восхищаются Звездой и могут приходить и не по одному разу.

  2. out x — гостю под номером \(x\) надоело ждать и он уходит (гарантируется, что в данный момент гость с таким номером находится в зале).

  3. check — Звезда готова дать очередной автограф и САО хочет узнать, кто первый в очереди (после этого счастливец получит автограф и уйдет по своим делам). Если очередь пуста, выведите \(-1\).

Формат входных данных
В первой строке вводится единственное натуральное число \(q\) (\(1 \leq q \leq 200\,000\)) — количество запросов. Далее в \(q\) строках вводятся вышеописанные запросы. Все числа, содержащиеся в запросах натуральные и не превосходят \(10^8\).

Формат выходных данных
На каждый запрос \(check\) в отдельной строке выведете номер первого человека в очереди.

МножестваСловариСтруктуры данных
✓ 2✗ 01 200средняяВойти и решать
Искусство ASCII#52184
Давным давно, еще когда не было персональных компьютеров, люди использовали печатные машинки для создания текстов, а самые умельцы создавали картинки из символов. 
Некоторые из таких картинок удалось найти в закодированном виде. Восстановите картинку по строке с кодом. 

Формат входных данных
Программа получает на вход строку с кодом.  Части кода разделены пробелом.
Каждый фрагмент кода это либо: 
nl означает NewLine (переход на новую строку)
либо 
Количество символа и какой символ
В качестве символов может быть любой печатаемый символ ASCII кода (до символа с кодом 127) либо специальные символы, закодированные следующим образом:
sp - пробел
bS - бэкслеш \
sQ - апостроф '
Количество символа - натуральное число, не превышающее 100.

Формат выходных данных 
Выведите получившуюся картинку.
СимволыСтроки
✓ 0✗ 431 400средняяВойти и решать
Задача №2#24632

int main()
{
       string s;
       vector <int> arr = { 70, 109, 108, 96, 37, 100, 114, 113, 41, 56, 96, 61, 59 };
       for(int i = 0; i < arr.size(); i++)
       {
             int x = s[i];
             cout << (x ^ arr[i]) << " ";
       }
       return 0;
}

Какое значение должна принимать строка s, чтобы в результате выполнения программы было выведено
 
1 2 3 4 5 6 7 8 9 10 11 12 13
 
?
 
Входные данные
 
Входные данные пусты
 
Выходные данные
 
Выведите одну строку – ответ на задачу.

(c) Егор Курбатов, 10и
Битовые операцииЦелые числа
✓ 0✗ 261 300средняяВойти и решать
Ёлочная гирлянда#93202

Ёлочная гирлянда состоит из n лампочек, пронумерованных от 1 до n. Каждая лампочка либо горит (обозначим «1»), либо не горит («0»). Текущее состояние гирлянды задано строкой a.

Монтажник Егор хочет, чтобы гирлянда выглядела по-праздничному — в виде строки b (тоже из нулей и единиц, той же длины n). Менять строку b нельзя — это «образец».

С гирляндой a Егор может выполнять две операции:

  • Переключить одну лампочку. Выбрать позицию i (1 ≤ i ≤ n) и поменять её состояние (0 → 1 или 1 → 0). Стоимость такой операции — 1 рубль.
  • Поменять местами две лампочки. Выбрать две позиции i и j (1 ≤ i, j ≤ n) и поменять состояния этих лампочек местами. Стоимость такой операции — |i - j| рублей, то есть расстояние между позициями.

Помогите Егору найти минимальную суммарную стоимость, с которой можно превратить гирлянду a в гирлянду b.
 

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

В первой строке — целое число n (1 ≤ n ≤ 106) — количество лампочек в гирлянде.

Во второй строке — строка a длины n, состоящая только из символов «0» и «1», — текущее состояние гирлянды.

В третьей строке — строка b длины n, состоящая только из символов «0» и «1», — желаемое состояние гирлянды.
 

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

Одно целое число — минимальная суммарная стоимость, которую нужно заплатить, чтобы превратить a в b.

*1300дпжадные алгоритмыСтроки
1 300средняяВойти и решать
Перевод ДНК в аминокислоты#58285

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

Необходимо:

  1. Найти старт-кодон ATG.
  2. Найти ближайший стоп-кодон (TAA, TAG, TGA) после старт-кодона.
  3. Перевести последовательность между старт- и стоп-кодонами в аминокислотную последовательность.
  4. Повторить процесс для всех возможных белков в последовательности.
Можете использовать словарь генетического кода: https://silvertests.ru/NoteBook.aspx?id=58286
Поиск подстроки в строкеСтроки
✓ 4✗ 481 200средняяВойти и решать
Подсчёт длины белков в последовательности ДНК#58281
В процессе трансляции последовательность ДНК сначала транскрибируется в РНК, а затем транслируется в белок. Белки кодируются участками между старт-кодоном (ATG) и ближайшим стоп-кодоном (TAA, TAG, TGA). Длина белка измеряется количеством аминокислотных остатков, где каждые три нуклеотида (триплет) кодируют одну аминокислоту.
Надо написать программу, которая:
  • Найти все белковые последовательности в заданной цепочке ДНК.
  • Подсчитать длину каждой белковой последовательности (в аминокислотах).
  • Вывести все найденные белки и их длины.
Длина белка в аминокислотах - это количество триплетов между старт- и стоп-кодонами.
Поиск подстроки в строкеСтроки
✓ 0✗ 341 400средняяВойти и решать
Максимальный XOR - 2#44507

Два числа a и b записаны в шестнадцатеричной системе счисления. Запись обоих имеет длину n. Вы можете сколько угодно раз менять две соседние цифры местами в любом из чисел. Какое максимальное значение может быть у результата применения побитовой операции XOR к получившимся после применения таких перестановок числам?

Эта операция определена над двоичным представлением чисел.

Определим операцию побитового исключающего «ИЛИ» (XOR). Пусть даны два целых неотрицательных двоичных числа x и y длины k (возможно с ведущими нулями): xk-1...x2x1x0 и yk-1...y2y1y0. Здесь xi это i-й бит числа x, а yi это i-й бит числа y. Пусть r = x XOR y - результат операции XOR над числами x и y. Тогда двоичной записью r будет rk-1...r2r1r0, где:  

\(r_i = \begin{cases} 1, ~ \text{если} ~ x_i ~ \neq ~ y_i \\ 0, ~ \text{если} ~ x_i ~ = ~ y_i \end{cases}\)



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

В первой строке содержится одно целое число n (1 <= n <= 100000) - длина записи чисел. Во второй строке задана запись числа a. В третьей строке задана запись числа b.

Буквы A, B, C, D, E, F отвечают за цифры 10, 11, 12, 13, 14, 15 в шестнадцатеричной системе счисления соответсвенно. Записи могут содержать ведущие нули.


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

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


Примечание

В первом примере можно поменять две соседние цифры в первом числе, получится F0 XOR 0E = FE.

Во втором примере любая перестановка цифр не меняет a  XOR  b. Обратите внимание, что длина выводимого числа должна быть равна n, поэтому надо выводить лидирующие нули.

В третьем примере можно получить 101010 из a и 010100 из b.

 
Примеры
№ Входные данные Выходные данные
1 
2
0F
0E
 
FE
2 
3
000
000
 
000
3 
6
010110
011000
 
111110
Битовые операции
✓ 6✗ 71 200средняяВойти и решать
Анализ файла#39618
Текстовый файл состоит не более чем из 106 символов и содержит только заглавные буквы латинского алфавита (ABC…Z). Текст разбит на строки различной длины. Назовем подпоследовательность оригинальной, если она ограничена слева подстрокой AВ, а справа подстрокой BA (данные подстроки также входят в подпоследовательность) и при этом в этой подпоследовательности нет других букв А и B. Оригинальная подпоследовательность не может начинаться в одной строке, а заканчиваться в другой.
Определите, сколько  всего  оригинальных подпоследовательностей во всем файле, а также длину максимальной из них.

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

Пример
Исходный файл:
AAABCAABCBAA
ZZABZZZBABCBA
QRABUTUUBA
В этом примере всего 4 оригинальных подпоследовательности (AВСВА, ABZZZBA, ABCBA, ABUTUTBA)
Самая длинная подпоследовательность (ABUTUTBA) имеет длину 8.
Ответ: 48


Файл к заданию
ЕГЭ_информатикаЕГЭ-24. Обработка символьных строкСтроки
1 400труднаяВойти и решать
Число Громозеки#38630
Пусть S(n) обозначает сумму цифр числа n в десятичной системе счисления. Например, S(123) = 1 + 2 + 3 = 6. Мы будем называть целое число n числом Громозеки, если для всех положительных целых чисел m таких, что m > n, выполняется условие \(\frac {n}{S(n)} <= \frac {m}{S(m)}\). По заданному целому числу K, перечислите K наименьших чисел Громозеки.

Входные данные
На вход подается целое число K (K>=1, K-ое наименьшее число Громозеки не больше 1015).

Выходные данные
Выведите K строк. В i-й строке должен быть указан i-й наименьший номер Громозеки.
 

 

Примеры
№ Входные данные Выходные данные
1 10 1
2
3
4
5
6
7
8
9
19

 

Вложенные циклыЦелые числа
✓ 2✗ 51 200средняяВойти и решать
Ёлочка#38324
«Нарисуйте» с помощью символов на экране лес. При этом не пользуйтесь командами перемещения курсора по экрану. Ваша программа должна последовательно выводить символы строк (или строки целиком).

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

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

Елочки должны изображаться символами «#» (решеточка), а пустые места между ними — символами «.» (точка). Во всех строках должно быть выведено одинаковое количество символов, при этом обязательно должна быть строка, в которой последним символом является решеточка, в последней строке обязательно должны быть решеточки (т.е. должен быть выведен прямоугольник из точек и решеточек, в нем не должно быть лишних столбцов и строк).

Входные данные
Вводится число елочек N, а дальше N пар натуральных чисел, описывающих елочки: первое число каждой пары задает количество треугольников в елочке, а второе — размер самого маленького треугольника. Елочки описываются в порядке слева направо (если смотреть на вершины елочек).

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

Выходные данные
Выведите требуемый «рисунок». Для лучшего понимания смотрите примеры.
 
Примеры
№ Входные данные Выходные данные
1 2
3 2
3 3		 
...#......#....
..###....###...
...#....#####..
..###.....#....
.#####...###...
...#....#####..
..###..#######.
.#####....#....
#######..###...
........#####..
.......#######.
......#########
2 3
1 1
2 1
3 2		 
#.#...#...
..#..###..
.###..#...
.....###..
....#####.
......#...
.....###..
....#####.
...#######
Задачи на моделированиеСимволы
✓ 3✗ 11 200средняяВойти и решать
Телеграммы Матроскина#38264
Когда Дядя Фёдор уехал домой в город, следить за хозяйством остались Матроскин и Шарик. Но поскольку Дядю Фёдора очень волновали дела в Простоквашино, они договорились, что каждую неделю Матроскин будет писать письмо с отчетом о делах. Довольно скоро Матроскин понял, что письма идут слишком долго, поэтому решил отправлять телеграммы. Обычно отчеты очень длинные, поэтому Матроскину пришлось отправлять несколько телеграмм. Чтобы Дяде Фёдору было удобнее разобраться в пришедших телеграммах, Матроскин следует следущим правилам:

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

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

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

Выходные данные
В первой строке выведите число N – количество телеграмм, на которое надо разбить исходную строку. В следующих N строках выведите сами телеграммы. Если текст передать заданным способом невозможно, выведите −1.

 
Примеры
№ Входные данные Выходные данные
1 deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl bwuoio 2
deesecnj vmguhee xhled rrr dfjhj fdytiaf baulvovt kvhygzhv wfaocftf scugmcqsk wadi bjeiq coesxqgnry tmlko gpmwns rcf dtdey bvirmlv gzl...
...bwuoio
Строки
✓ 3✗ 1421 200средняяВойти и решать
Обработка больших данных#33128
В научной лаборатории разрабатывается новая архитектура суперкомпьютера,
позволяющая эффективно обрабатывать большие объемы данных.
Суперкомпьютер имеет 2k ячеек памяти, пронумерованных от 0 до 2k– 1. Отрезком
[L, R] называется последовательность подряд идущих ячеек памяти с номерами от L до R,
включительно.
Некоторые отрезки памяти являются корректными. Отрезок памяти [L, R] является
корректным, если его длина (R – L + 1) равна 2i для некоторого i, а число L делится на 2i.
Например, если k = 3, то ячейки памяти пронумерованы от 0 до 7, а корректными являются
отрезки [0, 7], [0, 3], [4, 7], [0, 1], [2, 3], [4, 5], [6, 7], [0, 0], [1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,
6] и [7, 7].
Ключевой операцией в новой архитектуре является операция STORE, которая за одно
действие присваивает одно и то же значение всем ячейкам памяти некоторого корректного
отрезка.
Исходно все ячейки памяти содержат значение 0. В лаборатории планируют запустить
на суперкомпьютере программу обработки данных, но перед её запуском необходимо
инициализировать память определенным образом. А именно: первые с1 ячеек памяти
необходимо заполнить значениями v1, следующие c2 ячеек — значениями v2, и так далее,
последние cn ячеек памяти необходимо заполнить значениями vn, где 1 ≤ vi ≤ m.
Ученым надо выяснить, какое минимальное количество операций STORE необходимо
выполнить, чтобы проинициализировать память требуемым образом.
Например, если k = 3, n = 3, m = 2, c1 = 1, v1 = 1, c2 = 2, v2 = 2, c3 = 5, v3 = 1, то итоговое
содержимое памяти должно быть следующим: [1, 2, 2, 1, 1, 1, 1, 1]. В этом случае для
инициализации памяти достаточно трех операций STORE:
- STORE([0, 7], 1), после этой операции все ячейки памяти содержат значение 1;
- STORE([1, 1], 2), после этой операции содержимое памяти [1, 2, 1, 1, 1, 1, 1, 1];
- STORE([2, 2], 2) , после этой операции содержимое памяти [1, 2, 2, 1, 1, 1, 1, 1],
как и требуется.
Заметим, что операцию STORE([1, 2], 2) выполнить нельзя, потому что [1, 2] не
является корректным отрезком памяти.
Требуется написать программу, которая по заданному содержимому памяти
определяет минимальное количество операций STORE, которое необходимо выполнить для
инициализации памяти заданным образом.

Формат входных данных
Первая строка входных данных содержит три целых числа: k, n и m (0 ≤ k ≤ 30,1 ≤ n ≤ 10
5, 1 ≤ m ≤ 109).
Следующие n строк содержат по два целых числа, i-я из этих строк содержит числа ci
и vi (1 ≤ ci ≤ 2k, 1 ≤ vi ≤ m, c1 + c2 + … + cn = 2k).
Формат выходных данных
Требуется вывести одно целое число – минимальное количество операций STORE,
которое необходимо выполнить для инициализации памяти заданным образом.
 
Ввод Вывод
3 3 2
1 1
2 2
5 1
 3
Динамическое программированиеМножестваСтруктуры данных
✓ 0✗ 101 300средняяВойти и решать
Лифт#33123
В современном многоэтажном офисе крупной компании установлен новый лифт. В
компании работает n сотрудников. Для проверки эффективности системы управления
лифтом требуется провести моделирование его работы в конце рабочего дня, когда все
сотрудники должны покинуть здание и спуститься на первый этаж.
В здании m этажей, пронумерованных от 1 до m снизу-вверх. Известно, что i-й
сотрудник подходит к лифту в секунду ti на этаже ai, чтобы спуститься на первый этаж.
На каждом этаже могут находиться люди, ожидающие лифт. Когда очередной
сотрудник подходит к лифту, он вызывает лифт, если на этом этаже лифт еще не вызван,
либо присоединяется к ожидающим лифт. Таким образом, помимо вызвавшего лифт, вместе
с ним лифт могут ожидать и другие сотрудники.
В каждый момент времени не более одного вызова является активным.
Изначально лифт свободен и находится на первом этаже. Когда поступает первый
вызов, этот вызов становится активным и лифт отправляется на соответствующий этаж. Если
несколько вызовов поступает одновременно, активным становится вызов от сотрудника с
меньшим номером.
Лифт перемещается между этажами со скоростью один этаж в секунду. Когда лифт
оказывается на этаже, откуда был сделан активный вызов, в него заходят все, кто уже
ожидает лифт на этом этаже, и лифт отправляется вниз на первый этаж, со скоростью один
этаж в секунду.
При движении вниз лифт останавливается на тех этажах, в которых был сделан вызов
на момент проезда лифта мимо этого этажа. Все ожидающие лифт сотрудники заходят в него
и вызов на этом этаже сбрасывается. Когда лифт завершает движение на первом этаже, все
люди выходят из лифта, а лифт ожидает следующего вызова.
Если в момент, когда лифт освободился, есть хотя бы один необслуженный вызов,
активируется вызов, который поступил раньше других. Если несколько вызовов поступило
одновременно, активируется вызов от сотрудника с меньшим номером. Лифт продолжает
обслуживание описанным образом, пока все n сотрудников не окажутся на первом этаже.
Будем считать, что люди входят и выходят из лифта мгновенно. Каждую секунду
сначала люди подходят и вызывают лифт, а затем выполняются соответствующие действия
(лифт перемещается на соседний этаж, в него входят или из него выходят люди, принимается
решение, на какой вызов лифт должен отреагировать).
Требуется написать программу, которая по описанию вызовов лифта для каждого
сотрудника определяет, в какой момент этот сотрудник окажется на первом этаже.

Формат входных данных
Первая строка входных данных содержит целые числа n и m — количество людей,
вызывающих лифт, и количество этажей в здании (1 ≤ n ≤ 105, 2 ≤ m ≤ 109).
Следующие n строк описывают сотрудников, i-я из этих строк содержит два целых
числа ti и ai — секунду, в которую i-й сотрудник подходит к лифту, и номер этажа, на
котором это происходит (1 ≤ t1 ≤ t2 ≤ … ≤ tn ≤ 109, 2 ≤ ai ≤ m)
 
Формат выходных данных
Выходные данные должны содержать n целых чисел, для каждого сотрудника
требуется вывести секунду, в которую он выйдет из лифта на первом этаже.
 
Ввод Вывод
5 4
2 3
2 4
5 2
5 3
9 3
 
6
12
6
12
12

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


Использованные в пояснении к примеру обозначения
Использование сортировкиМножестваСортировка событийСтруктуры данных
✓ 0✗ 91 300средняяВойти и решать
Генерация ПСП#27312

Самой инновационной разработкой "British Scientists, Inc" является способ нахождения решения для любой задачи, которую возможно решить с помощью тильда-омега-лямбда-исчисления (то есть, для никакой). Для этого они перебирают все возможные скобочные последовательности длины x, где х - первая цифра секретной константы, использующейся во многих разработках компании. Если x нечётное, они просто прибавляют к нему единицу. Потом они используют продвинутые алгоритмы, использующие нейролингвистическое программирование и вычисленные по спирали Фибоначчи числа Каталана гуголдцатого порядка для определения местонахождения термов. Но эти алгоритмы уже реализованы и запатентованы. 

Ваша же задача - реализовать алгоритм перебора. 


Входные данные
На вход подаётся первая цифра секретной константы - x (\(1 <= x <= 9\)). 
 

Выходные данные
Нужно вывести все ПСП длины x (или x+1, если \(x \% 2 ==1\)) в лексикографическом порядке.

 

Примеры
№ Входные данные Выходные данные
1 1
( )
[ ]
{ }
Рекурсивный переборСтроки
✓ 8✗ 4501 200средняяВойти и решать
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средняяВойти и решать
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 106 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средняяВойти и решать
Шифрование#27098
Одним из самых простых способов шифрования открытого текста является шифр простой замены. Он состоит в том, что каждая буква в алфавите, которым написано открытое сообщение, заменяется на какой-то другой символ, например, другую букву того же алфавита. Пусть дана таблица замены, использующая для замены только 33 буквы русского алфавита в верхнем регистре (заглавные буквы):
   
Сообщение Шифртекст Сообщение Шифртекст Сообщение Шифртекст
А Г К Т Х З
Б Ш Л Х Ц Ж
В Ы М Я Ч Л
Г О Н Ь Ш Ё
Д Э О Ф Щ Н
Е Ц П У Ъ Д
Ё М Р К Ы Е
Ж Ъ С Ю Ь Б
З Щ Т Р Э Ч
И А У П Ю И
Й В Ф С Я Й

Если применить замену, заданную такой таблицей, к слову «ДОМ», получится зашифрованный текст «ЭФЯ». Если применить замену к полученному результату, из «ЭФЯ» получится «ЧСЙ», а из «ЧСЙ» таким способом можно получить текст «ЛЮВ». Известно, что через некоторое количество применений замены полученный результат совпадет с исходным словом «ДОМ», после чего результаты замены начнут повторяться. Определите, сколько различных шифртекстов (включая совпадающий с исходным словом) можно получить из произвольного заданного слова по произвольно заданной таблице замены таким способом.

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

Формат ввода:
В первой строке задана строка с  алфавитом используемых символов. Во второй строке задана последовательность заглавных букв, заменяющих буквы, стоящие в алфавитном порядке (таблица замены). Например, приведенной выше таблице соответствует строка «ГШЫОЭЦМЪЩАВТХЯЬФУКЮРПСЗЖЛЁНДЕБЧИЙ». В следующей строке задано слово, являющееся открытым текстом – в верхнем регистре (заглавными буквами) без пробелов. Например, слово «КРИПТОАНАЛИЗ».
Каждая из этих строк заканчивается либо символами с кодами 13, 10 (окончание строк DOS – для Pascal ABC .NET), либо символом с кодом 10 (окончание строк Unix) в зависимости от выбранного при сдаче программы типа конца строк. Никаких других символов в двух входных строка не встречается.
Русский текст задан в кодировке Windows-1251 (cp1251). В ней заглавные русские буквы от "А" до "Я" кроме буквы "Ё" имеют коды от 192 (шестнадцатеричное C0) до 223 (шестнадцатеричное DF). Буква "Ё" имеет код 168 (шестнадцатеричное A8). Русские буквы (кроме "Ё") упорядочены по алфавиту.

Формат вывода:
В единственной строке выведите число, соответствующее количеству различных возможных шифртекстов, которые можно получить из заданного открытого текста с помощью заданной таблицы замены.
 
Задача на реализациюМножестваСтруктуры данных
✓ 5✗ 351 200средняяВойти и решать
Урок физкультуры#21998
Феоктист Всеволодович — преподаватель физкультуры старой закалки, глубоко убеждённый, что в начале каждого урока школьников необходимо построить по росту. Для этого он сначала просит школьников построиться самостоятельно, после чего последовательно меняет местами про- извольную пару стоящих рядом учеников, пока шеренга не примет желанный вид.

Всего на урок пришло N детей, изначально построившихся таким образом, что рост стоящего на позиции i равен hi (используется нумерация c 1). Можно считать, что все числа hi различны и лежат в диапазоне от 1 до N. Шеренга считается упорядоченной, если на первой позиции стоит школьник ростом один, на второй позиции стоит школьник ростом два и так далее.

Феоктист Всеволодович получает большое удовольствие от процесса упорядочивания школьни- ков, поэтому он всегда выбирает наиболее длинную последовательность обменов. С другой стороны, он не хочет чтобы ученики догадались о том, что он умышленно затягивает построение, поэтому никогда не делает заведомо бессмысленных обменов. А именно, преподаватель никогда не меняет местами школьников на позициях i и j, если hi < hj . Очевидно, что данное ограничение делает процесс сортировки шеренги по росту конечным.

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

Формат входных данных
В первой строке ввода содержится единственное число N — количество школьников на уроке (1 <= N <= 1 000 000). Во второй строке записано N различных целых чисел hi (1 <= hi <= N). i-е число соответствует росту школьника стоящего на i-й позиции.

Формат выходных данных
Выведите два числа — номера позиций школьников, которым необходимо поменяться местами, чтобы минимизировать количество действий преподавателя. Если таких пар несколько, то выведите любую из них. Если никому меняться местами не нужно, выведите -1 -1.
Ввод Вывод
5
2 4 3 5 1		 2 5
4 1 2 3 4 -1 -1
10
2 3 7 1 5 10 4 6 9 8		 3 7
Дерево отрезков, RSQ, RMQСканирующая прямаяСловариСтруктуры данных
✓ 1✗ 391 200средняяВойти и решать
Британские учёные и Василий#21951
По рзелульаттам илссеовадний одонго анлигйсокго унвиертисета, не иеемт занчнеия, в кокам пряокде рсапожолены бкувы в солве. Галвоне, чотбы преавя и пслоендяя бквуы блыи на мсете. Осатьлыне бкувы мгоут селдовтаь в плоонм бсепордяке, все-рвано ткест чтаитсея без побрелм. Пичрионй эгото ялвятеся то, что мы чиатем не кдаужю бкуву по отдльенотси, а все солво цликеом.

Вдохновившись исследованием британских учёных о восприятии человеком текста, Вася решил, что современная письменность нуждается в серьёзном упрощении. В частности, в лексиконе Васи все слова состоят только из букв a, b и c. Кроме того, память у Васи плохая, поэтому Вася помнит лишь слова, которые содержат не более L букв.

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

Британские учёные очень заинтересовались исследованиями Васи. Они вступили с молодым учё- ным в активную переписку, однако, получив очередное Васино сообщение были несколько озадачены тем, что же он имел ввиду. Так как разобраться они так и не смогли, а очередное революционное открытие уже было проанонсировано в СМИ, они решили как-то оценить уровень гениальности автора. Для этого они решили понять, а из какого минимального количества слов может состоять словарный запас Василия?

Формат входных данных
В первой строке входных данных содержится целое число L — максимальная длина слова, кото- рое может содержаться в лексиконе Васи (1 <= L <= 10 000). В следующей строке содержится непустое сообщение, полученное учеными. Длина сообщения не превосходит 20 000 символов.

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

Пример
Ввод:
3
ababaabab

Вывод:
2
aba
ab

Замечание
В первом примере из условия одним из возможных способов проинтерпретировать Васино сооб- щение является: ab aba ab ab.
Z-функция. Префикс-функцияСтроки
✓ 3✗ 851 200средняяВойти и решать
Поделиться
Класснуть