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

Условие

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

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

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

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

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

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

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

В третьей строке файла записано число M (1≤ M≤ 100000) — количество видов бабочек, про которых Андрей Сергеевич хочет узнать, есть ли они у него в коллекции или же нет. В последней строке входного файла содержатся через пробел 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:

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
	public static boolean find(int search, int[] arr, int len) {
		boolean ret = false;
		int fst = 0;
		int lst = len - 1;
		while (fst <= lst) {
			int mid = (fst + lst) / 2;
			if (search == arr[mid]) {
				ret = true;
				break;
			} else if (search < arr[mid]) {
				lst = mid - 1;
			} else {
				fst = mid + 1;
			}
		}
		return ret;
	}
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int len = scan.nextInt();
		int[] arr = new int[len];
		int i;
		for (i = 0; i < len; i++) {
			arr[i] = scan.nextInt();
		}
		int num = scan.nextInt();
		int search;
		for (i = 0; i < num; i++) {
			search = scan.nextInt();
			System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static boolean find(int search, int[] arr, int len) {

boolean ret = false;

int fst = 0;

int lst = len - 1;

while (fst <= lst) {

int mid = (fst + lst) / 2;

if (search == arr[mid]) {

ret = true;

break;

} else if (search < arr[mid]) {

lst = mid - 1;

} else {

fst = mid + 1;

}

return ret;

}

public static void main(String[] args) {

Scanner scan = new Scanner(System.in);

int len = scan.nextInt();

int[] arr = new int[len];

int i;

for (i = 0; i < len; i++) {

arr[i] = scan.nextInt();

}

int num = scan.nextInt();

int search;

for (i = 0; i < num; i++) {

search = scan.nextInt();

System.out.print((find(search, arr, len))? "YES\n" : "NO\n");

}

Алгоритм:

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

Scanner scan = new Scanner(System.in);
int len = scan.nextInt();
int[] arr = new int[len];
int i;
for (i = 0; i < len; i++) {
	arr[i] = scan.nextInt();
}
int num = scan.nextInt();

Scanner scan = new Scanner(System.in);

int len = scan.nextInt();

int[] arr = new int[len];

int i;

for (i = 0; i < len; i++) {

arr[i] = scan.nextInt();

}

int num = scan.nextInt();

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

int search;
for (i = 0; i < num; i++) {
	search = scan.nextInt();
	System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
}

int search;

for (i = 0; i < num; i++) {

search = scan.nextInt();

System.out.print((find(search, arr, len))? "YES\n" : "NO\n");

}

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

public static boolean find(int search, int[] arr, int len) {
	boolean ret = false;
	int fst = 0;
	int lst = len - 1;
	while (fst <= lst) {
		int mid = (fst + lst) / 2;
		if (search == arr[mid]) {
			ret = true;
			break;
		} else if (search < arr[mid]) {
			lst = mid - 1;
		} else {
			fst = mid + 1;
		}
	}
	return ret;
}

public static boolean find(int search, int[] arr, int len) {

boolean ret = false;

int fst = 0;

int lst = len - 1;

while (fst <= lst) {

int mid = (fst + lst) / 2;

if (search == arr[mid]) {

ret = true;

break;

} else if (search < arr[mid]) {

lst = mid - 1;

} else {

fst = mid + 1;

}

return ret;

}

Ссылки:

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

Условие

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

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

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

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

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

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

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner scan = new Scanner(System.in);
        int x1 = scan.nextInt(), y1 = scan.nextInt();
        int x2 = scan.nextInt(), y2 = scan.nextInt(), z2 = scan.nextInt();
        double D = 1/Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);
        System.out.print(D);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner scan = new Scanner(System.in);

int x1 = scan.nextInt(), y1 = scan.nextInt();

int x2 = scan.nextInt(), y2 = scan.nextInt(), z2 = scan.nextInt();

double D = 1/Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);

System.out.print(D);

}

Ход решения:

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

double D = 1/Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);

1	double D = 1/Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);

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

System.out.print(D);

1	System.out.print(D);

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: бабочка

e-olymp 3966. An ardent collector of butterflies

Условие

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

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

Тесты:

Код на Java:

Алгоритм:

Ссылки:

e-olymp 57. Butterfly-orderly

Условие

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

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

Тесты:

Код на Java:

Ход решения:

Ссылки:

$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