Типы данных

741 задачавместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: успешные, неуспешные.
Вам дан словарь, состоящий из пар слов. Каждое слово является синонимом к парному ему слову. Все слова в словаре различны. Для одного данного слова определите его синоним.
 
Входные данные
Программа получает на вход количество пар синонимов N. Далее следует N строк, каждая строка содержит ровно два слова-синонима. После этого следует одно слово.
 
Выходные данные
Программа должна вывести синоним к данному слову.
 
Пример
Входные данные Выходные данные
1
3
Hello Hi
Bye Goodbye
List Array
Goodbye
Bye
✓ 216✗ 90500лёгкаяВойти и решать
Задана строка, состоящая только из:
• прописных и строчных букв английского алфавита;
• символов подчёркивания (они используются в качестве разделителей);
• круглых скобок (как открывающих, так и закрывающих).

Гарантируется, что каждая открывающая скобка имеет парную закрывающую, идущую следом. Аналогично, каждая закрывающая скобка имеет парную открывающую, которая расположена до неё. Для каждой пары соответствующих скобок верно, что между ними нет каких-либо других скобок. Иными словами, каждая скобка в строке входит в пару «открывающая-закрывающая», и такие пары не вкладываются друг в друга.
Например, допустимой строкой является: _Hello_Vasya(and_Petya)__bye_(and_OK)
Словом называется нерасширяемая последовательность подряд идущих букв, то есть последовательность букв, где слева и справа от неё находится скобка или символ подчёркивания, или соответствующий символ отсутствует.
Приведенный пример содержит семь слов: «Hello», «Vasya», «and», «Petya», «bye», «and» и «OK».

Напишите программу, которая найдет:
• длину самого длинного слова вне скобок (выведите 0, если слов вне скобок нет),
• количество слов внутри скобок (выведите 0, если слов внутри скобок нет).
 
Входные данные: в первой строке записано целое число n (\(1 <= n <= 255\)) — длина заданной строки. Во второй строке записана строка, состоящая только из строчных и прописных английских букв, открывающих и закрывающих скобок, а также символов подчёркивания.
 
Выходные данные: выведите два числа:
• длину самого длинного слова вне скобок (выведите 0, если слов вне скобок нет);
• количество слов внутри скобок (выведите 0, если слов внутри скобок нет).
 
Примеры
Входные данные Выходные данные
1 37
_Hello_Vasya(and_Petya)__bye_(and_OK)
5 4
2
37
_a_(_b___c)__de_f(g_)__h__i(j_k_l)m__
2 6
3
27
(LoooonG)__shOrt__(LoooonG)
5 2
4
5
(___)
0 0

Примечание
В первом примере слова «Hello», «Vasya» и «bye» записаны вне скобок, а слова «and», «Petya», «and» и «OK» — внутри. Обратите внимание, что слово «and» встречается дважды, и учитывать в ответе его тоже следует два раза.
✓ 267✗ 670700средняяВойти и решать
Найти в строке указанную подстроку и заменить ее на новую. Строка s, ее подстрока s1 для замены и новая подстрока s2 вводятся.

P.S. Искомые подстроки в исходной строке не пересекаются.
P.P.S. В строках не содержатся пробелы.
P.P.P.S. Искомая подстрока может встречаться неоднократно.
P.P.P.P.S. Все буквы строчные.
P.P.P.P.P.S. Нет символов помимо строчных латинских букв.

На вход подаются 3 строки: s, s1, s2. Длина всех строк не превосходит 100.
 
Примеры
Входные данные Выходные данные
1 abcde
ab
fg
fgcde
2
ababc
ab
c
ccc

 
✓ 698✗ 1 505500лёгкаяВойти и решать
Имеется прямая, покрашенная в белый цвет. На нее добавляют n черных отрезков один за другим.
Определите количество компонент связности из черных отрезков (то есть количество черных отрезков в объединении) после каждого добавления отрезка.
В частности, считайте, что если один отрезок заканчивается в точке x, а другой отрезок начинается в точке x, то эти два отрезка лежат в одной компоненте связности.
 
Входные данные
В первой строке следует целое число n (1 ≤ n ≤ 200 000) — количество отрезков.
i-я из следующих n строк содержит два целых числа li и ri (1 ≤ li < ri ≤ 109) — координаты левого и правого концов отрезка номер i. Отрезки перечислены в порядке их добавления на белую прямую.
 
Выходные данные
Выведите n целых чисел — количество компонент связности из черных отрезков после каждого добавления отрезка.

 
Примеры
Входные данные Выходные данные
1
3
1 3
4 5
2 4
1 2 1
2
9
10 20
50 60
30 40
70 80
90 100
60 70
10 40
40 50
80 90
1 2 3 4 5 4 3 2 1

 
 
✓ 54✗ 164900средняяВойти и решать
Входные данные
Дано число N (1 <= N <= 100000) – кол-во запросов. В следующих N строках содержится символ ‘+’ или ‘-’ и число a (1 <= a <= 1000000000). Если символ – ‘+’, то число a добавляется в множество, иначе – удаляются все значения a, которые были добавлены ранее.
Гарантируется, что при удалении числа, оно содержится в множестве.

Выходные данные
Требуется вывести в порядке возрастания все уникальные элементы в множестве после выполнения всех запросов или «-1», если в множестве нет элементов.

 
Примеры
Входные данные Выходные данные
1
3
+ 1
+ 2
- 1
2
2
3
+ 1
+ 1
- 1
-1
3
3
+ 1
+ 1
+ 1
1
Ежегодно в Санкт-Петербурге, Барнауле и некоторых городах ближнего зарубежья проходят соревнования по программированию. Эти соревнования проходят в рамках студенческого чемпионата мира по программированию, организованного одной из самых авторитетных ассоциаций АСМ (Association for Computing Machinery). На этих соревнованиях проходит отбор команд с Северо-Восточного Европейского Региона NЕЕRС (North-Eastern European Regional Contest). Ежегодно перед организаторами соревнований встает проблема определения команд, которые будут приглашены к участию в финале чемпионата мира по программированию. По новым правилам в финал проходят не более N команд, представляющих NEERC. Кроме этого, от одного вуза не может проходить более чем k команд. При этот из всех таких множеств выбирается то, в котором сумма мест занятых этими командами в полуфинальных соревнованиях минимальная возможная. Ваша задача по итоговому протоколу полуфинальных соревнований и числам N и k определить, какие команды будут приглашены к участию в финале чемпионата мира.
 
Входные данные
В первой сроке входного файла находится три натуральных числа Р (1 ≤ P ≤ 100000) — количество команд, принявших участие в полуфинале, N (1 ≤ N ≤ P ) и k (1 ≤ k ≤ P ) . В следующих P строках, по одному в строке перечислены названия университетов, команды которых заняли соответствующие места. Название университета содержит строчные и прописные латинские буквы и пробелы. Длина названия университета не превышает 30 символов. В следующей строке перечислены номера команд соответствующих университетов. Таким образам если название университета записано в i -той строке (2 ≤ i ≤ P + 1) , то эта команда заняла i - 1 место на полуфинале и имеет номер, записанный на i - 1 месте в P + 2 строке.
 
Выходные данные
В выходной файл выведите названия команд, приглашенных к участию в финале чемпионата мира по программированию, упорядоченных по месту, занятому на полуфинале. В качестве названия команды выведите название университета и через пробел #номер команды.
 
Пример
Входные данные Выходные данные
1
9 5 2
Fantasy University
Crazy University
Fantasy University
Fantasy University
Very Good U
Good U
Very Good U
Crazy University
Good U
1 1 2 3 2 1 1 2 2
Fantasy University #1
Crazy University #1
Fantasy University #2
Very Good U #2
Good U #1
✓ 367✗ 667800средняяВойти и решать
В мирное время казаки занимаются сельским хозяйством. Пантелей Прокофьевич Мелехов выращивает специальные математические овощи, которые растут по очень странным правилам: у каждого семечка i этих овощей есть значение урожайности ai, а урожайностью всей грядки является произведение урожайностей всех семян, посаженных на ней. У Мелехова есть N семян. Помогите ему выбрать из этих семян несколько так, чтобы при посадке этих семян урожайность грядки была максимальна.
 
Входные данные:
В первой строке содержится число N (1 <= N <= 15)
Во второй - N чисел ai, возможно вещественных (|ai| < 10)
 
Выходные данные:
Выведите максимальную урожайность грядки с точностью не менее 6 знаков после запятой, которой можно добиться с данным набором семян. Гарантируется, что оно больше 1.
 
Ввод Вывод
5
2.0 -1.2 4.7 -2.9 -1.1
32.712000

(с) Григорьев Е., 2018
Дана база данных о продажах некоторого интернет-магазина. Каждая строка входного файла представляет собой запись вида:
Покупатель товар количество,
где Покупатель — имя покупателя (строка без пробелов), товар — название товара (строка без пробелов), количество — количество приобретенных единиц товара.
 
Создайте список всех покупателей, а для каждого покупателя подсчитайте количество приобретенных им единиц каждого вида товаров.
 
 
Входные данные
В первой строке входного файла содержится число N (\(1<=N<=100000\)) —количество записей содержащихся в данной базе данных. Вводятся сведения о покупках в указанном формате.
 
Выходные данные 
Выведите список всех покупателей в лексикографическом порядке, после имени каждого покупателя выведите двоеточие, затем выведите список названий всех приобретенных данным покупателем товаров в лексикографическом порядке, после названия каждого товара выведите количество единиц товара, приобретенных данным покупателем. Информация о каждом товаре выводится в отдельной строке.
 
 
Пример
Входные данные Выходные данные
1
6
Ivanov paper 10
Petrov pens 5
Ivanov marker 3
Ivanov paper 7
Petrov envelope 20
Ivanov envelope 5
Ivanov:
envelope 5
marker 3
paper 17
Petrov:
envelope 20
pens 5
✓ 747✗ 996600лёгкаяВойти и решать
В файловую систему одного суперкомпьютера проник вирус, который сломал контроль за правами доступа к файлам. Для каждого файла Ni известно, с какими действиями можно к нему обращаться:
 
запись W
чтение R
запуск X
 
Вам требуется восстановить контроль над правами доступа к файлам (ваша программа для каждого запроса должна будет возвращать OK, если над файлом выполняется допустимая операция, или же Access denied, если операция недопустима).
 
Входные данные
В первой строке содержится число N (1 <= N <= 10000) - количество файлов содержащихся в данной файловой системе.
В следующих N строках содержатся имена файлов и допустимых с ними операций, разделенные пробелами. Длина имени файла не превышает 15 символов.
Далее указано число M (1 <= M <= 50000) - количество запросов к файлам.
В последних M строках указан запрос вида Операция Файл. К одному и тому же файлу может быть применено любое количество запросов.
 
Выходные данные
Для каждого из M запросов нужно вывести в отдельной строке Access denied или OK.
 
 
Пример
Входные данные Выходные данные
1
4
helloworld.exe R X
pinglog W R
nya R
goodluck X W R
5
read nya
write helloworld.exe
execute nya
read pinglog
write pinglog
OK
Access denied
Access denied
OK
OK
✓ 912✗ 1 142600лёгкаяВойти и решать
Дан текст, состоящий из нескольких строк. Текст заканчивается строкой, содержащей единственное слово "END!". Слово "END!" не является содержимым текста, а служит только признаком окончания.

Постройте для данного текста алфавитно-частотный словарь отсортированный по частоте слов: список слов, справа от каждого слова должно быть указано, сколько раз оно встречается в исходном файле. Слова должны идти в порядке убывания. Если количество слов одинаково, сортировка идет по словам в лексикографическом порядке.

Слова должны быть приведены к строчному виду, и без знаков препинания.
 
Пример
Входные данные Выходные данные
1 Duis aute irure dolor in reprehenderit in voluptate.
Velit esse cillum dolore eu fugiat nulla pariatur.
END!
in 2
aute 1
cillum 1
dolor 1
dolore 1
duis 1
esse 1
eu 1
fugiat 1
irure 1
nulla 1
pariatur 1
reprehenderit 1
velit 1
voluptate 1
Слово называется анаграммой другого слова, если оно может быть получено перестановкой его букв.
 
Формат входных данных
Даны два слова на отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.
 
Формат выходных данных
Требуется вывести "YES"  – если введенные слова являются анаграммами друг друга, "NO"  – если нет.
Даны два неупорядоченных набора целых чисел (может быть, с повторениями). Выдать без повторений в порядке возрастания все те числа, которые встречаются в обоих наборах.
 
Входные данные
В первой строке входного потока записано через пробел два целых числа N и М (1 ≤ N, М ≤ 300 000) — количество элементов первого и второго наборов, соответственно. В следующих двух строках записано сначала N чисел первого набора, а затем M чисел второго набора. Числа разделены пробелами. Каждое из этих чисел попадает в промежуток от 0 до 105.
 
Выходные данные
Необходимо вывести в возрастающем порядке без повторений все числа, которые входят как в первый, так и во второй набор. Числа разделять одним пробелом. Если таких чисел нет, то ничего выводить не нужно.
 
Входные данные Выходные данные
11 6
2 4 6 8 10 12 10 8 6 4 2
3 6 9 12 15 18
6 12
RAID#28422
При хранении данных одна из основных задач – соблюдение баланса между расходами на количество дисков и надёжностью записи. Одним из компромиссных по надёжности и стоимости хранения данных является RAID-3 – избыточный массив независимых дисков с выделенным диском для хранения блоков чётности. Наш RAID-3 состоит из пяти дисков, на четырёх из которых содержится информация, а на пятом – блоки контрольных битов чётности. При записи четырёх байтов (по байту на каждый из четырёх дисков) вычисляется контрольный байт четности, составленный из контрольных битов. Для каждого из восьми разрядов вычисляется сумма значений битов в этих разрядах во всех байтах данных, при этом значение контрольного бита выбирается так, чтобы сумма значений во всех разрядах (включая контрольный) была чётной. Например, у нас есть два основных диска и на них записывается байты 10010010 и 01110111. Тогда значение контрольного байта равно 11100101 – в каждом разряде сумма получается чётной.

Один из четырёх основных дисков в RAID-3 вышел из строя. Известны значения байтов в трёх оставшихся дисках и значение байта на контрольном диске. Какой байт был записан на сломавшемся диске? Все числа приведены в десятичной системе счисления.
 
– значения на первых трех дисках: 177, 177, 177, контрольный байт: 177;
– значения на первых трех дисках: 79, 79, 79, контрольный байт: 0;
– значения на первых трех дисках: 46, 56, 248, контрольный байт: 90;
– значения на первых трех дисках: 255, 0, 150, контрольный байт 96;
– значения на первых трех дисках: 137, 232, 23, контрольный байт 212.

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

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

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


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

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

 

Примеры
Входные данные Выходные данные
1 1
( )
[ ]
{ }
Тильда-омега-лямбда-исчисление - ещё более инновационная разработка "British Scientists, Inc" в сфере функционального программирования. Его отличие от омега-лямбда-исчисления только в возможности ставить квадратные и фигурные скобки. Планировались также скобки в форме слоников, но стандарт ЮНИКОД у компании изменить не получилось. 
На вход подаётся тильда-омега-лямбда-выражение длиной не более 10^7 символов. Нужно вывести результат его тильда-иззи-редукции, работающей так же, как и иззи-редукция для омега-лямбда-выражений, но с учётом квадратных и фигурных скобок.

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

 

Примеры
Входные данные Выходные данные
1 main{izzy[lol](ttt)} gg
Омега-лямбда-исчисление - инновационная разработка "British Scientists, Inc" в сфере формальной логики. Любое выражение омега-лямбда-исчисления состоит из круглых скобок и термов (термом может быть любая последовательность из букв латинского алфавита). 
Иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм gg, если нет - в терм wp
На вход подаётся омега-лямбда-выражение длиной не более 107 символов. Нужно вывести результат его иззи-редукции.
 

 

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

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

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

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


Примеры
Входные данные Выходные данные
1
2
((()())
))))))
True
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


 
Ферма Джона представлена решёткой 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"
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
Поделиться
Класснуть