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

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

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

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

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

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

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: Пересечение множеств

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

3
1 2 3
3
4 3 2

2 3

E: Кубики

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

Номер любого цвета — это целое число в пределах от 0 до 10⁹. В первой строке входного файла записаны числа N и M — количество кубиков у Ани и Бори соответственно. В следующих N строках заданы номера цветов кубиков Ани. В последних M строках номера цветов кубиков Бори.

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

4 3
0
1
10
9
1
3
0

2
0 1
2
9 10
1
3

F: Количество слов в тексте

Во входном файле (вы можете читать данные из файла input.txt) записан текст. Словом считается последовательность непробельных символов идущих подряд, слова разделены одним или большим числом пробелов или символами конца строки.

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

She sells sea shells on the sea shore;
The shells that she sells are sea shells I'm sure.
So if she sells sea shells on the sea shore,
I'm sure that the shells are sea shore shells.

19

G: Полиглоты

Каждый из \(N\) школьников некоторой школы знает \(M_i\) языков. Определите, какие языки знают все школьники и языки, которые знает хотя бы один из школьников.

Первая строка входных данных содержит количество школьников \(N\). Далее идет \(N\) чисел \(M_i\), после каждого из чисел идет \(M_i\) строк, содержищих названия языков, которые знает \(i\)-й школьник. Длина названий языков не превышает 1000 символов, количество различных языков не более 1000. \(1 \le N \le 1000\), \(1 \le M_i \le 500\).

3
3
Russian
English
Japanese
2
Russian
English
1
English

1
English
3
Russian
Japanese
English

H: Забастовки

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

\(i\)-я партия объявляет забастовки строго каждые \(b_i\) дней, начиная с дня с номером \(a_i\). То есть \(i\)-я партия объявляет забастовки в дни \(a_i\), \(a_i+b_i\), \(a_i+2b_i\) и т.д. Кроме того, если какая-либо чрезвычайно активная партия организует в течение года более 1000 забастовок, то правительство немедленно разгонит эту партию, поэтому ни одна партия не устраивает более 1000 забастовок в течение года.

Если в какой-то день несколько партий объявляет забастовку, то это считается одной общенациональной забастовкой.

В календаре страны \(N\) дней, пронумерованных от \(1\) до \(N\). Первый день года является понедельником, шестой и седьмой дни недели — выходные, неделя состоит из семи дней.

Программа получает на вход число дней в году \(N\) \((1\le N\le10^9)\) и число политических партий \(K\) \((1\le K\le1000)\). Далее идет \(K\) строк, описывающие графики проведения забастовок. \(i\)-я строка содержит числа \(a_i\) и \(b_i\) \((1\le a_i, b_i\le N)\).

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

19 3
2 3
3 5
9 8

8

1000000000 1
1 7

1000

Пояснение к примеру 1. Первая партия объявляет забастовки в дни 2, 5, 8, 11, 14, 17. Вторая партия объявляет забастовки в дни 3, 8, 13, 18. Третья партия — в дни 9 и 17. Дни номер 6, 7, 13, 14 являются выходными. Таким образом, общенациональные забастовки пройдут в дни 2, 3, 5, 8, 9, 11, 17, 18.

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

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

Август и Беатриса играют в игру. Август загадал натуральное число от 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

J: Угадай число - 2

Август и Беатриса продолжают играть в игру, но Август начал жульничать. На каждый из вопросов Беатрисы он выбирает такой вариант ответа YES или NO, чтобы множество возможных задуманных чисел оставалось как можно больше. Например, если Август задумал число от 1 до 5, а Беатриса спросила про числа 1 и 2, то Август ответит NO, а если Беатриса спросит про 1, 2, 3, то Август ответит YES.

Если же Бетриса в своем вопросе перечисляет ровно половину из задуманных чисел, то Август из вредности всегда отвечает NO.

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

Вам дана последовательность вопросов Беатрисы. Приведите ответы Августа на них.

Формат входных данных аналогичен предыдущей задаче, но во входных данных отсутствуют ответы Августа.

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

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

NO
YES
6 8 10

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

Поскольку тип 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

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

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

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

M: Номер появления слова

Во входном файле (вы можете читать данные из файла input.txt) записан текст. Словом считается последовательность непробельных символов идущих подряд, слова разделены одним или большим числом пробелов или символами конца строки.

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

one two one two three

0 0 1 1 0

She sells sea shells on the sea shore;
The shells that she sells are sea shells I'm sure.
So if she sells sea shells on the sea shore,
I'm sure that the shells are sea shore shells.

0 0 0 0 0 0 1 0 0 1 0 0 1 0 2 2 0 0 0 0 1 2 3 3 1 1 4 0 1 0 1 2 4 1 5 0 0

N: Словарь синонимов

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

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

Программа должна вывести синоним к данному слову.

3
Hello Hi
Bye Goodbye
List Array
Goodbye

Bye

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

O: Выборы в США

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

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

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

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

McCain 10
McCain 5
Obama 9
Obama 8
McCain 1

McCain 16
Obama 17

Ivanov 1

Ivanov 1

P: Функция

Вычислите функцию: \[ 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.

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

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

apple orange banana banana orange

banana

R: Права доступа

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

• запись W,
• чтение R,
• запуск X.

Вам требуется восстановить контроль над правами доступа к файлам (ваша программа для каждого запроса должна будет возвращать OK если над файлом выполняется допустимая операция, или же Access denied, если операция недопустима.

В первой строке входного файла содержится число \(N\) (\(1 \le N \le 10000\)) —количество файлов содержащихся в данной файловой системе.

В следующих \(N\) строчках содержатся имена файлов и допустимых с ними операций, разделенные пробелами. Длина имени файла не превышает 15 символов.

Далее указано чиcло \(M\) (\(1 \le M \le 50000\)) — количество запросов к файлам.

В последних \(M\) строках указан запрос вида Операция Файл. К одному и тому же файлу может быть применено любое колличество запросов.

Для каждого из \(M\) запросов нужно вывести в отдельной строке Access denied или OK.

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

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

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

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 — самому слову. Тогда стандартная сортировка будет сортировать список пар, при этом пары сравниваются по первому элементу, а если они равны — то по второму. Это почти то, что требуется в задаче.

T: Страны и города

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

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

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

2
Russia Moscow Petersburg Novgorod Kaluga
Ukraine Kiev Donetsk Odessa
3
Odessa
Moscow
Novgorod

Ukraine
Russia
Russia

U: Банковские счета

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

1. Пополнение счета клиента.
2. Снятие денег со счета.
3. Запрос остатка средств на счете.
4. Перевод денег между счетами клиентов.
5. Начисление процентов всем клиентам.

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

Входной файл содержит последовательность операций. Возможны следующие операции:

DEPOSIT name sum - зачислить сумму sum на счет клиента name. Если у клиента нет счета, то счет создается.

WITHDRAW name sum - снять сумму sum со счета клиента name. Если у клиента нет счета, то счет создается.

BALANCE name - узнать остаток средств на счету клиента name.

TRANSFER name1 name2 sum - перевести сумму sum со счета клиента name1 на счет клиента name2. Если у какого-либо клиента нет счета, то ему создается счет.

INCOME p - начислить всем клиентам, у которых открыты счета, p% от суммы счета. Проценты начисляются только клиентам с положительным остатком на счету, если у клиента остаток отрицательный, то его счет не меняется. После начисления процентов сумма на счету остается целой, то есть начисляется только целое число денежных единиц. Дробная часть начисленных процентов отбрасывается.

Для каждого запроса BALANCE программа должна вывести остаток на счету данного клиента. Если же у клиента с запрашиваемым именем не открыт счет в банке, выведите ERROR.

DEPOSIT Ivanov 100
INCOME 5
BALANCE Ivanov
TRANSFER Ivanov Petrov 50
WITHDRAW Petrov 100
BALANCE Petrov
BALANCE Sidorov

105
-50
ERROR

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

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

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

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

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

В первой строке содержится единственное целое число 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

W: Контрольная по ударениям

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

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

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

Вводится сначала число N — количество слов в словаре (0≤N≤20000).

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

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выведите количество ошибок в Петином тексте, которые найдет Вася.

4
cAnnot
cannOt
fOund
pAge
thE pAge cAnnot be fouNd

2

4
cAnnot
cannOt
fOund
pAge
The PAGE cannot be found

4

X: Продажи

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

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

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

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

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

Y: Выборы в США - 2

На этот раз вам известно число выборщиков от каждого штата США и результаты голосования каждого гражданина США (а также в каком штате проживает данный гражданин).

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

Первая строка входных данных содержит количество штатов в США N. Далее идет N строк, описывающих штаты США, каждая строка состоит из названия штата и числа выборщиков от этого штата. Далее до конца файла идут записи результатов голосования по каждому из участников голосования. Одна строка соответствует одному избирателю. Записи имеют вид: название штата, имя кандидата, за которого проголосовал данный избиратель. Названия штатов и имена кандидатов не содержат пробелов.

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

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

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

2
Florida 25
Pennsylvania 23
Florida Gore
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Pennsylvania Bush
Florida Gore
Pennsylvania Gore
Florida Bush
Pennsylvania Gore
Florida Bush
Pennsylvania Gore

Bush 25
Gore 23

3
Florida 5
Pennsylvania 4
Alaska 3
Florida Gore
Pennsylvania Obama
Pennsylvania Clinton
Alaska Bush

Gore 5
Clinton 4
Bush 3
Obama 0

Z: Снеговики

Для того, чтобы слепить снеговика, необходимо три снежных кома разного размера. В вашем распоряжении есть \(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

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

Фирма 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

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

В магазине проходит новогодняя распродажа — цены всех товаров снижены на 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

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