Timus 2002

Ссылка на засчитанное решение.

Идея решения состоит в том, чтобы использовать 2 ассоциативных массива, один из которых хранит в качестве ключа и значения логин и пароль пользователь, а второй — логин и состояние (онлайн/оффлайн).

На С++ можно обойтись и одним ассоциативным массивом, если воспользоваться такой структурой: map<string, pair<string, bool> > m.

Код программы (http://ideone.com/3Uqhuh):

 

BinarySearchTree

Двоичное дерево поиска, или BST, — это структура данных, предназначенная для работы с упорядоченными множествами.

Свойство дерева: если мы находимся в вершине с ключом k, то в левом поддереве находятся только ключи, которые строго меньше k, а в правом — строго больше.

Описание методов, реализованных в классе BinarySearchTree:

  • метод add():
    • если дерево пустое, то говорим, что корень — это наш узел;
    • сравниваем поступивший ключ с ключом узла:
      • если ключ меньше, то идём в левое поддерево;
      • если ключ равен, то задаём узлу новое поступившее значение;
      • если ключ больше, то идём в правое поддерево;
  • методы minKey() и maxKey():
    • по свойству дерева, минимальный ключ располагается в самом левом поддереве, а максимальный — в самом правом;
  • метод delete():
    • сначала находим нужный элемент по ключу (если такового нет, то выходим из метода);
    • если у удаляемого узла нет правого поддерева, то мы просто замещаем узел его левым поддеревом;
    • иначе находим в правом поддереве узел с минимальным ключом:
      • если у этого узла родитель — это удаляемый узел, то мы просто говорим, что правое поддерево удаляемого узла есть правое поддерево найденного, а ключ и значение удаляемого узла — это ключ и значение найденного;
      • если у этого узла другой родитель, то мы замещаем найденный узел его же правым поддеревом, а ключ и значение удаляемого узла — это ключ и значение найденного;

Код программы (http://ideone.com/Z2hbBv):

 

Обратная польская нотация

Передо мной стояли задачи:

  • перевести выражение в обратную польскую нотацию;
  • посчитать значение выражения.

Также я реализовала унарный минус, деление и функции cube(), sqrt(), pow10().

Выражение Обратная польская нотация Результат
15 * -(3 — 4) 15 3 4 — u- * 15
sqrt(4) + (8 * 0.5) 4 sqrt 8 0.5 * + 6
-cube(-3) 3 u- cube u- 27
92 / 10 92 10 / 9.2
pow10(2) — 95 + 4 * 8 2 pow10 95 — 4 8 * + 37

Алгоритм перевода в обратную польскую запись:

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

Алгоритм вычисления значения выражения в обратной польской нотации:

  • если в записи встретили число, то кладём его в стэк;
  • если в записи встретили функцию или унарный минус, то :
    • вытаскиваем из стэка верхний элемент;
    • применяем функцию к нему;
    • кладём элемент обратно в стэк;
  • если в записи встретили бинарный оператор, то:
    • вытаскиваем из стэка два верхних элемента;
    • выполняем над ними операцию;
    • кладём в стэк результат выполнения операции;
  • выводим последний элемент стэка.

Код программы (http://ideone.com/c69iJg):

 

 

BitSegmentedArray

Мне предоставили реализовать класс, который наследует SegmentedArray и характеризуется следующим:

  • принимает большой массив
  • элементы массива — 0 и 1
  • частые запросы get() и set()

Чтобы была возможность хранить очень большой массив, я решила построить класс с помощью битовых операций. Это было возможно, так как элемент моего массива — это 0 и 1, и любое число можно представить в виде последовательности нулей и единиц. Поэтому внутри класса если массив long, в одной ячейке которого может храниться до 64 элементов. Так была решена проблема с расходом памяти.

Из-за представления чисел в двоичном коде, к ним легко применимы битовые операции. Например, для реализации метода get() достаточно использовать битовый сдвиг и битовое «и». Следовательно, метод работает за О(1).

В реализации метода set() мне помогла блочная структура (64 элемента в 1 ячейке массива). А именно: я проверяю границы заданного отрезка, а ячейки, которые попали внутрь полностью просто приравниваю константе: 0 — если все элементы ячейки нули, -1 — если все элементы ячейки единицы.

Точно так же реализован метод add().

С методом min() всё и того проще: ответом служит либо 0, либо 1. Первый же ноль, встреченный на заданном отрезке, определяет ответ.

Также я предположила, что, как и в большинстве олимпиадных задач, индексация массива начинается с единицы. То есть в методе get(), set(), add() и min() необходима сначала уменьшить каждый индекс на единицу, а лишь потом проводить операции над массивом, так как индексация в нём начинается с нуля.

Теоретическая оценка сложности методов:

  • get(i): O(1);
  • set(x, y, val): O((y-x)/64);
  • add(x, y, val): O((y-x)/64) — для val%2==1, и O(1) — для val%2==0;
  • min(x, y) — O((x-y)/64) — в худшем случае (на отрезке все элементы нули), O(1) — в лучшем случае (на отрезке все элементы единицы).

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

Протестировать программу можно здесь.

Простейшая реализация интерфейса: SimpleSegmentedArray.

Сравнение скорости работы методов: