e-olymp 3966. An ardent collector of butterflies

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

Условие

Как известно, Андрей Сергеевич — ярый коллекционер бабочек. Он имеет огромную коллекцию, экспонаты которой собраны со всего мира. Будем считать, что в мире существует 2000000000 видов бабочек.

Чтобы не запутаться, Андрей Сергеевич присвоил каждому виду уникальный номер. Нумерация бабочек всегда начинается с единицы.

Теперь он хочет знать, есть ли бабочка с видом K в его коллекции, или же её придётся добывать, затрачивая уйму сил и денег.

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

В первой строке входного файла содержится единственное число N (1N100000) — количество видов бабочек в коллекции Андрея Сергеевича.

В следующей строке через пробел находятся N упорядоченных по возрастанию чисел — номера видов бабочек в коллекции.

Все виды бабочек в коллекции имеют различные номера.

В третьей строке файла записано число M (1M100000) — количество видов бабочек, про которых Андрей Сергеевич хочет узнать, есть ли они у него в коллекции или же нет. В последней строке входного файла содержатся через пробел M чисел — номера видов бабочек, наличие которых необходимо проверить.

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

Выходной файл должен содержать M строчек. Для каждого запроса выведите «YES«, если бабочка с данным номером содержится в коллекции, и «NO» — в противном случае.

Тесты:

Входные данные Выходные данные:
1 7
10 47 50 63 89 90 99
4
84 33 10 82
NO
NO
YES
NO
2 10
1 4 7 11 12 43 44 67 344 355
5
1 2 4 44 45
YES
NO
YES
YES
NO

Код на Java:

Алгоритм:

Вначале считываем необходимые нам значения: размер коллекции len, элементы коллекции (массив arr) и количество проверяемых экспонатов num:

Затем по очереди считываем номера проверяемых экспонатов, ищем их в массиве, используя алгоритм бинарного поиска, и затем сообщаем о наличии или отсутствии экспоната:

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

Ссылки:

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

e-olymp 57. Butterfly-orderly

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

Условие

Школьники, идя из дому в школу или наоборот – со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.

Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами X_1Y_1, бабочка перелетала в точку с координатами X_2Y_2, Z_2, расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.

Какую оптическую силу D имели крылышки-линзы бабочки в этот момент?

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

В первой строке 2 числа: координаты X_1Y_1, обертки от конфетки. Во второй – 3 числа: координаты X_2Y_2, Z_2 бабочки в момент сжигания обертки.

Все входные данные целые числа, не превышающие по модулю 1000.

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

Единственное число – оптическая сила крылышек-линз D, вычисленная с точностью до 3-х знаков после запятой за правилами математических округлений.

Тесты:

X_1 Y_1 X_2 Y_2 Z_2 D
10 20 10 20 100 0.010
10 30 10 30 50 0.020
10 30 20 40 110 0.009

Код на Java:

Ход решения:

Вычисляем оптическую силу линзы D по формуле D = \frac{1}{f}, где f – расстояние между бабочкой и обёрткой. вычисляем его по формуле: f = \sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2+Z_2^2}. Вычисление в одну строку:

Далее  выводим на экран:

Ссылки:

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