e-olimp 3966. An ardent collector of butterflies

13.06.2017 by Владислав Козачков

Задача взята с сайта 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$

Код на Haxe:

package;

import cpp.Lib;
import haxe.io.Input;
import haxe.io.Output;

class Main {
	public static function find(search:Int, arr:Array<Int>) {
		var ret:Bool  = false;
		var fst:Int = 0;
		var lst:Int = arr.length - 1;
		var mid:Int;
		while (fst <= lst) {
			mid = Math.floor((fst + lst) / 2);
			if (search == arr[mid]) {
				ret = true;
				break;
			} else if (search < arr[mid]) {
				lst = mid -1;
			} else {
				fst = mid +1;
			}
		}
		return ret;
	}
	
	static function main() {
		var input:Input = Sys.stdin();
		var output:Output = Sys.stdout();
		var len:Int = Std.parseInt(input.readLine());
		var arr = new Array<Int>();
		var i:Int;
		var input_str:String = input.readLine();
		var space_loc:Int;
		var num:Int;
		var search:Int;
		for (i in 0...len) {
			space_loc = input_str.indexOf(" ");
			if (space_loc == 0 && input_str.charAt(0) != " ") {
				space_loc = input_str.length;
			}
			arr.push(Std.parseInt(input_str));
			if (space_loc != input_str.length) {
				input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
			}
		}
		num = Std.parseInt(input.readLine());
		input_str = input.readLine();
		for (i in 0...num) {
			space_loc = input_str.indexOf(" ");
			if (space_loc == 0 && input_str.charAt(0) != " ") {
				space_loc = input_str.length;
			}
			search = Std.parseInt(input_str);
			output.writeString(find(search, arr)? "YES\n":"NO\n");
			if (space_loc != input_str.length) {
				input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
			}
		}
	}
}

package;

import cpp.Lib;

import haxe.io.Input;

import haxe.io.Output;

class Main {

public static function find(search:Int, arr:Array<Int>) {

var ret:Bool = false;

var fst:Int = 0;

var lst:Int = arr.length - 1;

var mid:Int;

while (fst <= lst) {

mid = Math.floor((fst + lst) / 2);

if (search == arr[mid]) {

ret = true;

break;

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

lst = mid -1;

} else {

fst = mid +1;

}

return ret;

}

static function main() {

var input:Input = Sys.stdin();

var output:Output = Sys.stdout();

var len:Int = Std.parseInt(input.readLine());

var arr = new Array<Int>();

var i:Int;

var input_str:String = input.readLine();

var space_loc:Int;

var num:Int;

var search:Int;

for (i in 0...len) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0 && input_str.charAt(0) != " ") {

space_loc = input_str.length;

}

arr.push(Std.parseInt(input_str));

if (space_loc != input_str.length) {

input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);

}

num = Std.parseInt(input.readLine());

input_str = input.readLine();

for (i in 0...num) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0 && input_str.charAt(0) != " ") {

space_loc = input_str.length;

}

search = Std.parseInt(input_str);

output.writeString(find(search, arr)? "YES\n":"NO\n");

if (space_loc != input_str.length) {

input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);

}

Ход решения:

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

var input:Input = Sys.stdin();
var output:Output = Sys.stdout();
var len:Int = Std.parseInt(input.readLine());
var arr = new Array<Int>();
var i:Int;
var input_str:String = input.readLine();
var space_loc:Int;
var num:Int;
var search:Int;
for (i in 0...len) {
	space_loc = input_str.indexOf(" ");
	if (space_loc == 0 && input_str.charAt(0) != " ") {
		space_loc = input_str.length;
	}
	arr.push(Std.parseInt(input_str));
	if (space_loc != input_str.length) {
		input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
	}
}
num = Std.parseInt(input.readLine());

var input:Input = Sys.stdin();

var output:Output = Sys.stdout();

var len:Int = Std.parseInt(input.readLine());

var arr = new Array<Int>();

var i:Int;

var input_str:String = input.readLine();

var space_loc:Int;

var num:Int;

var search:Int;

for (i in 0...len) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0 && input_str.charAt(0) != " ") {

space_loc = input_str.length;

}

arr.push(Std.parseInt(input_str));

if (space_loc != input_str.length) {

input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);

}

num = Std.parseInt(input.readLine());

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

input_str = input.readLine();
for (i in 0...num) {
	space_loc = input_str.indexOf(" ");
	if (space_loc == 0 && input_str.charAt(0) != " ") {
		space_loc = input_str.length;
	}
	search = Std.parseInt(input_str);
	output.writeString(find(search, arr)? "YES\n":"NO\n");
	if (space_loc != input_str.length) {
		input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
	}
}

input_str = input.readLine();

for (i in 0...num) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0 && input_str.charAt(0) != " ") {

space_loc = input_str.length;

}

search = Std.parseInt(input_str);

output.writeString(find(search, arr)? "YES\n":"NO\n");

if (space_loc != input_str.length) {

input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);

}

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

public static function find(search:Int, arr:Array<Int>) {
	var ret:Bool  = false;
	var fst:Int = 0;
	var lst:Int = arr.length - 1;
	var mid:Int;
	while (fst <= lst) {
		mid = Math.floor((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 function find(search:Int, arr:Array<Int>) {

var ret:Bool = false;

var fst:Int = 0;

var lst:Int = arr.length - 1;

var mid:Int;

while (fst <= lst) {

mid = Math.floor((fst + lst) / 2);

if (search == arr[mid]) {

ret = true;

break;

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

lst = mid -1;

} else {

fst = mid +1;

}

return ret;

}

Ссылки:

Рабочий код для тестирования на try.haxe.org: Try Haxe !

e-olymp 57. Бабочка-санитар

26.04.2017 by Николай Яковлев

Задача взята с сайта e-olymp.com.
Решение на с++

Условие

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

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

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

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

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

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

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

Единственное число – оптическая сила крылышек-линз [latex]D[/latex].

Код

class Main
{

    static function main()
    {
        var x1, y1;
        var x2, y2, z2;

        x1 = getNextInt();
        y1 = getNextInt();
        x2 = getNextInt();
        y2 = getNextInt();
        z2 = getNextInt();

        var result:Float = 1 / Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);

        var output = Sys.stdout();
        output.writeString(Std.string(result) + "\n");
    }

    static function getNextInt()
    {
        var number = Sys.stdin().readLine();
        return Std.parseInt(number);
    }
}

class Main

{

static function main()

{

var x1, y1;

var x2, y2, z2;

x1 = getNextInt();

y1 = getNextInt();

x2 = getNextInt();

y2 = getNextInt();

z2 = getNextInt();

var result:Float = 1 / Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + z2 * z2);

var output = Sys.stdout();

output.writeString(Std.string(result) + "\n");

}

static function getNextInt()

{

var number = Sys.stdin().readLine();

return Std.parseInt(number);

}

Ход решения:

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

e-olymp 57. Butterfly-orderly

20.03.2017 by Владислав Козачков

Задача взята с сайта e-olymp.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.

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

Единственное число – оптическая сила крылышек-линз $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

Код на Haxe:

class Test {
    public var x1:Int;
    public var y1:Int;
    public var x2:Int;
    public var y2:Int;
    public var z2:Int;
        
    public function new(x1, y1, x2, y2, z2) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        this.z2 = z2;
    }
    
    static function main() {
        var tests = new Array();
        tests.push(new Test(10, 20, 10, 20, 100));
        tests.push(new Test(10, 30, 10, 30, 60));
        tests.push(new Test(10, 30, 20, 40, 110));
        var D:Float;
        for (i in 0...3) {
            var x1:Int = tests[i].x1;
            var y1:Int = tests[i].y1;
            var x2:Int = tests[i].x2;
            var y2:Int = tests[i].y2;
            var z2:Int = tests[i].z2;
            D = 1/Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+z2*z2);
            trace(D);
        }
    }
}

class Test {

public var x1:Int;

public var y1:Int;

public var x2:Int;

public var y2:Int;

public var z2:Int;

public function new(x1, y1, x2, y2, z2) {

this.x1 = x1;

this.y1 = y1;

this.x2 = x2;

this.y2 = y2;

this.z2 = z2;

}

static function main() {

var tests = new Array();

tests.push(new Test(10, 20, 10, 20, 100));

tests.push(new Test(10, 30, 10, 30, 60));

tests.push(new Test(10, 30, 20, 40, 110));

var D:Float;

for (i in 0...3) {

var x1:Int = tests[i].x1;

var y1:Int = tests[i].y1;

var x2:Int = tests[i].x2;

var y2:Int = tests[i].y2;

var z2:Int = tests[i].z2;

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

trace(D);

}

Ход решения:

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

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

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

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

trace(D);

trace(D);

Примечание: Входные данные для тестирования были заданы программно из-за определенных затруднений при использовании стандартного ввода.

Ссылки:

Рабочий код для тестирования на try.haxe.org: Try Haxe !

Алексей Маслеев	Сергей Завада	Анастасия Улановская
Владислав Козачков	Николай Яковлев	Даша Тарабаева
Денис Швецов	Лена Наумова	Артур Тарасов
Евгений Кравчук	Иоанна Васильева	Дарья Пиндус
Даша Кивганова	Артём Мисесин	Кирилл Автомонов
Алёна Ищук	Александр Зайченко	Маша Лукьянова
Игорь Варламов	Геннадий Муржи

haxe

Учебные материалы по программированию

Tag Archives: бабочка

e-olimp 3966. An ardent collector of butterflies

Условие

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

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

Тесты:

Код на Haxe:

Ход решения:

Ссылки:

e-olymp 57. Бабочка-санитар

Условие

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

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

Код

Ход решения:

e-olymp 57. Butterfly-orderly

Условие

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

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

Тесты:

Код на Haxe:

Ход решения:

Ссылки: