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

Record Keeping#89862

Фермер Джон детально записывает порядок прихода коров на дойку. Каждый час группа из трёх коров входит в амбар и ФД записывает их имена. Например, за 5 часов он имеет такой список, где каждая строка соответствует группе вошедших коров:
BESSIE ELSIE MATILDA FRAN BESSIE INGRID BESSIE ELSIE MATILDA MATILDA INGRID FRAN ELSIE BESSIE MATILDA
ФД заметил, что одна и та же группа коров может несколько раз появляться в этом списке. Например, группа BESSIE, ELSIE и MATILDA появляется три раза (ФД необязательно записывает их имена в одинаковом порядке при каждом входе в амбар).
Помогите ФД посчитать количество приходов той группы, которая пришла наибольшее количество раз.
PROBLEM NAME: records
Формат входных данных
* Строка 1: Количество часов, N, в течение которых ФД вёл запись (1 <= N <= 1000).
* Строки 2..1+N: Каждая строка содержит список из трёх разделенных одиночными пробелами имён. Каждое имя имеет длину от 1 до 10 символов и стоит только из символов A-Z.

Формат выходных данных
* Строка 1: Количество приходов той группы, которая пришла наибольшее количество раз.
Примечание
Группа {BESSIE, ELSIE, MATILDA} вошла в амбар 3 раза.

Словари

—Войти и решать

Уникальные числа#84689

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

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

В первой строке — число N (1 ≤ N ≤ 100000).

Во второй строке — N целых чисел первого массива (1 ≤ число ≤ 1000000).

В третьей строке — число M (1 ≤ M ≤ 100000).

В четвёртой строке — M целых чисел второго массива.

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

Одно число — количество общих уникальных элементов.

Словари

—Войти и решать

Библиотека Мерлина#84679

Волшебник Мерлин управляет своей библиотекой заклинаний. Он может выполнять три типа операций:

+ X — добавить книгу с номером X в библиотеку

- X — убрать книгу с номером X из библиотеки

? X — проверить, есть ли книга с номером X в библиотеке

Помоги Мерлину ответить на все его вопросы!

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

В первой строке — число Q (1 ≤ Q ≤ 100000) — количество операций.

В следующих Q строках — операции в формате: "+ X", "- X" или "? X" (1 ≤ X ≤ 1000000).

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

Для каждой операции "?" выведите "YES", если книга есть в библиотеке, или "NO", если её нет.

Словари

✓ 3✗ 4—Войти и решать

Покемоны#84678

Маша коллекционирует карточки покемонов. Каждый день она покупает новые пакетики с карточками. К сожалению, карточки часто повторяются! Маша хочет знать, сколько уникальных покемонов у неё в коллекции после всех покупок.

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

В первой строке — число N (1 ≤ N ≤ 100000) — количество купленных карточек.

Во второй строке — N целых чисел — номера покемонов на карточках (1 ≤ номер ≤ 1000000).

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

Одно число — количество уникальных покемонов в коллекции.

Словари Хеш

✓ 3✗ 1—Войти и решать

Сортируем словарь (C++)#68143

Алфавитно-частотный словарь - это частотный словарь, в котором слова с указанием их частоты (встречаемости) расположены по алфавиту.
Постройте словарь, отсортированный по частоте слов, в котором слова расположены порядке уменьшения их частоты встречаемости, справа от каждого слова должно быть указано сколько раз оно встречается в тексте. Если количество слов одинаково, сортировка идет по словам в лексикографическом порядке. Признаком окончания текста является "END!".

Входные данные
На вход подаются строки текста. Последняя строка содержит одно единственное слово "END!" и является признаком окончания текста.

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

Примеры

№	Входные данные	Выходные данные
1	один два три один два END!	два 2 один 2 три 1

Словари

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

66401#66401

Группа молодых энтузиастов "МэК" захотели посчитать сколько сантиметров проходит палец сотрудника колл-центра, когда тот набирает номер телефона клиента на циферблате. Для начального варианта программы достаточно считать сколько палец прошёл в одном из направлений, по горизонтали или по вертикали. Расстояние между центрами всех кнопок равно 1, считается, что всегда нажимается центр кнопки.
Расстояние кнопок по диагонали (45 градусов), например между "1" и "5" равно 1.4. Расстояние между Кнопками под 30 градусов, например между "1" и "6" равно 2,2. Расстояние между "1" и "0", а также между "3" и "0" равно 3.1. Начальная позиция пальца оператора всегда на той цифра с которой начинается номер телефона.

Формат входных данных
На вход программы поступает номер телефона, содержащий от 2 до 20 цифр. Также направления: 0 - горизонталь, 1 - вертикаль.
Формат выходных данных
На выходе программа выдаёт число, равное пройденному расстоянию. Например: номер телефона 8965, считаем горизонталь. Из 8 в 9 +1, из 9 в 6 нет движения по горизонтали, из 6 в 5 +1. Общее пройденное расстояние равно 2.
Циферблат:
123
456
789
0

Словари

✓ 1✗ 0—Войти и решать

65961#65961

Агрохолдинг «Дикое Поле» анализирует результаты сбора урожая. Известно, сколько тонн зерна убрали на каждом из N полей, находящихся в распоряжении холдинга. Так как несколько огромных полей сильно влияют на среднее, в агрохолдинге решили ввести другую метрику. Опорными называются поля, урожай с которых превышает пороговое значение, но меньше среднего. Определите наиболее часто встречающийся урожай с опорного поля.
Формат ввода
На вход программе в первой строке подаётся натуральное число N (N ≤ 1000) – количество полей. Во второй строке подаётся натуральное число M (M≤ 100 т) – пороговое значение урожая с поля. Далее в N строках идёт по одному натуральному числу m_i – масса урожая с поля номер i (1≤ m_i ≤1000 т).
Формат вывода
Вывести одно целое число – наиболее часто встречающийся урожай с опорного поля. Если таких значений несколько, выведите наибольшее. Если таких значений нет, выведите 0.

Алгоритмы обработки реализация Словари

✓ 4✗ 3—Войти и решать

65812#65812

Ваня очень дружелюбный мальчик, поэтому у него очень много друзей. Ваня рад этому, но вот делиться, если он что-то купил, приходится со всеми. Потому Ваня придумал очень гениальный план. Когда его спрашивают, что он купил, при выходе с магазина, он хочет называть только те продукты, которыми ему не жалко поделиться.
Продукты, которыми не жалко поделиться, это продукты, которых Ваня купил минимум K//2 (целочисленное деление K на 2), где K – количество друзей, которые встретили Ваню у магазина.
Определите, какими продуктами Ваня поделится в этот раз с ребятами.

Формат входных данных
На вход в программу на первой строке подаётся K – количество друзей, которые встречают Ваню у магазина (1 <= K <= 10000).
На второй строке подаётся N (1 <= N <= 1000000) – количество продуктов, которые купил Ваня.
Далее, на N строках указаны названия продуктов (одно слово английскими буквами), купленных Ваней, притом продукты, которые были куплены более чем в количестве 1 штуки, идут подряд. Если Ваня купил Apple 3 штуки, то Apple будут идти подряд. Но продукты не отсортированы по алфавиту!

Формат выходных данных
На выходе необходимо вывести в отсортированном по алфавиту порядке названия всех продуктов (каждое название на новой строке), которыми поделится Ваня. Если Ваня не поделится с ребятами продуктами, то вывести «NO» заглавными буквами.

Словари

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

Самое частое слово#58238

Алиса только что завершила подсчет уникальных слов в файле. Вдруг экран её компьютера ярко засветился, и на нем появилась новая информация:

"Система обновлена! Новый файл доступен: Число.txt."
P.S. Число в названии файла равно числу, полученному в ответе на предыдущюю задачу. Например, если ответ был 123, то доступен файл 123.txt

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

"В файле слов, как в море, не счесть,
Найди, какое из них чаще здесь есть!"

Алиса быстро принялась за дело! И ты не отставай... Найди ответ

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

Алгоритмы обработки Ввод, вывод данных Словари

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

Сортируем словарь (Python)#56516

Алфавитно-частотный словарь - это частотный словарь, в котором слова с указанием их частоты (встречаемости) расположены по алфавиту.
Постройте словарь, отсортированный по частоте слов, в котором слова расположены порядке уменьшения их частоты встречаемости, справа от каждого слова должно быть указано сколько раз оно встречается в тексте. Если количество слов одинаково, сортировка идет по словам в лексикографическом порядке. Признаком окончания текста является "END!".

Входные данные
На вход подаются строки текста. Последняя строка содержит одно единственное слово "END!" и является признаком окончания текста.

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

Примеры

№	Входные данные	Выходные данные
1	один два три один два END!	два 2 один 2 три 1

Словари

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

Жребий Крижановского#50926

Одиночество есть жребий всех выдающихся умов.

Артур Шопенгауэр

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

Вас назначили ведущим. Помогите установить победителя или определить, что такого нет.

Формат входных данных
В первой строке дано одно число \(n\) (\(1 \le n \le 10^5\)) — количество участников игры. Далее в \(n\) строках вводятся названные участниками натуральные числа, не превосходящие \(10^9\).

Формат выходных данных
Программа должна вывести число, написанное победителем. Если победителя нет, то нужно вывести число \(-1\).

Замечание

В первом примере из условия участвовали \(7\) игроков и они назвали числа \(5\), \(1\), \(1\), \(3\), \(4\), \(3\), \(1\). Сначала оставим только те числа, которые встречаются ровно один раз: \(5\) и \(4\). Минимальное из этих чисел равно \(4\).

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

Алгоритмы обработки реализация Словари

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

Подсчет пар#50778

Вам дан массив A из N чисел. Найдите количество различных пар (i, j), таких, что j>=i и A[i] = A[j].

Формат входных данных
Первая строка входных данных содержит количество тестовых случаев T. Каждый тестовый случай состоит из двух строк, первая строка - число N, за ней следует строка, состоящая из N целых чисел, которые являются элементами массива A.

Ограничения

1 <= T <= 10

1 <= N <= 10⁶ 

-10⁶ <= A[i] <= 10⁶

0 <= i < N

Формат выходных данных
Для каждого тестового случая выведите количество различных пар.

Словари Сортировка подсчетом

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

Словарь#50553

Однажды, разбирая старые книги на чердаке, школьник Вася нашёл англо-латинский словарь. Английский он к тому времени знал в совершенстве, и его мечтой было изучить латынь. Поэтому попавшийся словарь был как раз кстати.

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

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

Помогите Васе выполнить работу по созданию латинско-английского словаря из англо-латинского.

Формат входных данных
В первой строке содержится единственное целое число \(N\) (\(1 \le N \le 100\)) — количество английских слов в словаре. Далее следует \(N\) описаний. В первой строке каждого описания содержится английское слово. В следующей строке записано единственное число \(K \ge 1\) — количество переводов. В следующих \(K\) строках приведены переводы текущего английского слова на латинский, по одному в каждой строке.

Все слова состоят только из маленьких латинских букв. Общее количество слов на входе не превышает \(100\). Длина каждого слова не превосходит 15 символов.

Формат выходных данных
Выведите соответствующий данному латинско-английский словарь в следующем формате. В первую строку запишите единственное целое число \(N\) — количество латинских слов в словаре. Далее выведите \(N\) описаний, каждое описание в отдельной строке: сначала латинское слово, затем отделённый пробелами дефис (символ номер 45), затем разделённые запятыми с пробелами переводы этого латинского слова на английский.

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

Алгоритмы поиска Обработка текста Словари

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

50099#50099

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

Входные данные
В первой строке натуральное число N, не превышающее 10, - количество переменных. Далее N строк, в которых через пробел записано имя переменной в виде одной заглавной латинской буквы, и два целых числа (по модулю не превышают 10⁶) - минимальное и
максимальное значения, которые определяются её типом данных. Затем в следующей строке записано натуральное число M, не превышающее 100 - количество операций над переменными.
Далее в M строках записаны выражения вида A = B + K, где A и B - имена переменных, а K - число, не превышающее по модулю 10⁶. Допустимы две операции: сложение и вычитание.

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

Словари

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

Строка по шаблону#47190

Магистр Аркадий любит работать со строками и создавать для них шаблоны. Сейчас у Аркадия есть строка-шаблон и строка s. Аркадий хочет, чтобы вы определили подходит ли данная строка-шаблон для строки s.

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

Входные данные
Программа получает на вход две строки: строку-шаблон и строка s.

Выходные данные
Выведите YES, если строка-шаблон подходит для строки s, и NO в противном случае.

Примеры

№	Входные данные	Выходные данные
1	abba dog cat cat dog	`YES`
2	abba dog cat cat fish	NO

Словари

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

Волшебные строки#47187

Магистр Аркадий очень любит работать со строками и превращать одни строки в другие. Он считает, что две строки s и t являются "магическими", если символы в s можно заменить таким образом, чтобы получилась строка t. При этом, все вхождения символа заменяются на другой символ с сохранением порядка следования символов. НО, никакие два символа не могут быть заменены на один и тот же символ. Однако символ может быть заменен на самого себя.

Входные данные
Программа получает на вход две строки s и t.

Ограничения

1 <= Длина строки s <= 5 * 10⁴
Длина строки s = Длина строки t
s и t состоят из любых допустимых ASCII символов

Выходные данные
Выведите YES, если данные строки "магические" и NO в противном случае. Вы можете можете выводить ответ в любом регистре.

Примеры

№	Входные данные	Выходные данные
1	egg add	`YES`
1	foo bar	`NO`

Словари

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

Триспектакулярные числа#46944

Триспектакулярные числа - это числа, которые встречаются в каком-либо наборе чисел более чем в ⌊n/3⌋ число раз. В заданном наборе из n чисел, найдите все триспектакулярные числа этого набора.

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

Ограничения

1 <= n <= 5 * 10⁴
-10⁹ <= a[i] <= 10⁹

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

Примеры

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

Словари

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

Наиболее часто встречающееся слово#46411

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

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

Ограничения

1 <= длина текста <= 1000
текст состоит из английских букв, разделителем слов является знак пробела (' '), и/или один из следующих символов: "!?',;.".
0 <= количество запрещенных слов <= 100
1 <= длина каждого запрещенного слова <= 10
запрещенное слово состоит только из английских букв, записанных в нижнем регистре.

Выходные данные
Выведите в нижнем регистре наиболее часто встречаемое слово.

Примеры

№	Входные данные	Выходные данные
1	Alpha Beta alpha Z z, b. 1 alpha	z
2	a. 0	a

Словари

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

Объединение подобных элементов#45254

Дан двумерный массив целых чисел, items1 и items2, представляющие собой два множества элементов. Каждый из данных массивов обладает следующими свойствами:

items[i] = [value_i, weight_i], где value_i обозначает значение, а weight_i обозначает вес i^го элемента;
значение каждого элемента уникально.

Верните двумерный массив ret, где ret[i] = [value_i, weight_i], в котором weight_i является суммой весов всех значений value_i.
Массив ret должен быть отсортирован по возрастанию по значению value.

Входные данные
Программа получает на вход в первой строке целое число n1 - количество элементов в массиве items1. Далее следуют n1 строк, в каждой из которых записаны два целых числа value_i, weight_i- элементы первого массива и их веса.
В следующей строке записано целое число n2 - количество элементов в массиве items2. Далее следуют n2 строк, в каждой из которых записаны два целых числа value_i, weight_i- элементы второго массива и их веса.

Ограничения на входные данные:

1 <= n1, n2 <= 1000
items1[i].len() == items2[i].len() == 2
1 <= value_i, weight_i <= 1000
Каждое значение value_i в items1 уникально.
Каждое значение value_i в items2 уникально.

Выходные данные
Выведите массив ret в требуемом формате (см. пример)

Примеры

№	Входные данные	Выходные данные
1	3 1 1 4 5 3 8 2 3 1 1 5	[[1, 6], [3, 9], [4, 5]]
2	3 1 1 3 2 2 3 3 2 1 3 2 1 3	[[1, 4], [2, 4], [3, 4]]

Словари

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

МОШ и числа#44659

На заключительный этап МОШ по информатике в 2023 году пришло N участников. Так получилось, что у каждого ребенка на каком либо из предметов одежды было записано одно число. При регистрации, один из организаторов решил записать все эти числа. Позже выяснилось, что каким-то чудесным образом, все участники зарегистрировались в порядке неубывания этих чисел на одежде.

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

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

В первой строке входного файла содержится единственное число N (0 <= N <= 10⁵) — количество участников заключительного этапа. В следующей строке находятся N упорядоченных по неубыванию неотрицательных целых чисел, не превосходящих 10⁹ и разделенных пробелами — числа, записанные у участников на одежде. В третьей строке файла записано число M (1<=M<=100000) — количество чисел, информацию о которых хотят узнать судьи. В четвертой строке через пробел записаны M целых неотрицательных чисел (не превышающих 10⁹+1).

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

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

Бинарный поиск в массиве Словари

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