Замечания по вводу-выводу

Во всех упражнениях этого листка ввод-вывод может быть как стандартным, так и файловым (input.txt/output.txt).

Некоторые задания на использование словарей должны быть выполнены на языке Python.

Упражнения на set

A: Количество различных чисел

Дана массив чисел. Определите, сколько в нём встречается различных чисел.

В первой строке входного файла записано количество чисел в массиве \(N\), \(1\le N\le 10^5\). Вторая строка содержит \(N\) целых положительных чисел не превосходящих \(10^9\), записанных через пробел.

Программа должна вывести единственное число — количество различных встречающихся чисел среди данных.

5
1 2 3 2 1

3

B: Встречалось ли число раньше

Дан массив чисел, как в предыдущей задаче. Для каждого числа выведите слово YES (в отдельной строке), если это число ранее встречалось в массиве, или NO, если не встречалось.

6
1 2 3 2 3 4

NO
NO
NO
YES
YES
NO

C: Разность множеств

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

3
1 3 2
3
2 4 3

1

D: Угадай число

Август и Беатриса играют в игру. Август загадал натуральное число от 1 до \(N\). Беатриса пытается угадать это число, для этого она называет некоторые множества натуральных чисел. Август отвечает Беатрисе YES, если среди названных ей чисел есть задуманное или NO в противном случае. После нескольких заданныъх вопросов Беатриса запуталась в том, какие вопросы она задавала и какие ответы получила и просит вас помочь ей определить, какие числа мог задумать Август.

Первая строка входных данных содержит число \(N\) — наибольшее число, которое мог загадать Август и число \(K\) — количество вопросов Беатрисы. Далее идет \(3K\) строк, содержащие вопросы Беатрисы и ответы Августа на них. Для каждого вопроса сначала задается количество чисел в этом вопросе, затем — сами числа. В третьей строке каждого вопроса записан ответ Августа: YES или NO.

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

10 2
5
1 2 3 4 5
YES
5
2 4 6 8 10
NO

1 3 5

E: Очередь с приоритетами

Поскольку тип set хранится упорядоченным, а операции с ним выполняются за логарифм, то можно использовать тип set для реализации очереди с приоритетами. То есть нужно составить set из приоритетов элементов. Рассмотрим две типичные операции над очередью с приоритетами:

1. Нужно узнать элемент с наибольшим (наименьшим) приоритетом. То есть set должен хранить информацию не только о приоритетах элементов, но и о самих элементах (например, их номера). Для этого сделаем элементами set не приоритеты элементов, а пары значений (приоритет, номер), то есть множество будет хранить информацию как о приоритетах, так и о самих элементах.

Для представления пары элементов в STL есть шаблон pair с двумя параметрами: типами элементов в паре. Например, чтобы создать “пару” элементов типа int можно использовать такое объявление:

pair <int, int> P;

А объявить множество элементов, каждый из которых является парой, можно делать так:

set <pair <int, int> > S;

У объекта типа pair есть два поля: first и second, которые соответствуют первому и второму элементу пары. То есть доступ к элементам пары можно получить так: P.first и P.second.

Для создания объектов типа pair можно использовать более компактную функцию make_pair(a, b), которая возвращает объект типа pair, у которого поле first равно a, а поле second равно b.

Объекты типа pair можно сравнивать, при этом сравнение сначала осуществляется по полю first, а если они равны, то сравнивается поле second.

Таким образом, для реализации очереди с приоритетами нужно сделать set типа pair <int, int>, где поле first будет равно приоритету элемента, а поле second — его номеру.

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

Постановка задачи

Используя описанную выше технологию реализуйте очередь с приоритетами.

Программа получает на вход количество операций с очередь \(n\le 10^5\). Далее идет \(n\) строк, каждая из которых содержит одну из следующих команд:

ADD p. Эта команда добавляет в очередь новый элемент с приоритетом p. Добавляемый элемент в очередь получает порядковый номер, номера выдаются подряд начиная с 1. Программа выводит номер этого элемента (т.е. первая команда ADD выводит 1, следующая 2 и т.д.).

CHANGE n p. Приоритет элемента с номером n необходимо изменить на p. Программа выводит новый приоритет данного элемента. Гарантируется, что элемент с номером n содержится в очереди.

MIN. Программа удаляет из очереди элемент с наименьшим приоритетом. Если таких несколько, то удаляется элемент с наименьшим номером. Программа выводит два числа: номер удаленного элемента и его приоритет. Гарантируется, что очередь непуста.

MAX. Программа удаляет из очереди элемент с наибольшим приоритетом. Если таких несколько, то удаляется элемент с наибольшим номером. Программа выводит два числа: номер удаленного элемента и его приоритет. Гарантируется, что очередь непуста.

5
ADD 3
ADD 5
CHANGE 2 -3
MAX
MIN

1
2
2
1 3
2 2

F: Приближенный поиск

Создайте структуру данных, которая поддерживает следующие операции:

1. Добавнение числа x в множество. Если такой элемент уже есть в множестве, то новый элемент не добавляется.
2. Удаление числа x из множества. Если такого числа нет, то удаляется ближайший к нему элемент множества. Если существует два равных ближайших элемента, то удаляется меньший из них.

Программа получает на вход количество элементов \(N\le10^5\). Далее следует \(N\) строк с описанием операции. Каждая строка имеет вид ADD x или DEL x, где x — число, не превосходящее по модулю \(10^9\). Гарантируется, что если дана операция DEL x, то множество непусто.

Для каждой операции типа DEL программа должна вывести значение удаленного элемента.

6
ADD 7
ADD 10
DEL 8
ADD 1
DEL 8
DEL 2

7
10
1

Упражнения на map

G: Функция

Вычислите функцию: \[ f(n) = \begin{cases} 1 & \text{если } n \le 2\\ f(\lfloor6 n / 7\rfloor) + f(\lfloor2 n / 3\rfloor)&\text{если } n \bmod 2 = 1\\ f(n - 1) + f(n - 3)&\text{если } n \bmod 2 = 0\\ \end{cases} \]

Программа получает на вход натуральное число \(n\le 10^{18}\).

Программа должна вывести \(f(n)\bmod 2^{32}\).

7

10

Указание. Чтобы найти ответ по модулю \(2^{32}\), нужно все вычисления выполнять с использованием 32-битного типа unsigned int.

H: Самое частое слово

Дан текст. Выведите слово, которое в этом тексте встречается чаще всего. Если таких слов несколько, выведите то, которое меньше в лексикографическом порядке.

apple orange banana banana orange

banana

I: Частотный анализ

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

hi
hi
what is your name
my name is bond
james bond
my name is damme
van damme
claude van damme
jean claude van damme

damme
is
name
van
bond
claude
hi
my
james
jean
what
your

Указание. После того, как вы создадите словарь всех слов, вам захочется отсортировать его по частоте встречаемости слова. Желаемого можно добиться, если создать вектор, типа pair <int, string>, где поле first будет равно частоте появления слова, а поле second — самому слову. Тогда стандартная сортировка будет сортировать список пар, при этом пары сравниваются по первому элементу, а если они равны — то по второму. Это почти то, что требуется в задаче.

J: Снеговики

Для того, чтобы слепить снеговика, необходимо три снежных кома разного размера. В вашем распоряжении есть \(n\) снежных комов, которые представляют собой шары с радиусами \(r_1\), \(r_2\), ..., \(r_n\). Снеговика можно слепить из любых трех комов, радиусы которых попарно различны. Например, из комов с радиусами 1, 2 и 3 можно слепить снеговика, а из комов с радиусами 2, 2, 3 или 2, 2, 2 —нельзя. Определите, какое наибольшее количество снеговиков можно слепить из данных комов.

В первой строке входных данных задано целое число \(n\) (\(1\le n\le 10^5\)) — количество комов. В следующей строке заданы \(n\) целых чисел — радиусы комов \(r_1\), \(r_2\), ..., \(r_n\) (\(1\le r_i\le 10^9\)). Радиусы комов могут совпадать.

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

7
1 2 3 4 5 6 7

2
3 2 1
6 5 4

3
2 2 3

0

K: Коммерческий калькулятор

Фирма OISAC выпустила новую версию калькулятора. Этот калькулятор берет с пользователя деньги за совершаемые арифметические операции. Стоимость каждой операции равна 5 % от числа, которое является результатом операции. На этом калькуляторе требуется вычислить сумму \(N\) натуральных чисел (числа известны). Нетрудно заметить, что от того, в каком порядке мы будем складывать эти числа, иногда зависит, в какую сумму денег нам обойдется вычисление суммы чисел (тем самым оказывается нарушен классический принцип “от перестановки мест слагаемых сумма не меняется”). Например, пусть нам нужно сложить числа 10, 11, 12 и 13. Тогда если мы сначала сложим 10 и 11 (это обойдется нам в 1.05 ₽), потом результат с 12 (1.65 ₽), и затем с 13 (2.3 ₽), то всего мы заплатим 5 ₽, если же сначала отдельно сложить 10 и 11 (1.05 ₽), потом 12 и 13 (1.25 ₽) и, наконец, сложить между собой два полученных числа (2.3 ₽), то в итоге мы заплатим лишь 4.6 ₽. Напишите программу, которая будет определять, за какую минимальную сумму денег можно найти сумму данных \(N\) чисел.

Первая строка входных данных содержит число \(N\) (\(2 \le N \le 10^5\)). Во второй строке заданы \(N\) натуральных чисел, каждое из которых не превосходит 10000.

Определите, сколько денег нам потребуется на нахождения суммы этих \(N\) чисел. Результат должен быть выведен абсолютно точно.

Используйте контейнер multiset для решения.

4
10 11 12 13

4.6

2
1 1

0.1

L: Распродажа

В магазине проходит новогодняя распродажа — цены всех товаров снижены на 25 %. Оказалось, что первоначально все цены делились на 4, поэтому после снижения цен все цены также выражаются целым числом.

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

Первая строка входных данных содержит общее количество ценников N, \(2 \le N \le 10^5\), \(N\) — чётное число. Далее записаны \(N\) целых положительных чисел, не превосходящих \(10^9\), идущих в порядке неубывания по одному в строке — числа, записанные на всех ценниках (как старых, так и новых). Гарантируется, что входные данные корректны, то есть решение существует.

Программа должна вывести \(N / 2\) целых чисел в порядке неубывания — стоимости товаров после понижения цен.

Задача должна быть решена с использованием контейнера multiset.

6
30 40 42 45 56 60

30 42 45

M: Англо-латинский словарь

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

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

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

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

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

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

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

3
apple - malum, pomum, popula
fruit - baca, bacca, popum
punishment - malum, multa

7
baca - fruit
bacca - fruit
malum - apple, punishment
multa - punishment
pomum - apple
popula - apple
popum - fruit

N: Продажи

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

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

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

Ivanov paper 10
Petrov pen 5
Ivanov marker 3
Ivanov paper 7
Petrov envelope 20
Ivanov envelope 5

Ivanov:
envelope 5
marker 3
paper 17
Petrov:
envelope 20
pen 5

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

O: Родословная: подсчет высоты (Python)

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

Каждом элементу дерева сопоставляется целое неотрицательное число, называемое высотой. У родоначальника высота равна 0, у любого другого элемента высота на 1 больше, чем у его родителя.

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

Программа получает на вход число элементов в генеалогическом древе \(N\). Далее следует \(N-1\) строка, задающие родителя для каждого элемента древа, кроме родоначальника. Каждая строка имеет вид имя_потомка имя_родителя.

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

Эта задача имеет решение сложности \(O(n)\), но вам достаточно написать решение сложности \(O(n^2)\) (не считая сложности обращения к элементам словаря).

Пример ниже соответствует приведенному древу рода Романовых.

9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I

Alexander_I 4
Alexei 1
Anna 1
Elizabeth 1
Nicholaus_I 4
Paul_I 3
Peter_I 0
Peter_II 2
Peter_III 2

P: Родословная: предки и потомки (Python)

Даны два элемента в дереве. Определите, является ли один из них потомком другого.

Программа получает на вход описание дерева, как в задаче W. Далее до конца файла идут строки, содержащие имена двух элементов дерева. Для каждого такого запроса выведите одно из трех чисел: 1, если первый элемент является предком второго, 2, если второй является предком первого или 0, если ни один из них не является предком другого.

9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
Anna Nicholaus_I
Peter_II Peter_I
Alexei Paul_I

1
2
0

Q: Родословная: LCA (Python)

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

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

По-английски такая задача называется lowest common ancestor (LCA).

9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I
Alexander_I Nicholaus_I
Peter_II Paul_I
Alexander_I Anna

Paul_I
Peter_I
Anna

R: Родословная: Число потомков (Python)

Для каждого элемента дерева определите число всех его потомков (не считая его самого).

Формат выходных данных совпадает с задачей W. Выведите список всех элементов в лексикографическом порядке, для каждого элемента выводите количество всех его потомков.

Решение должно иметь сложность \(O(N)\), не считая сложности обращения к элементам словаря и сортировки результата.

9
Alexei Peter_I
Anna Peter_I
Elizabeth Peter_I
Peter_II Alexei
Peter_III Anna
Paul_I Peter_III
Alexander_I Paul_I
Nicholaus_I Paul_I

Alexander_I 0
Alexei 1
Anna 4
Elizabeth 0
Nicholaus_I 0
Paul_I 2
Peter_I 8
Peter_II 0
Peter_III 3

ZZ: Ферзь

Доска в \(N\)-мерных шахматах представляет собой \(N\)-мерный куб размером \(S \times S \times \ldots \times S\) ячеек. Одна из угловых ячеек этого куба имеет координаты (\(1, 1, \ldots, 1\)), а ячейка в противоположном углу — координаты (\(S, S, \ldots, S\)). Ладья в \(N\)-мерных шахматах ходит, смещаясь на произвольное ненулевое количество ячеек по одной из своих координат. Слон в \(N\)-мерных шахматах ходит, смещаясь на произвольное ненулевое количество ячеек по всем \(N\) координатам одновременно, причём смещения по всем координатам должны быть равны по модулю. Ферзь в \(N\)-мерных шахматах может ходить и как ладья, и как слон. Ферзь находится на пустой шахматной доске в ячейке с координатами (\(C_1, C_2, \ldots, C_N\)). Определите количество различных ячеек, в которых он может оказаться через два хода.

Первая строка входных данных содержит целые числа \(N\) (\(1 \le N \le 5\)) и \(S\) (\(2 \le S \le 100\)). Вторая строка содержит \(N\) целых чисел \(C_i\) (\(1 \le C_i \le S\)).

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

3 3
1 2 3

27