e-olymp 396. Дождь

Задача

Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капли могут встретиться препятствия, которые изменяют ее путь к земле.

Как это выглядит на координатной плоскости

Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Напишите программу, которая по координате $X$$0$ точки появления капли над землей вычисляет координату $X$ точки соприкосновения капли с землей $(Y  =  0)$.

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

Во входном файле в первой строке содержатся два целых числа через пробел – координата $X$$0$ точки появления капли $(0  < X$$0$ $<  10000)$ и количество отрезков-препятствий $N (0  ≤ N  ≤  100)$. Далее следует $N$ строк, каждая из которых содержит четыре разделенные пробелами числа $x$$1$,  $y$$1$,  $x$$2$,  $y$$2$ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $0$ до $10000$,  $x$$1$ $ < x$$2$,  $y$$1$ $≠$ $y$$2$$)$. Отрезки не пересекаются и не соприкасаются.

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

В выходной файл вывести одно целое число – координату $X$ точки соприкосновения капли с землей.

Тесты

Входные данные Выходные данные
30 4
25 35 40 30
1 32 20 30
33 22 50 29
18 10 33 19
18
12 5
12 9 13 5
17 8 19 5
13 10 10 7
6 17 4 12
13 4 5 12
 13
40 3
12 30 21 39
41 5 45 70
20 30 25 35
 40
70 6
45 75 598 37
489 48 726 47
673 873 46 36
60 735 373 762
483 73 364 59
462 375 583 457
726

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

 

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

Сортируем наш динамический массив по наибольшим координатам $y$ и, если $y$ равны, по координатам $x$.

Далее составим алгоритм решения задачи:

  1. Если $X$ $ ∈ [x$$1$$, x$$2$$]$, то наша капля пересечется с данной прямой. В противном случае мы просто игнорируем данное препятствие.
  2. Тогда мы сравниваем координаты $y$$1$ и $y$$2$, выбираем из них наименьшее и присваиваем соответствующую координату $x$$1$ или $x$$2$ координате нашей капли $X$.
  3. Повторяем до тех пор, пока не будут обработаны все препятствия и выводим последнюю присвоенную координату $X$ нашей капли, так как она и будет координатой $x$ соприкосновения капли с зимой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

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

Задача:

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

push_front

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

push_back

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

pop_front

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

pop_back

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

front

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

back

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

size

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

clear

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

exit

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

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

Результат на C++

Результат на Java

Код на C++:

Код на Java:

 

Пояснение:

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

Трудности возникли тогда, когда количество элементов в деке сравнялось с вместимостью базового массива. В таком случае необходимо величить вместимость дека. Сделать это можно следующим образом. Нужно создать новый массив, перенести в него элементы старого массива, а после присвоить указателю на старый массив указатель на новый. После увеличения вместимости дека возник вопрос: Куда указывают указатели? Мы их не меняли, а значит они имеют прежние значения, что уже не актуально. Так как первый элемент в новом массиве находится на нулевой позиции, меняем значение указателя на первый элемент (front_) на нуль. Указатель на последний элемент (back_) теперь должен иметь значение равное, уменьшенному на единицу, количеству элементов. Осталось только изменить значение вместимости (capacity), у меня вместимость увеличивается вдвое.

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