e-olymp 8515. Homo or Hetero?

Task

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$

Code 1

Code 2 (map)

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.

Links

2 thoughts on “e-olymp 8515. Homo or Hetero?

  1. Операция count выполняется минимум за $O\left(\log n\right)$, так что если у Вас несколько ее вычислений подряд, разумно сохранить их в одну переменную, а не вычислять каждый раз.

Добавить комментарий