#744

Хеширование

Темы: [Эвристические методы]

Реализуйте структуру данных типа “множество строк”. Хранимые строки – непустые последовательности длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество и проверки принадлежности данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит 10⁶.

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

Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции – один из двух символов: + означает добавление данной строки в множество; ? означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит 10⁶. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве.

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

Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.

Примеры

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

+ hello
? hello
? bye
+ bye
? bye
#

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

YES
NO
YES

#745

Хеширование с удалением

Темы: [Эвристические методы] [Язык программирования] [Хеш]

Реализуйте структуру данных типа “множество строк”. Хранимые строки – непустые последовательности длиной не более 10 символов, состоящие из строчных латинских букв. Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству. Максимальное количество элементов в хранимом множестве не превосходит 10⁶.

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

Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция. Тип операции – один из трех символов: + означает добавление данной строки в множество; - означает удаление строки из множества; ? означает проверку принадлежности данной строки множеству. Общее количество операций во входном файле не превосходит 10⁶. Список операций завершается строкой, в которой записан один символ # – признак конца входных данных. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.

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

Программа должна вывести для каждой операции типа ? одну из двух строк YES или NO, в зависимости от того, встречается ли данное слово в нашем множестве.

Примеры

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

+ hello
+ bye
? bye
- bye
? bye
? hello
#

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

YES
NO
YES

#746

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

Темы: [Эвристические методы] [Куча]

Фирма 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 ≤ N ≤ 10⁵). Во второй строке заданы N натуральных чисел, каждое из которых не превосходит 10000.

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

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

Примеры

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

4
10 11 12 13

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

4.60

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

2
1 1

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

0.10

#747

Hexadecimal to binary

Темы: [Разные системы счисления]

Напишите программу, переводящую число из шестнадцатеричной системы счисления в двоичную.

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

Программа получает на вход строку, состоящую из цифр 0, ..., 9 и букв A, ..., F, являющуюся записью некоторого 16-ричного целого числа. Длина строки не превосходит 50 символов, первый символ в строке не равен 0. Необходимо вывести запись этого числа в двоичном виде без лидирующих нулей.

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

Выведите результат перевода.

Примеры

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

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

#748

Binary to hexadecimal

Темы: [Разные системы счисления]

Напишите программу, переводящую число из двоичной системы счисления в шестнадцатеричную.

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

Программа получает на вход строку, состоящую из нулей и единиц, длина которой не превосходит 1000 символов. Первый символ строки всегда единица. Данная строка является двоичной записью некоторого числа, которое необходимо записать в шестнадцатеричном виде и вывести с использованием цифр 0, ..., 9 и букв A, ..., F без лидирующих нулей.

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

Выведите результат перевода.

Примеры

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

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