# e-olymp 8515. Homo or Hetero?

Consider a list of numbers with two operations:
$\cdot$ insert number— adds the specified number to the end of the list.
$\cdot$ delete number— removes the first occurrence of the specified number from the list. If the list does not contain the number specified, no changes are performed.

For example: the result of the insertion of a number $4$ to the list $[1,2,1]$ is the list $[1,2,1,4]$. If we delete the number $1$ from this list, we get the list $[2,1,4]$, but if we delete the number $3$ from the list $[1,2,1,4]$,the list stays unchanged.

The list is homogeneous if it contains at least two equal numbers and the list is heterogeneous if it contains at least two different numbers. For example: the list $[2,2]$ is homogeneous, the list $[2,1,4]$ is heterogeneous, the list $[1,2,1,4]$ is both, and the empty list is neither homogeneous, nor heterogeneous.

Write a program that handles a number of the operations insert and delete on the empty list and determines list’s homogeneity and heterogeneity after each operation.

# Input

The first line of the input file contains an integer number $N$ $(1 \leq N \leq 10^{5})$ — the number of operations to handle. Following $N$ lines contain one operation description each. The operation description consists of a word “insert” or “delete”, followed by an integer number $K$ $(-10^{9} \leq K \leq 10^{9})$ — the operation argument.

# Output

For each operation output a line, containing a single word, describing the state of the list after the operation:

$\cdot$ “both” — if the list is both homogeneous and heterogeneous.
$\cdot$ “homo” — if the list is homogeneous, but not heterogeneous.
$\cdot$ “hetero” — if the list is heterogeneous, but not homogeneous.
$\cdot$ “neither” — if the list is neither homogeneous nor heterogeneous.

# Tests

# Input Output
1 11
$insert$ 1
$insert$ 2
$insert$ 1
$insert$ 4
$delete$ 1
$delete$ 3
$delete$ 2
$delete$ 1
$insert$ 4
$delete$ 4
$delete$ 4
$neither$
$hetero$
$both$
$both$
$hetero$
$hetero$
$hetero$
$neither$
$homo$
$neither$
$neither$
2 15
$insert$ -50
$insert$ -2
$insert$ 1
$insert$ 4
$delete$ 1
$delete$ 3
$delete$ -2
$delete$ -50
$insert$ 4
$delete$ 4
$delete$ 4
$insert$ 100
$insert$ -150
$delete$ -150
$delete$ 100
$neither$
$hetero$
$hetero$
$hetero$
$hetero$
$hetero$
$hetero$
$neither$
$homo$
$neither$
$neither$
$neither$
$hetero$
$neither$
$neither$

# Solution

Let’s memorize two numbers on each step: how many of different numbers and different pairs of identical numbers in a one-dimensional array. If there are more than one different numbers in the array and more than zero different pairs of the same numbers, then print "both". If the sum of different numbers in the array is less than two and different pairs of identical numbers are more than zero, then we enter "homo". If there are more than one different numbers in the array and less than one different pairs of the same numbers, then enter "hetero". In other cases, we enter "neither". In the last case, when an array is $0$ numbers or $1$ number.

# Задача

Профессор из тридевятого царства решил, что посчитать сумму делителей числа $n$ до $10^{10}$ сможет любой троечник, поэтому усложнил для Кости задачу, дав числа с большим количеством цифр. Но наш герой не хотел сдаваться, уж больно он хотел стать отличником.
Костя очень просит Вас помочь ему в этом деле, ведь он помнит, как успешно Вы справились с предыдущей задачей.

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

Одно целое число $n \left(1 \leqslant n < 10^{15}\right).$

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

Выведите сумму делителей числа $n.$

# Тесты

 Входные данные Выходные данные $100000000000031$ $100000000000032$ $10000019$ $10000020$ $400001520001444$ $700002730002667$ $9$ $13$ $304250263527210$ $1281001468723200$ $94083986096100$ $457766517350961$ $1234567898765$ $1517681442816$ $100000000000000$ $249992370597277$ $562949953421312$ $1125899906842623$ $81795$ $161280$ $9999999999999$ $14903272088640$ $997$ $998$ $1325$ $1674$ $2468013$ $3290688$ $951641320$ $2447078400$ $71675429738641$ $71695352830464$ $1100000000033$ $1200000000048$ $6300088$ $11859480$ $98$ $171$ $9102837465$ $15799834440$

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right). Доказательство. Рассмотрим произведение: \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right) Если раскрыть скобки, то получим сумму членов ряда: p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k}, где 0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right) Но такие члены являются делителями n, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей n, т.е. равно \sigma\left(n\right). Итак, \sigma\left(n\right) можно вычислить по нашей формуле. С другой стороны, каждая сумма 1 + p_m + p_m^2+\ldots+p_m^{\alpha_m} является суммой геометрической прогрессии с первым членом 1 и знаменателем p_m. Поэтому иначе данную формулу можно переписать так:$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$Для того, чтобы не вычислять p_k^{\alpha_k+1}, перепишем данную формулу в следующем виде:$$\sigma\left(n\right) = \left(\frac{p_1^{\alpha_1}-1}{p_1-1}+p_1^{\alpha_1}\right)\cdot\left(\frac{p_2^{\alpha_2}-1}{p_2-1}+p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(\frac{p_k^{\alpha_k}-1}{p_k-1}+p_k^{\alpha_k}\right).$$# Ссылки Код решения # Сумма делителей # Задача Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу: Найти сумму делителей данного числа n. Костя обратился к Вам как к опытному программисту, который знает алгебру, с просьбой о помощи решить данную задачу. # Входные данные Одно целое число n \left(1 \leqslant n < 10^{10}\right). # Выходные данные Выведите сумму делителей числа n. # Тесты  Входные данные Выходные данные 12 28 239 240 1234 1854 6 12 1000000007 1000000008 44100 160797 223092870 836075520 2147483648 4294967295 678906 1471002 1111111 1116000 9876543210 27278469036 99460729 99470703 5988 14000 1 1 1348781387 1617960960 135792 406224 5402250 17041284 375844500 1259767236 1000000000 2497558338 2357947691 2593742460 # Код программы # Решение задачи Пусть n имеет каноническое разложение n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k}, где p_1 < p_2 < \ldots <p_k — простые делители числа n, \alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}. Тогда сумма натуральных делителей числа n равна \sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$

Код решения

# Задача

На доске выписаны $n$ целых чисел. Все они пронумерованы от $1$ до $n.$ Разрешается выбрать два произвольных числа, вытереть оба с доски и написать новое число, равное их среднему арифметическому. Новое число получает номер $n + 1.$ После этого снова выбираются два числа и вместо них записывается их среднее арифметическое, которому дается номер $n + 2$ и т.д. Так продолжается до тех пор, пока на доске не останется только одно число. Чем больше будет это число, тем более успешной считается последовательность действий.

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

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

В первой строке записано целое число $n$ $(1 \leqslant n \leqslant 10^5).$ Во второй строке задаются $n$ целых чисел, которые были первоначально записаны на доске. Все числа лежат в диапазоне от $-10000$ до $10000.$

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

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

## Тесты

 Входные данные Выходные данные $3$ $7\;2\;4$ $2\;3$ $1\;4$ $4$ $6\;2\;7\;1$ $2\;4$$1\;5$$3\;6$ $4$ $12\;4\;7\;2$ $2\;4$$3\;5$$1\;6$ $5$$234\;2\;5\;54\;5 2\;3$$5\;6$$4\;7$$1\;8$

## Решение задачи

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

## Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

# Задача

Найдите сумму значений функции
$$f \left(x \right ) = x + \frac{1}{x}$$
в нескольких целых точках.

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

В первой строке задано количество точек $n$ $\left (1 \leqslant n \leqslant 50 \right ).$ В следующей строке заданы $n$ целых чисел $x_1, x_2, …, x_n$ — точки, значения функции в которых нужно просуммировать $\left (0 \leqslant \left |x_i \right | \leqslant 10^9 \right ).$

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

Выведите одно число — сумму значений функции $f \left(x \right )$ в заданных точках. Ответ считается правильным, если абсолютная или относительная погрешность не превышает $10^{-9}.$

# Тесты

 Входные данные Выходные данные $3$ $7.833333333333333$ $1 \ 2 \ 3$ $2$ $0$ $1 \ -1$ $5$ $4.265140415140415$ $10 \ -13 \ 21 \ -18 \ 4$ $1$ $10.1$ $10$

# Решение задачи

Мы просто суммируем значения функции в каждой точке. Тут использовали тип long double для точек и значений функции для меньшей погрешности.

# Задача

Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную $i$. В начальный момент Черный Ящик пустой, переменная $i$ равна $0$. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:
ADD(x): добавить элемент x в Черный Ящик;
GET: увеличить $i$ на $1$ и вывести $i$-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.
Помните, что $i$-ый минимальный элемент находится на $i$-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.
Рассмотрим работу черного ящика на примере:

 № Транзакция $i$ Содержимое Черного Ящика после транзакции Ответ 1 ADD(3) 0 3 2 GET 1 3 3 3 ADD(1) 1 1, 3 4 GET 2 1, 3 3 5 ADD(-4) 2 -4, 1, 3 6 ADD(2) 2 -4, 1, 2, 3 7 ADD(8) 2 -4, 1, 2, 3, 8 8 ADD(-1000) 2 -1000, -4, 1, 2, 3, 8 9 GET 3 -1000, -4, 1, 2, 3, 8 1 10 GET 4 -1000, -4, 1, 2, 3, 8 2 11 ADD(2) 4 -1000, -4, 1, 2, 2, 3, 8

Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно $30000$ (каждого типа).
Опишем последовательность транзакций двумя целочисленными массивами:

1. $A_1, \ A_2, \ldots , \ A_m:$ последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие $2 000 000 000$, $m \leq 30000$. Для выше описанного примера $A = \left (3, 1, -4, 2, 8, -1000, 2 \right).$
2. $u_1, \ u_2, \ldots , \ u_n:$ последовательность указывает на количество элементов в Черном Ящике в момент выполнения первой, второй, … $n$-ой транзакции GET. Для выше описанного примера $u = \left (1, 2, 6, 6 \right ).$

Работа Черного Ящика предполагает, что числа в последовательности $u_1, \ u_2, \ldots , \ u_n$ отсортированы в неубывающем порядке, $n \leq m$, а для каждого $p \left (1 \leq p \leq n \right )$ имеет место неравенство $p \leq u(p) \leq m$. Это следует из того, что для $p$-го элемента последовательности $u$ мы выполняем GET транзакцию, которая выводит $p$-ый минимальный элемент из набора чисел $A_1, \ A_2, \ldots , \ A_{u_p}$.

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

Состоит из следующего набора чисел: $m, \ n, \ A_1, \ A_2, \ldots , \ A_m, \ u_1, \ u_2, \ldots , \ u_n.$ Все числа разделены пробелами и (или) символом перевода на новую строку.

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

Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.

## Тесты

 Входные данные Выходные данные 7 4 3 1 -4 2 8 -1000 2 1 2 6 6 3 3 1 2 8 3 5 8 3 7 3 5 7 0 2 3 3 5 5 8 10 4 6 3 7 3 8 4 7 4 6 15 4 6 8 9 3 3 4 4 5 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 11 5 4 6 8 9 5 3 6 8 10 12 13 6 7 8 9 10 3 4 5 6 6

## Решение задачи

Пусть nums — множество всех элементов последовательности $A_n$. blackBox — мультимножество, представляющее собой описанный в задаче Черный Ящик на $i$-ом запросе. Изначально blackBox содержит «бесконечность» для избежания выхода за пределы. it — итератор, указывающий на $i$-ый минимальный элемент blackBox. Изначально данный итератор указывает на первый элемент множества. На $i$-ом запросе в blackBox копируются элементы массива nums от $u_{i-1}-1$-го до $u_{i}-1$-го (примем, что $u_0$ = 0). Тогда при добавлении в blackBox элемента, меньшего, чем тот, на который в данный момент указывает итератор it — $min_i$, $i$-ым минимальным элементом, становится элемент, предшествующий $min_i$. После выполнения ответа на $i$-ый запрос итератор должен указывать на $i+1$-ый минимальный элемент, то есть на элемент, следующий за $min_i$.

# Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

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

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

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

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

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

# Тесты

 Входные данные Выходные данные $6$ $9$ $3$ $1\, 3\, 2$ $2$ $2\, 3$ $2$ $5$ $2$ $3\, 2$ $2$ $2\, 3$ $5$ $41$ $4$ $84\, 50\, 50\ 8$ $2$ $1\, 21$ $100$ $100$ $2$ $1\, 50$ $4$ $1\, 2\, 3\, 4$

# Решение задачи

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
Найдем теперь общее минимальное время работы роботов, требуемое для завершения обработки всех деталей. Пусть нам уже известно, за какое время обрабатывают роботы первого типа каждую из данных деталей. Очевидно, что если возможно выполнить работу за $t$, то возможно выполнить работу и за $t+1$, а также, если невозможно выполнить работу за $t$, то невозможно выполнить работу за $t-1$. Следовательно, для решения данной задачи можно применить бинарный поиск по ответу. Применим бинарный поиск по ответу, рассматривая детали по мере их поступления с конца: роботы могут выполнить работу за $T$, если для каждой детали существует такой робот второго типа, который выполнит работу за $T_{2}$, такое, что $T_{1}+T_{2}$ $\leqslant T$, где $T_{1}$ – время, за которое эту деталь выполнит робот первого типа.
Теперь оценим сложность работы алгоритма. Бинарный поиск работает за $O(\log n)$. Для каждого этапа бинарного поиска мы обрабатываем $n$ деталей. Далее для каждой из $n$ деталей работает логарифмическая вставка в мультисет. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log^2n)$.

# Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

# e-olymp 1868. Функция

Условие задачи
Вычислите функцию:

$f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}$

Входные данные
Одно натуральное число $n \;$ $(1 \leq n \leq 10^{12})$.

Выходные данные
Значение $f(n)$, взятое по модулю $2^{32}$.

# e-olymp 1072. Химические реакции

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится формула — левая часть уравнения, во второй- одно число $N (1 \leq N \leq 10)$ — количество рассматриваемых правых частей, в каждой из последующих $N$ строк — одна формула — предполагаемая правая часть уравнения.

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

(Примечание: понятие формулы в данном алфавите можно прочитать по ссылке выше.)

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

Для каждой из $N$ заданных строк вывести одну строку вида

формула левой части==формула правой части

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

формула левой части!=формула правой части

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

Решение (вспомогательные функции)

Так как задача достаточно объемная, напишем ряд вспомогательных функций:

1. Определяет, является ли символ цифрой.
2. Определяет, является ли символ буквой в верхнем регистре.
3. Определяет, является ли символ буквой в нижнем регистре.
4. Будем хранить содержимое формулы используя структуру map (карта), ключами будут выступать названия элементов (строки), значениями — количества их вхождений. Если элемента в карте нет, добавляем пару <элемент, кол-во>, иначе — прибавляем к старом числу вхождений новое. За это отвечает следующая функция.
5. Для простоты разобьем формулу на подформулы (по знаку $+$, если он встречается), и будем работать с каждой формулой по отдельности. Функция разбивает строку на подстроки по знаку $+$ и заполняет ими вектор $storage$ (так как мы не знаем кол-во подформул заранее, вектор предпочтительнее массива).
6. По условию, перед каждой подформулой может идти множитель, относящейся ко всей подформуле. Функция возвращает множитель ( $1$, если множитель не записан явно).
7. Основная функция. Добавляет в карту $content$ содержимое подформулы.
8. Обрабатывает формулу. Просто вызывает функции №$6$ и №$7$ по очереди для каждой из подформул (элементов из $subformulas$).

Решение (основной алгоритм)

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

Тут:

1. $formula$ — подформула обрабатываемой формулы (без общего множителя);
2. $multiplier$ — множитель, определяется предыдущей функцией, перед вызовом данной;
3. $content$ — карта, куда записываются элементы всех подформул текущей формулы (доступ осуществляется по адресу).

Алгоритм разделяется на 2 случая, в зависимости от наличия скобок. Предположим, скобок в подформуле (далее — просто формуле) нет. Заведем переменные $name$ (название элемента. тип string) и $coefficient$ (задний коэффициент, тип string). Тогда, проходя по порядку по символам формулы, будем выполнять следующие действия в зависимости от текущего символа($c$):

1. $c$ — цифра: добавляем его в конец строки $coefficient$;
2. $c$ — буква в нижнем регистре: добавляем его в конец строки $name$;
3. $c$ —  буква в верхнем регистре: если строка $name$ — пустая (первый элемент в формуле), то добавляем его в конец строки $name$. Иначе, сперва обнуляем $name$, потом добавляем. Тогда, если строка $coefficient$ — пустая, присваиваем $coefficient=$»$1$». Получаем количество вхождений элемента как $multiplier*stoi(coefficient)$, где stoi() — стандартная функция, преобразующая число к строке. Затем добавляем в карту элемент и полученное кол-во вхождений.

(Примечание: пункт $3$ для последнего элемента (кроме обновления значения $name$) придется повторить отдельно.)

Если же в формуле имеются скобки, то:

1. Находим первую открывающую скобку.
2. Находим соответствующую ей закрывающую скобку.
3. Для выражения в скобках вычисляем задний коэффициент (см. код), заносим в переменную $newMultiplier$ значение множителя для выражения внутри скобок.
4. Рекурсивно вызываем функцию getContent() для:
1. Выражения перед открывающей скобкой, если формула не начинается с нее.

($begin$ — номер первого символа внутри скобок.)
2. Выражения внутри скобок.

($end$ — номер закрывающей скобки.)
3. Выражения после закрывающей скобки или заднего коэффициента, если присутствует (если только скобка/коэффициент не является концом формулы).

($afterEnd$ — следующий после скобки/коэффициента символ.)

Этот алгоритм фактически является решением задачи. Теперь в методе $main$ надо всего лишь обработать главную формулу, а затем для каждого случая в цикле — сравниваемую с ней формулу, сравнив после содержимое их карт (сравнение осуществляется просто используя оператор сравнения ==). Обработка подразумевает последовательный вызов функций  split() и  process().

Тесты

 № Ввод Вывод 1 C2H5OH+3O2+3(SiO2) 6 2CO2+3H2O+3SiO2 2C+6H+13O+3Si 99C2H5OH+3SiO2 3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)+Ge 3(Si(O)2)+2CO+3H2O+O2 C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2 C2H5OH+3O2+3(SiO2)==2C+6H+13O+3Si C2H5OH+3O2+3(SiO2)!=99C2H5OH+3SiO2 C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)!=C2H5OH+3O2+3(SiO2)+Ge C2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2 2 2H2O 5 HHOHHO 2H+H2+(O(O)) 2((H2)O) HOHHOHe H4O 2H2O==HHOHHO 2H2O==2H+H2+(O(O)) 2H2O==2((H2)O) 2H2O!=HOHHOHe 2H2O!=H4O 3 8Zn+Ar4+Ne 3 Ne(Ar2(Zn)4)2 2Ne(Ar2(Zn)4) Ne+2Zn2(((((Ar)))))2Zn2 8Zn+Ar4+Ne==Ne(Ar2(Zn)4)2 8Zn+Ar4+Ne!=2Ne(Ar2(Zn)4) 8Zn+Ar4+Ne==Ne+2Zn2(((((Ar)))))2Zn2

Код

Ссылки

Засчитанное решение на e-olymp.

Код на ideaone.

# acm.timus.ru №2002. Тестовое задание

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

 Время: 0.5 секунды Память 64 Мб

### Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…
Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!
Мы рассмотрели вашу заявку на вакансию разработчика программного обеспечения и были заинтересованы вашей кандидатурой. Для оценки ваших профессиональных навыков мы предлагаем вам выполнить несложное тестовое задание: необходимо реализовать систему регистрации для форума. Она должна поддерживать три операции:
1. «register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
2. «login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
3. «logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».
Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!
И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

### Исходные данные

В первой строке дано целое число $n$ — количество операций $1\leq{n}\leq100$. В каждой из следующих $n$ строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

### Результат

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

### Пример

 Исходные данные Результат 6 register vasya 12345 login vasya 1234 login vasya 12345 login anakin C-3PO logout vasya logout vasya success: new user added fail: incorrect password success: user logged in fail: no such user success: user logged out fail: already logged out

### Решение

Для решения данной задачи нам необходимо воспользоваться структурой данных, которая хранит в себе пары вида «ключ — значение», а также структурой, которая будет хранить в себе некоторое множество. Воспользуемся структурами HashMap (Java) / map (C++) (key -> value)  и HashSet  (множество).

Рассмотрим операции, которые должна уметь обрабатывать наша система:

1. «register username password». При регистрации нового пользователя будем помещать его в нашу «базу» зарегистрированных пользователей при условии, что он не зарегистрирован. Поиском по ключу в HashMap / map проверим существование уже зарегистрированного никнейма. Если найдётся такой пользователь, то система выдаст сообщение об ошибке.
2. «login user password». Если база пользователей содержит в себе логин пользователя, пароли совпадают и пользователь не в он-лайне, то система разрешит user’у вход на форум. В противном случае, с соответствующими сообщениями об ошибках, не разрешит вход. Отслеживать пользователей, которые уже online, будем с помощью HashSet. Если пользователя нет в базе пользователей, которые сейчас на сайте, то открывая доступ, система поместит его в базу-online. Тогда новый запрос login с этого ника будет отклонён.
3. «logout name». Если пользователя нет в базе пользователей, то его logout невозможен. Иначе, если его нет в базе-online, то тоже система выдаст сообщение об ошибке. Если user есть в базе пользователей и находится в онлайне, то выход возможен. Во время logouta удаляем пользователя из базы-online.

### Реализация

В данном отчёте задачи будут представлены на языках Java и C++. Опишем, для начала, какие классы и методы необходимо использовать для решения этой задачи на языке Java:

HashMap:

Будем использовать интерфейс Map, имплементация (реализация) — HashMap. Из интерфейса Map воспользуемся следующими методами:

• containsKey(Key K) — возвращает true, если ключ найден. В противном случае — false;
• put(Key K, Value V) — записывает пару ключ-значение в структуру;
• get(Key K) — по ключу возвращает значение.

HashSet:

Используем интерфейс Set, реализация — HashSet. Будем использовать следующие методы:

• contains(Object o) — возвращает true, если элемент принадлежит множеству. Иначе — false;
• add(Object o) — добавляет элемент во множество;
• remove(Object o) — удаляет элемент из множества.

Теперь для С++:

В С++ воспользуемся немного другим подходом. Воспользуемся только map. Создадим структуру, которая будет содержать 2 поля: пароль и статус. Воспользуемся следующими методами:

• find (K key) — возвращает итератор элемента.
• end() — возвращает итератор за последним элементом.

### set или без него?

Для данной задачи использование set’a не принципиально. Но если предположить, что, помимо запросов регистрации, входа и выхода, был бы ещё и запрос вывести пользователей, которые онлайн, преимущество использования set’a очевидно.

Код на Java:

Код на С++:

### Результаты

Обе реализации прошли все тесты на Тимусе с такими результатами:

 Язык Время работы Память С++ 0.015 412 КБ Java 0.124 1 804 КБ

Задача

Ideone (Java)

Ideone (C++)

Java (Set)

Java (Map)

C++ (map)

C++ (set)