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

Задача

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

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

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

n, m, x_i, y_i, i = \overline{1, n}, r_j, j = \overline{1, m}

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

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

Тест

Входные данные Выходные данные
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

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

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

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

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

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

Ссылки

e-olymp 2820. Перемещение коня

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из n клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче.

Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток n и b в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из a в b.

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

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква (ah), задающая столбец и второй – цифра (18), задающая строку на шахматной доске.

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

Для каждого теста вывести одну строку следующего содержания: «Путь от xx к yy занимает n шагов»

Тест

Пример входных данных Пример выходных данных
e2 e4 Путь от e2 к e4 занимает 2 шагов.
a1 b2 Путь от a1 к b2 занимает 4 шагов.
b2 c3 Путь от b2 к c3 занимает 2 шагов.
a1 h8 Путь от a1 к h8 занимает 6 шагов.
a1 h7 Путь от a1 к h7 занимает 5 шагов.
h8 a1 Путь от h8 к a1 занимает 6 шагов.
b1 c3 Путь от b1 к c3 занимает 1 шагов.
f6 f6 Путь от f6 к f6 занимает 0 шагов.

 

Решение

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Для начала объявим переменные aи b типа char, где a и b — это координаты двух клеток. В цикле при помощи форматированного ввода по шаблону вводим 4 переменных, в которых a, ny — координата одной клетки и b, ty — координата другой клетки. nx — цифровая координата, которую мы получаем из буквы, отнимая от a.  Создаем очередь, добавляем начальную клетку и ищем все возможные ходы пока не попадем в нужную клетку. Чтобы получить длину пути, нужно хранить длины путей до данной клетки в матрице и обновлять ее, по ходу продвижения. Длина в начальной клетке — 0, а длина в каждой последующей — 1. На экран выводим количество шагов, которые необходимо сделать конем, чтобы попасть из одной клетки в другую.

e-olymp 6128. Простой дек

Постановка задачи

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

push_front

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

push_back

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

pop_front

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

pop_back

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

front

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

back

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

size

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

clear

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

exit

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

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

  • pop_front,
  • pop_back,
  • front,
  • back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

Также условие задачи можно посмотреть здесь.

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

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

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

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

Тесты

Входные данные Выходные данные
1 push_back 3
push_front 14
size
clear
push_front 1
back
push_back 2
front
pop_back
size
pop_front
size
exit
ok
ok
2
ok
ok
1
ok
1
2
1
1
0
bye
2 push_front 7
push_front 8
push_front 9
pop_back
back
push_front 11
size
pop_back
pop_back
pop_back
push_back 90
front
exit
ok
ok
ok
7
8
ok
3
8
9
11
ok
90
bye
3 push_back -5
push_back -20
push_back 2
pop_front
push_front 7
size
clear
pop_back
push_front 11
size
exit
ok
ok
ok
-5
ok
3
ok
-1
ok
1
bye

Посмотреть работу программы на примере первого теста можно на сайте ideone.

Решение

Описание решения

Чтобы смоделировать работу дека, напишем соответствующий класс class Deque, который будет содержать следующие поля:

  1. int[] data — массив для хранения данных внутри дека;
  2. static final int maxSize = 10000 — статическое неизменное поле, содержащее максимальное количество элементов в деке (по условию задачи 10000);
  3. int size — текущее количество элементов в деке;
  4. int head, end — индексы первого (верхнего) и последнего (нижнего) элементов дека в массиве int[] data.

Так как дек — это структура, в которой элементы можно добавлять и удалять как в начало, так и в конец, то индексы первого и последнего элементов в массиве будут постоянно изменяться при добавлении/удалении в дек объектов. Поэтому крайне важно организовать модель так, чтобы при произвольном добавлении в начало и конец дека новых элементов, массив содержал эти элементы в правильном порядке, а в программе не возникало ошибки выхода за границы массива.

Это сделано следующим образом: изначально индексы первого и последнего элементов массива data равны 0, как и размер массива (это описывается в конструкторе класса Deque). При добавлении в начало дека нового элемента, индекс первого элемента int head будет смещаться на 1 вперед, пока не достигнет верхней границы массива (9999), затем начнет свой отсчет опять с нуля. При добавлении нового элемента в конец дека, смещаться будет индекс последнего элемента, причем вниз, пока не достигнет 0, затем продолжит с верхней границы массива. Такой подход дает возможность непрерывно добавлять и удалять в дек элементы, однако если количество элементов в деке станет максимальным ( if (size == maxSize)), добавить новый элемент уже не получится, для него нужно освободить место.

При запуске программы, сперва создается объект класса Deque dq = new Deque(), затем программа принимает входные данные while((str = br.readLine()) != null) и вызывает соответствующий метод класса Deque.

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

  1. push_front и push_back — добавление в дек нового элемента. Если текущее количество элементов в деке равен максимально допустимому количеству элементов, добавления происходить не будет, а программа выдаст предупреждающее сообщение. Если дек не пустой, количество элементов увеличится на 1, а сам элемент будет размещен в массиве с соответствующим индексом head или end (в зависимости от того, куда добавляется элемент, в верх или в низ). Этот индекс, соответственно, увеличится или уменьшится на 1. Если количество элементов в деке равно 0, вставка произойдет точно так же, однако индексы head и end останутся прежними, указывая таким образом на один и тот же элемент. После успешной вставки на экран будет выведено сообщение «ok».
  2. pop_front и pop_back — если в деке есть хотя бы 1 элемент, функция возвратит из массива data элемент с индексом head или end (соответственно для каждого метода), при этом этот индекс «двигается» в обратную для себя сторону (индекс верхнего элемента уменьшается, индекс нижнего — увеличивается), а количество элементов в деке уменьшается на 1. Если же дек пуст, функция вернет значение -1.
  3. back и front — методы, аналогичные pop_front и pop_back, с тем отличием, что не будут изменять индексы head и end или количество элементов в деке, а просто возвратят нужные элементы.
  4. size — возвращает количество элементов в деке ( return size;).
  5. clear — приравнивает поля size, head и end к 0, имитируя удаление из дека всех элементов. Выводит на экран сообщение «ok».
  6. exit — выводит на экран сообщение «bye», после чего программа завершит работу.

Посмотреть решение задания можно на сайте e-olymp.

e-olymp 6122. Простой стек

Задача

Формулировка задания на e-olymp.

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

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

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

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

Каждая строка содержит одну команду.

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

Для каждой команды вывести в отдельной строке соответствующий результат.

Тесты

 Входные данные  Выходные данные
            push 2                             push 3                             push 5                              back                                 size                                   pop                                 size                                  push 7                             pop                                clear                                 size                                   exit                     ok                                       ok                                       ok                                        5                                        3                                        5                                        2                                       ok                                        7                                       ok                                        0                                      bye

Отмечу так же, что программа успешно прошла все тесты на сайте e-olymp со следующими результатами.

Решение

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Структура класса Stack из себя представляет следующее:

  • Динамический массив   storage  типа  Vector<Integer> , который, по сути, и является хранилищем элементов стека;
  • Конструктор, в котором происходит инициализация вектора  storage ;
  • Метод  push(int number)  типа void , который принимает как параметр число, и заносит это число в стек;
  • Метод  pop()  типа  int , который возвращает значение верхнего элемента стека и извлекает его;
  • Метод  back()  типа  int , который возвращает значение верхнего элемента стека, без его извлечения;
  • Метод  size() , который возвращает количество элементов, находящихся в стеке;
  • Метод  clear() , который очищает стек;
  • Метод exit()  типа String , который возвращает строку «bye».

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 6123. Стек с защитой от ошибок

Задача

Стек с защитой от ошибок

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

push n

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

pop

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

back

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

size

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

clear

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

exit

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

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

Команды для стека.

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

Соответствующие значения для каждой команды(см. выше).

Тесты

Последовательность Результат
1 push 2
back
pop
size
pop
push 1
size
exit
ok
2
2
0
error
ok
1
bye
2 push 3
push 1
push 5
size
pop
size
exit
ok
ok
ok
3
5
2
bye
3 back
push 9
pop
pop
exit
error
ok
9
error
bye
4 size
push 1
size
back
pop
exit
0
ok
1
1
1
bye

Код

Решение

Создаем структуру в которой реализуем все команды для стека с помощью функций и указателя cursorcursor указывает на последний элемент в строке. Изначально cursor , т.к. элементы в массиве, на которые бы он указывал, отсутствуют.

push n  записывает в ячейку с номером cursor элемент n.size возвращает cursor т.е. действительный размер стека.pop возвращает последний помещённый в стек элемент, то есть элемент с номером pointer+1 , при этом удаляя его из стека. back возвращает последний помещённый в стек элемент, то есть элемент с номером cursor-1.В обоих случаях для проверки того, пуст ли стек, используется логическая функция error. clear обнуляет массив cursor и присваивает cursor начальное значение = -1.Команды считываются и выполняются пока не будет введено exit, после чего выведется соответствующее сообщение и программа завершится.

Ссылка на Ideone

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-дерево выложенное тут.

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

 

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