Киньте в личку Задача №1698. Гомо или гетеро? умоляю пАмАгИтЕ Максимальное время работы на одном тесте:
3 секунды
Максимальный объем используемой памяти:
256 мегабайт
Определим две операции над списком целых чисел:
insert number – добавляет заданное число в конец списка
delete number – удаляет первое вхождение заданного числа из списка. Если список не содержит заданного числа, то ничего не меняется.
Например, результатом добавления числа 4 в список [1, 2, 1] будет список [1, 2, 1, 4]. Если мы удалим число 1 из этого списка, то получим список [2, 1, 4], но если мы попытаемся удалить число 3 из списка [1, 2, 1, 4], то список останется неизменным.
Список называется гомогенным, если он содержит хоты бы два одинаковых числа и гетерогенным, если содержит хотя бы два различных числа. Например, список [2, 2] является гомогенным, список [2, 1, 4] – гетерогенным, список [1, 2, 1, 4] – одновременно и тем и другим, а пустой список не является ни гомогенным, ни гетерогенным.
Напишите программу, которая по последовательности операций добавления и удаления в пустой список, определяет после каждой из операций, является ли список гомогенным или гетерогенным.
Формат входных данных
Первая строка содержит целое число n – количество операций (1 ≤ n ≤ 100 000).
Следующие n строк содержат описания операций. Каждая операция описывается словом "insert" или "delete" и числом k – аргументом операции (-109 ≤ k ≤ 109).
Формат выходных данных
Для каждой операции выведите строку, содержащую единственное слово, описывающее состояние списка после этой операции:
"both" - если список одновременно является и тем и другим
"hetero" - если список является гетерогенным
"homo" - если список является гомогенным
"neither" - если список не принадлежит ни одному типу.
Выпишем последние цифры при возведении 2 в степень:
2¹=2, 2²=4, 2³=8, 2⁴=...6
2⁵=...2, 2⁶=...4, 2⁷=...8, 2⁸=...6
2⁹=...2, и т.д.
Видно, что если показатель степени делится на 4 без остатка, то последняя цифра равна 6. Если остаток 3, то последняя цифра 8. Если 2, то 4. Если 1, то 2.
Остаток от деления 1024 на 4 равен 0. Значит, 2¹⁰²⁴=...6
Выпишем последние цифры при возведении 8 в степень:
8¹=8, 8²=...4, 8³=...2, 8⁴=...6
8⁵=...8, 8⁶=...4, 8⁷=...2, 8⁸=...6
8⁹=...8. и т.д.
Показатель степени 1023 при делении на 4 дает в остатке 3. Следовательно, последняя цифра 8¹⁰²³ равна 2
8¹⁰²³=...2
Тогда можно найти последнюю цифру данного выражения
8¹⁰²³+2¹⁰²⁴-3=...6 + ...2 - 3=...8 -3=...5
ответ: 5 единиц