Шифровка

Условие задачи

Взята с сайта.
Мюллер много раз пытался поймать Штирлица с поличным, но тот всё время выкручивался. Как-то раз Штирлиц просматривал электронную почту. В это время незаметно вошел Мюллер и увидел, как у него на экране появился бессмысленный набор символов. «Шифровка», — подумал Мюллер. «UTF-8», — подумал Штирлиц.
Известно, что Штирлиц шифрует текст следующим образом:

1)Убирает все пробелы и знаки препинания.
2)Заменяет все подряд идущие одинаковые буквы на одну такую букву.
3)Многократно вставляет в произвольное место текста две одинаковых буквы.

Попробуйте восстановить текст, каким он был после второго шага. Для этого удалите из текста все пары одинаковых символов, добавленные на третьем шаге.

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

aaxxHuuuuelllnnloxxvvoo!

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

Hello!

Решение с использованием функционала класса String

Решение с использованием функционала структуры данных ArrayList

Решение

Записываем строку в переменную типа $latex String$. Записываем ее в $latex ArrayList$ посимвольно. В следующем цикле добавляем проверку на индекс текущего элемента чтобы не выйти за пределы списка и проверяем совпадают ли ближайшие 2 символа, если да то удаляем их, если нет то переходим к следующему шагу цикла. По его окончанию выводим элементы списка.
Пример решения со строками на ideone.
Пример решения с списком на ideone.

A301. Количество точек в полукругах

Задача

Даны действительные числа [latex]x_1, y_1[/latex], [latex]x_2, y_2[/latex], [latex]\ldots[/latex], [latex]x_{20}, y_{20}[/latex], [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex], [latex]\left( 0 < r_1 < r_2 < \ldots < r_{11} \right)[/latex]. Пары [latex]\left( x_1, y_1 \right)[/latex], [latex]\left( x_2, y_2 \right)[/latex], [latex]\ldots[/latex] [latex]\left( x_{20}, y_{20} \right)[/latex] рассматриваются как координаты точек плоскости. Числа [latex]r_1[/latex], [latex]r_2[/latex], [latex]\ldots[/latex], [latex]r_{11}[/latex] рассматриваются как радиусы одиннадцати полукругов в полуплоскости [latex]y > 0[/latex] с центром в начале координат. Найти количество точек, попадающих внутрь каждого полукруга (границы-полуокружности не принадлежат полукругам).

Примечание: будем рассматривать задачу с произвольным количеством точек [latex]n[/latex] и полуокружностей [latex]m[/latex].

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

[latex]n[/latex], [latex]m[/latex], [latex]x_i, y_i[/latex], [latex]i = \overline{1, n}[/latex], [latex]r_j[/latex], [latex]j = \overline{1, m}[/latex]

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

[latex]a_j[/latex] — количество точек в [latex]j[/latex]-том полукруге, [latex]j = \overline{1, m}[/latex].

Тест

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

14 4
5 -4
4 90
2 4.91
8 9.0
8.3 4.111
20 49.0
0 301.419
8.01 34.5
2.1 -49.1
0.01 0.03
56 1.91
4.04918 34.49294
-1.85892 5.01674
51 214
14.94 44.09
41.4 -154
-581.49 495
14.39 -81.682
77 194.4
0.3
20.82
50.9
51
65.845
90.37
109.58
170.83
217
301.58901
314

1
6
9
9
11
12
12
12
13
15
15

Иллюстрация к тесту:

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

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

Из входного потока считываем координаты всех точек, и отсеиваем из них те, у которых координата [latex]y \le 0[/latex], так как они по условию не могут принадлежать данным полуокружностям, остальные же добавляем в вектор точек dots. После этого, создаём два массива: первый rads — массив радиусов — считываем из входного потока, второй amounts — обнуляем. В i-ой ячейке массива amounts будем хранить количество точек, которые принадлежат [latex]i[/latex]-тому, и большим чем он полукругам. После этого, используя алгоритм бинарного поиска, находим наименьший полукруг, который содержит точку, и запоминаем его номер. Затем количество точек, содержащихся в данном и больших, чем данный полукругах, увеличиваем на единицу.

После обработки вектора точек, массив amounts преобразуем в массив количеств точек, содержащихся в конкретных полукругах, так как до этой обработки он содержит количество точек, которые «аккумулированы» i-тым, и большими чем i-тый полукруги.

Таким образом, общая асимптотика программы составит [latex]O \left(m+n \cdot \log_{2}{m}\right)[/latex], где [latex]n[/latex] — количество точек, а [latex]m[/latex] — полукругов.

Ссылки

e-olymp 6127. The queue of unlimited size

Задача взята с сайта e-olymp.com.

Условие

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

push n

Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.

pop

Удалить из очереди первый элемент. Программа должна вывести его значение.

front

Программа должна вывести значение первого элемента, не удаляя его из очереди.

size

Программа должна вывести количество элементов в очереди.

clear

Программа должна очистить очередь и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Размер очереди должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций front и pop программа должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример выходных данных.

Тесты:

Входные данные Выходные данные:
1 push 1
front
exit
ok
1
bye
2 size
push 1
size
push 2
size
push 3
size
exit
0
ok
1
ok
2
ok
3
bye

Код на Java:

Алгоритм:

Каждый элемент (узел) очереди состоит из информационной части (его значение) и адресной. В адресную часть первого элемента записываем адрес следующего элемента и т.д., тем самым мы создаем порядок следования элементов в очереди, связывая их между собой. При добавлении или удалении элемента мы соответственно изменяем размер очереди, который изначально равен нулю, а также меняем позиции указателей на начало и конец очереди. В условии задачи сказано, что если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error. Для этого соответствующие методы делаем логическими.

Ссылки:

Рабочий код для тестирования на Ideone.com: Ideone.com

e-olimp 6129. Дек неограниченного размера

Задача:

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front

Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit
Программа должна вывести bye и завершить работу.

Тесты:

Последовательность Результат
push_front
4
push_back
5
front
push_front
3
back
size
pop_front
pop_back
clear
pop_back
size
exit
ok

ok

4
ok

5
3
3
5
ok
error
0
bye

 

 

Решение

Решение на Ideone
Дек — (двухсторонняя очередь) — структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания являются одновременно FIFO и LIFO. Для реализации дека неограниченного размера удобно использовать двусвязный список.

e-olymp 6125. Простая очередь

Задача

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

  • push n — Добавить в очередь число n (значение n задается после команды). Программа должна вывести ok.
  • pop — Удалить из очереди первый элемент. Программа должна вывести его значение.
  • front — Программа должна вывести значение первого элемента, не удаляя его из очереди.
  • size — Программа должна вывести количество элементов в очереди.
  • clear — Программа должна очистить очередь и вывести ok.
  • exit — Программа должна вывести bye и завершить работу.

Гарантируется, что набор входных команд удовлетворяет следующим требованиям: максимальное количество элементов в очереди в любой момент не превосходит 100, все команды pop и front корректны, то есть при их исполнении в очереди содержится хотя бы один элемент.

Данную задачу также можно найти здесь.

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

Описаны в условии. Смотрите также тесты, расположенные ниже.

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

Описаны в условии. Смотрите также тесты, расположенные ниже.

Тесты

Входные данные Выходные данные
1 push 123
size
push -5
pop
exit
ok
1
ok
123
bye
2 push 1
push 2
front
push 42
pop
exit
ok
ok
1
ok
1
bye
3 push 1
push 2
pop
pop
size
exit
ok
ok
1
2
0
bye

Код

Реализуем абстрактный тип данных очередь, который отвечает принципу FIFO («первый вошёл – первый вышел») с помощью массива. Очередь имеет начало и конец, на которые указывают соответственно start и finish. Изначально очередь является пустой, поэтому start = 0, finish = 0. При добавлении нового элемента в очередь записываем его в конец. finish при этом увеличиваем на единицу. Извлекаемый же элемент берём в начале очереди, после чего start++. Если необходимо получить значение начала очереди, не извлекая его, воспользуемся функцией front(), возвращающей значение первого элемента. Для получения размера очереди используем функцию size(), которая возвращает разницу между концом и началом очереди. Если очередь нужно очистить, то приравниваем finish и start к нулю.

Код на сайте ideone.com находится здесь.

Timus №2002

Условие и начальные данные можно посмотреть по ссылке.

Тест:

исходные данные результат
6
register alena 223344 success: new user added
login alena 223 fail: incorrect password
login alena 223344 success: user logged in
login john 454545 fail: no such user
logout alena success: user logged out
logout alena fail: already logged out

Решение:

Для решения этой задачи я использовала два ассоциативных массива. Первый (usersAndPasswords) хранит в качестве ключа имя зарегистрированного пользователя, а в качестве значения — пароль этого пользователя; второй (loggedInUsers) хранит вошедших на форум пользователей, а в качестве значения всегда единица, потому что мы никак не используем значение, нам важно только есть ли имя пользователя в этом массиве или нет.

Когда пользователь входит на форум мы добавляем его имя как ключ в массив loggedInUsers. А когда он выходит мы удаляем его из этого массива. Для проверки есть ли пользователь на форуме или он уже вышел, мы проверяем есть ли он в массиве loggedInUsers или нету.

Ссылка на решение на ideone.

Ссылка на засчитанное решение на http://acm.timus.ru/.

Timus 2002 by Tolia

Для решения использовалось AVL-дерево выложенное тут.

Алгоритм решения задачи с соответствием с условием задачи.

 

Ссылка на решение.

BST – Двоичные деревья поиска

Задача

Разработать класс, реализующий функциональность дерева двоичного поиска.

Ссылка на условие http://java.mazurok.com/word-of-week/bst

Тесты

input output
put S 11.11 Ok
put E 22.22 Ok
put A 33.33 Ok
put R 44.44 Ok
put H 55.55 Ok
put C 66.66 Ok
put X 77.77 Ok
put M 88.88 Ok
size 8
min (A->33.33)/2
max (X->77.77)/1
print L0: (S->11.11)/8
.L1: (E->22.22)/6
..L2: (A->33.33)/2
…L3: (C->66.66)/1
..L2: (R->44.44)/3
…L3: (H->55.55)/2
….L4: (M->88.88)/1
.L1: (X->77.77)/1
delete E Ok
size 7
min (A->33.33)/2
max (X->77.77)/1
print L0: (S->11.11)/7
.L1: (H->55.55)/5
..L2: (A->33.33)/2
…L3: (C->66.66)/1
..L2: (R->44.44)/2
…L3: (M->88.88)/1
.L1: (X->77.77)/1
exit N/A

Критерий тестирования

В ходе тестирования мы добавляем 8 ключей с уникальными значениями. Затем мы определяем размер, минимальный и максимальный узлы, а также распечатываем все дерево, чтобы убедится, что оно имеет ожидаемою конфигурацию. Затем мы удаляем 1 ключ с серединным значением и повторяем вышеперечисленные операции, чтобы увидеть ожидаемые изменения в дереве.

Формат вывода:

Команды min и max выводят одиночный узел в следующем формате: (ключ->значение)/кол-во узлов

Команда print выводит дерево по уровням, каждая строчка имеет следующий формат: уровень: (ключ->значение)/кол-во узлов

Структура программы

Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:

  1. Класс CountingBST, реализующий функциональность дерева двоичного поиска с подсчетом количества узлов в дереве
  2. Класс CountingBSTTestApp, реализующий тестовое приложение

Класс CountingBST

Все методы разделены на пары — один метод пары приватный, а другой — публичный. Это необходимо для того, чтобы передавать первым аргументом корень дерева, начиная с которого выполняются все операции. Каждый приватный метод содержит первым аргументом узел, начиная с которого будет выполнятся операция. Публичный метод вызывает приватный и передает ему в качестве первого аргумента корень дерева. Это относится к основным операциям на дереве:

  1. put — помещает ключ и значение в дерево
  2. get — извлекает значение по клчу
  3. size — возвращает количество узлов дерева
  4. min — находит узел с минимальным ключом
  5. max — находит узел с максимальным ключом
  6. delete — удаление по Хиббарду ( Coursera presentation )
  7. print — печать дерева

Помимо основных полей, необходимых для BST, узел содержит поле count, в котором содержится количество все узлов поддерева, корнем которого является данный узел, включая сам узел.

Класс CountingBSTTestApp

Данный класс реализует тестовое приложение для класса CountingBST. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста. Он реализует командный интерпритатор, где каждая команда вызывает соответствующий публичный метод тестируемого класса. По-этому тест представляет собой текстовый файл с командами для стандартного потока ввода с консоли.

Ссылка на Ideone: https://ideone.com/b0xrPX

 

acm.timus.ru №2002. Тестовое задание

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

Время: 0.5 секунды
Память 64 Мб

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…
Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!
Мы рассмотрели вашу заявку на вакансию разработчика программного обеспечения и были заинтересованы вашей кандидатурой. Для оценки ваших профессиональных навыков мы предлагаем вам выполнить несложное тестовое задание: необходимо реализовать систему регистрации для форума. Она должна поддерживать три операции:
  1. «register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
  2. «login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
  3. «logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».
Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!
И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq n\leq 100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

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

Пример

Исходные данные Результат
6register vasya 12345

login vasya 1234

login vasya 12345

login anakin C-3PO

logout vasya

logout vasya

success: new user addedfail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Код

Данная программа представляет собой типичный пример использования таблицы символов, согласно терминологии Coursera. Для доступа к учетным записям используется интерфейс Map, а для реализации самой базы данных учетных записей — объект типа TreeMap. Учетная запись пользователей реализована в виде одного элемента типа Map.entry, где имя пользователя — это ключ, а атрибуты учетной записи — пароль и флаг подключен/отключен — реализованы в виде отдельной структуры AccountInfo, которая является значением этого ключа.

Время работы Выделено памяти
0.124 1 928 КБ
 Ссылка на Ideone: https://ideone.com/3Y2W4z

Binary Heap (двоичная куча)

В данном отчёте я напишу о структуре данных под названием куча (Heap), а точнее — о её разновидности.

Двоичная куча

Двоичная куча — структура данных, двоичное дерево, для которого выполнены три условия:

  • Значение в любой вершине не меньше чем значение в потомках
  • Расстояние до корня отличается не более чем на один уровень
  • Заполняется слева на право

Зафиксируем операции, которые будем проводить над кучей:

  • Достать максимальный элемент из кучи, не удаляя его
  • Добавить элемент в кучу
  • Создать кучу
  • Отсортировать массив путём превращения его в кучу, а кучи — в отсортированный массив
  • Узнать размер кучи
  • Удалить максимальный элемент из кучи

Описание методов

1. Восстановление свойства кучи

Каждый элемент помещается в конец кучи, потом становится на своё место, соответственно свойств кучи.

Сложность: [latex]O(\log(n))[/latex]

2. Возврат максимального элемента

Возвратить содержимое самой верхней вершины.

Сложность: [latex]O(1)[/latex]

3. Удаление максимального элемента

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

Сложность: [latex]O(\log(n))[/latex]

4. Пирамидальная сортировка

Достаточно заметить, что в самую первую вершину кучи всегда (по крайней мере, по введённым свойствам) встаёт максимальный элемент. Если каждый раз удалять максимальный элемент — получим отсортированный массив.

Сложность: [latex]O(n\log(n))[/latex]

О реализации

Реализуется структура данных с абстрактным типом данных.  Для хранения вершин будем использовать ArrayList. Для каждой вершины под номером [latex]i[/latex] её левый сын хранится в [latex]2*i+1[/latex] вершине, а правый — в [latex]2*i+2[/latex] вершине.

Класс содержит следующие методы:

  • Heap() — конструктор
  • shiftUp() — восходящее восстановление свойства кучи
  • shiftDown() — нисходящее восстановление свойства кучи
  • insert() — добавление элемента в кучу
  • delete() — удаление первой вершины
  • size() — размер кучи
  • isEmpty() — проверка на пустоту
  • toString() — преобразование в строку
  • max() — максимальный элемент
  • print() — вывод кучи на экран

Код