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

Proggy-Buggy 2018: Задача E. Треугольник или не треугольник?

Задача

Баги считает треугольником любые три различные точки плоскости, соединенные отрезками. Даже написал диссертацию: «Треугольник или не треугольник? Вот в чём вопрос!», которая породила множество вопросов. Его очень утомили вопросы из разряда, «а это треугольник?». Если хотите, помогите Баги: напишите программу «Баги-бот», которая вместо Баги отвечала бы на вопрос, образуют ли три заданные точки треугольник.

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

Строка содержащая три пары целых чисел, координаты $x1$, $y1$, $x2$, $y2$, $x3$, $y3$ $(0\leq xi,yi\leq1000)$, разделенных пробелом.

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

Строка «$yes$» или «$no$» (без кавычек) — ответ программы «Баги-бот».

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 0 0 1 0 0 1 $yes$
2 1 1 1 2 1 3 $yes$
3 1 1 1 1 1 2 $no$

Код программы

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

В задаче главное внимательно прочитать условие. Если любые две заданные точки совпадают, то программа «Баги-бот» должна ответить no, иначе yes.

Ссылки

Код программы на IdeOne

e-olymp 1118. Арбузы

Задача

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

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

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

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

Вывести два числа: массу арбуза, который Иван Васильевич купит теще, и массу арбуза, который он купит себе, или вывести сообщение «$Ooops!$» (без кавычек), если кто-то останется без арбуза.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 5
3 5 8 4 6
$3$ $8$
2 8
6 12 9 5 8 15 7 10
$5$ $15$
3 1
10
$Ooops!$

Код программы

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

Из потока данных, где $n$ чисел найдём минимальное и максимальное число. Если $n<2$, то кто-то останется без арбуза, поэтому выведем «$Ooops!$» (без кавычек).

Ссылки

Условие задачи на E-Olymp

Код программы на IdeOne

e-olymp 8595. Собаки и обезьяны

Задача

У Барыша есть $n$ собак и $m$ обезьян. Он хочет выстроить их в одну линию. Но он не хочет, чтобы в каком-либо месте стояло подряд две собаки или две обезьяны, потому что в таком случае они начинают драться. Сколько существует различных вариантов построения, таких чтобы ни обезьяны, ни собаки не дрались. Ответ выведите по модулю $10^{9}+7$. Имейте в виду, что собаки и обезьяны между собой различаются.

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

Два числа $n$ и $m$ $\left(1 \leq n, m \leq 10^{5}\right)$.

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

Выведите количество различных вариантов построения обезьян и собак по модулю $10^{9}+7$.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 2 2 8
2 3 2 12
3 1 8 0
4 100000 100000 530123477
5 99999 100000 768947656

Код программы

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

В данной задаче три случая. Если разница между количеством собак и обезьян превышает один, то будет невозможно разместить их так, чтобы собаки с обезьянами чередовались. Размещение собак равно n!. Размещение обезьян равно m!. Если количество одинаково, то сначала может быть как собака, так и обезьяна. Поэтому ответом будет 2*n!*m! и выведем ответ по модулю $10^{9}+7$. В остальных случаях будет ответом n!*m! и выведем ответ по модулю $10^{9}+7$. Последний случай, значит, что разница между количеством собак и обезьян это $1$. Промежуточные вычисления будут иметь тип long long, так как в промежуточных вычислениях, число может быстро увеличиваться. Поэтому после каждого умножения будем искать остаток при делении числа на $10^{9}+7$, если число будет превышать $10^{9}+7$.

Ссылки

Условие задачи на E-Olymp

Код программы на IdeOne

e-olymp 8371. Четное или нечетное

Задача

Задано натуральное число $n$. Определить его четность.

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

Одно натуральное число $n$ $\left(1 \leq n \leq 10^{9}\right)$.

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

Если число $n$ четное, то вывести EVEN. Если нечетное, то вывести ODD.

Тесты

# ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
1 1 ODD
2 99 ODD
3 500 EVEN
4 1000000000 EVEN

Код программы (Линейные вычисления)

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

Если число четное, то будет выполняться условие n%2==0, тогда выводим EVEN. Если число нечетное, то будет выполняться условие n%2==1, тогда выводим ODD.

Код программы (Ветвление)

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

Число четное, если оно делится на $2$ без остатка, значит выполняется условие: n % 2 == 0. В противном случае, число будет нечетным.

Ссылки

Условие задачи на E-Olymp

Код программы на IdeOne (Линейные вычисления)

Код программы на IdeOne (Ветвление)