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 1078. The line degree

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

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

Условие

Обозначим через $a*b$ конкатенацию строк $a$ и $b$.

Например, если $a = «abc»$ и $b = «def»$, то $a*b = «abcdef»$.

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:

$a^0 = «»$ (пустая строка)
$a^{n+1} = a*a^n$

По заданной строке $s$ необходимо найти наибольшее значение $n$, для которого $s = a^n$ для некоторой строки $a$.

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

Каждый тест состоит из одной строки $s$, содержащей печатные (отображаемые) символы. Строка $s$ содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки $s$ вывести в отдельной строке наибольшее значение $n$, для которого $s = a^n$ для некоторой строки $a$.

Тесты:

Входные данные	Выходные данные
$abcabc$ $gcdgcd$ $gcgcgc$ $gggggg$ $hhhh$	$2$ $2$ $3$ $6$ $4$
$BbbbBbbbBbbb$ $dogdogdog$ $aaaaaaaa$ $cstring$	$3$ $3$ $8$ $1$

Код на Haxe:

package;

import cpp.Lib;

class Main 
{
	static function stringpow(s:String):Int {
		var answer:Int = 1;
		var size:Int = s.length;
		var i:Int;
		for (i in 1...Math.round(size / 2 + 1)) {
			/*searching for tha alleged answer degree,
			 *which is necessarily a length-of-string divisor*/
			if (s.length % i == 0) {
				//assume that choosen line degree is maximal
				var broken:Bool = false;
				var j:Int = 0;
				while (j < size-i) {
					//comparing string blocks
					if (s.substr(j, i) != s.substr(j+i, i)) {
						broken = true;
						break;
					}
					j += i;
				}
				if (!broken) {
					//if the expected degree of the string was correct, return it.
					answer = Math.round(size / i);
					break;
				}
			}
		}
		return answer;
	}
	
	static function main() {
		var s:String = Sys.stdin().readLine();
		while (s.length > 0) {
			Sys.stdout().writeString(stringpow(s) + "\n");
			s = Sys.stdin().readLine();
		}
	}
}

package;

import cpp.Lib;

class Main

{

static function stringpow(s:String):Int {

var answer:Int = 1;

var size:Int = s.length;

var i:Int;

for (i in 1...Math.round(size / 2 + 1)) {

/*searching for tha alleged answer degree,

*which is necessarily a length-of-string divisor*/

if (s.length % i == 0) {

//assume that choosen line degree is maximal

var broken:Bool = false;

var j:Int = 0;

while (j < size-i) {

//comparing string blocks

if (s.substr(j, i) != s.substr(j+i, i)) {

broken = true;

break;

}

j += i;

}

if (!broken) {

//if the expected degree of the string was correct, return it.

answer = Math.round(size / i);

break;

}

return answer;

}

static function main() {

var s:String = Sys.stdin().readLine();

while (s.length > 0) {

Sys.stdout().writeString(stringpow(s) + "\n");

s = Sys.stdin().readLine();

}

Ход решения:

Из условия следует, что степень строки определяется максимальным числом одинаковых подстрок. В таком случае степень строки является одним из делителей длины этой строки, и очевидно, что максимальная степень строки будет обратно пропорциональна максимальной длине подстроки.
Для решения поставленной задачи используем функцию $cstringpow$, которая в качестве аргумента принимает строку, и возвращает её степень. Реализуем эту функцию следующим образом: вначале ищем делители значения переменной $size$ (с использованием счётчика $i$ в цикле), в которую было предварительно была сохранена длина строки, полученная из свойства $lenght$. Числа, которые будут получатся из выражения $size/i$, будут предполагаемой максимальной степенью строки. Естественно, они будут находится в порядке убывания.

Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения $size/i$ будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, следовательно, её степень равна $1$.

Ссылки:

Оригинальное решение: cpp.mazurok.com.
Рабочий код для тестирования на try.haxe.org: Try Haxe !

A704

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

Задача взята отсюда.

Условие

Даны квадратные матрицы с целыми числами $A$, $B$ и $C$ порядка $n$. Получить матрицу $(A+B)*C$.

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

В первой строке — размерность матриц $n$. Далее вводятся построчно матрицы $A$, $B$ и $C$.

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

Вывести построчно результирующую матрицу $(A+B)*C$.

Тесты:

Тесты:

$n$	$A$	$B$	$C$	Output
$3$	$1$ $2$ $3$ $4$ $5$ $6$ $7$ $8$ $9$	$0$ $1$ $0$ $0$ $0$ $0$ $0$ $0$ $0$	$1$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $1$	$1$ $3$ $3$ $4$ $5$ $6$ $7$ $8$ $9$
$2$	$4$ $6$ $12$ $7$	$3$ $2$ $1$ $1$	$7$ $3$ $2$ $8$	$65$ $85$ $107$ $103$
$3$	$3$ $4$ $1$ $1$ $2$ $1$ $5$ $6$ $7$	$1$ $3$ $1$ $2$ $4$ $5$ $6$ $5$ $1$	$1$ $1$ $0$ $5$ $8$ $1$ $2$ $3$ $2$	$43$ $66$ $11$ $45$ $69$ $18$ $82$ $123$ $27$

Код на Haxe:

package;

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

class Main 
{
	static function main() 
	{
		var input:Input = Sys.stdin();
		var n:Int = Std.parseInt(input.readLine());
		var ab = new Array<Array<Int>>();
		var c = new Array<Array<Int>>();
		var d = new Array<Array<Int>>();
		var i:Int = 0, j:Int = 0, k:Int = 0;
		var input_str:String;
		var space_loc:Int;
		var arr_temp:Array<Int>;
		for (i in 0...n) {
			arr_temp = new Array<Int>();
			input_str = input.readLine();
			for (j in 0...n) {
				space_loc = input_str.indexOf(" ");
				if (space_loc == 0) {
					space_loc = input_str.length;
				}
				arr_temp.push(Std.parseInt(input_str));
				if (space_loc != input_str.length) {
					input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
				}
			}
			ab.push(arr_temp);
		}
		for (i in 0...n) {
			input_str = input.readLine();
			for (j in 0...n) {
				space_loc = input_str.indexOf(" ");
				if (space_loc == 0) {
					space_loc = input_str.length;
				}
				ab[i][j] += (Std.parseInt(input_str));
				if (space_loc != input_str.length) {
					input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
				}
			}
		}
		for (i in 0...n) {
			arr_temp = new Array<Int>();
			input_str = input.readLine();
			for (j in 0...n) {
				space_loc = input_str.indexOf(" ");
				if (space_loc == 0) {
					space_loc = input_str.length;
				}
				arr_temp.push(Std.parseInt(input_str));
				if (space_loc != input_str.length) {
					input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
				}
			}
			c.push(arr_temp);
		}
		for (i in 0...n) {
			arr_temp = new Array<Int>();
			for (j in 0...n) {
				arr_temp[j] = 0;
				for (k in 0...n) {
					arr_temp[j] += ab[i][k] * c[k][j];
				}
				Sys.stdout().writeString(arr_temp[j] + " ");
			}
			d.push(arr_temp);
			Sys.stdout().writeString("\n");
		}
	}
}

package;

import cpp.Lib;

import haxe.io.Input;

class Main

{

static function main()

{

var input:Input = Sys.stdin();

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

var ab = new Array<Array<Int>>();

var c = new Array<Array<Int>>();

var d = new Array<Array<Int>>();

var i:Int = 0, j:Int = 0, k:Int = 0;

var input_str:String;

var space_loc:Int;

var arr_temp:Array<Int>;

for (i in 0...n) {

arr_temp = new Array<Int>();

input_str = input.readLine();

for (j in 0...n) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0) {

space_loc = input_str.length;

}

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

if (space_loc != input_str.length) {

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

}

ab.push(arr_temp);

}

for (i in 0...n) {

input_str = input.readLine();

for (j in 0...n) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0) {

space_loc = input_str.length;

}

ab[i][j] += (Std.parseInt(input_str));

if (space_loc != input_str.length) {

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

}

for (i in 0...n) {

arr_temp = new Array<Int>();

input_str = input.readLine();

for (j in 0...n) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0) {

space_loc = input_str.length;

}

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

if (space_loc != input_str.length) {

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

}

c.push(arr_temp);

}

for (i in 0...n) {

arr_temp = new Array<Int>();

for (j in 0...n) {

arr_temp[j] = 0;

for (k in 0...n) {

arr_temp[j] += ab[i][k] * c[k][j];

}

Sys.stdout().writeString(arr_temp[j] + " ");

}

d.push(arr_temp);

Sys.stdout().writeString("\n");

}

Ход решения:

В первом цикле читаем матрицу $A$:

for (i in 0...n) {
	arr_temp = new Array<Int>();
	input_str = input.readLine();
	for (j in 0...n) {
		space_loc = input_str.indexOf(" ");
		if (space_loc == 0) {
			space_loc = input_str.length;
		}
		arr_temp.push(Std.parseInt(input_str));
		if (space_loc != input_str.length) {
			input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
		}
	}
	ab.push(arr_temp);
}

for (i in 0...n) {

arr_temp = new Array<Int>();

input_str = input.readLine();

for (j in 0...n) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0) {

space_loc = input_str.length;

}

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

if (space_loc != input_str.length) {

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

}

ab.push(arr_temp);

}

Во втором цикле считываем элементы матрицы $B$ и сразу прибавляем их к соответствующим элементам матрицы $A$:

for (i in 0...n) {
	input_str = input.readLine();
	for (j in 0...n) {
		space_loc = input_str.indexOf(" ");
		if (space_loc == 0) {
			space_loc = input_str.length;
		}
		ab[i][j] += (Std.parseInt(input_str));
		if (space_loc != input_str.length) {
			input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
		}
	}
}

for (i in 0...n) {

input_str = input.readLine();

for (j in 0...n) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0) {

space_loc = input_str.length;

}

ab[i][j] += (Std.parseInt(input_str));

if (space_loc != input_str.length) {

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

}

В третьем цикле читаем матрицу $C$:

for (i in 0...n) {
	arr_temp = new Array<Int>();
	input_str = input.readLine();
	for (j in 0...n) {
		space_loc = input_str.indexOf(" ");
		if (space_loc == 0) {
			space_loc = input_str.length;
		}
		arr_temp.push(Std.parseInt(input_str));
		if (space_loc != input_str.length) {
			input_str = input_str.substr(space_loc + 1, input_str.length - space_loc);
		}
	}
	c.push(arr_temp);
}

for (i in 0...n) {

arr_temp = new Array<Int>();

input_str = input.readLine();

for (j in 0...n) {

space_loc = input_str.indexOf(" ");

if (space_loc == 0) {

space_loc = input_str.length;

}

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

if (space_loc != input_str.length) {

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

}

c.push(arr_temp);

}

Наконец, в четвертом цикле вычисляем и выводим элементы результирующей матрицы $D = (A + B) * C$:

for (i in 0...n) {
	arr_temp = new Array<Int>();
	for (j in 0...n) {
		arr_temp[j] = 0;
		for (k in 0...n) {
			arr_temp[j] += ab[i][k] * c[k][j];
		}
		Sys.stdout().writeString(arr_temp[j] + " ");
	}
	d.push(arr_temp);
	Sys.stdout().writeString("\n");
}

for (i in 0...n) {

arr_temp = new Array<Int>();

for (j in 0...n) {

arr_temp[j] = 0;

for (k in 0...n) {

arr_temp[j] += ab[i][k] * c[k][j];

}

Sys.stdout().writeString(arr_temp[j] + " ");

}

d.push(arr_temp);

Sys.stdout().writeString("\n");

}

Ссылки:

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

e-olymp 19. The degree of symmetry

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

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

Условие

Степенью симметрии натурального числа назовём количество пар его десятичных цифр, в которых цифры совпадают и расположены симметрично относительно середины десятичной записи этого числа. Если некоторая цифра стоит посередине десятичной записи, её тоже нужно учитывать в паре с ней самой. Найти степень симметрии числа $n$.

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

Одно натуральное число $n < 2 * 20^9$.

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

Вывести степень симметрии числа $n$.

Тесты:

Ввод	Вывод
$123322$	$2$
$100$	$1$
$1010$	$0$
$1234321$	$4$
$1234567891$	$1$

Код на Haxe:

package;

import cpp.Lib;

class Main 
{
	static function main() 
	{
		var n:Int = Std.parseInt(Sys.stdin().readLine());
		var i:Int = 0;
		var count = 0;
		var num = [];
		if (n == 0) {
			num.push(0);
		} else {
			while (n > 0) {
				num.push(n % 10);
				n = Math.floor(n / 10);
			}
		}
		var j:Int = num.length - 1;
		while (i <= j) {
			if (num[i] == num[j]) {
				count++;
			}
			i++;
			j--;
		}
		Sys.stdout().writeString("" + count + "\n");
	}
}

package;

import cpp.Lib;

class Main

{

static function main()

{

var n:Int = Std.parseInt(Sys.stdin().readLine());

var i:Int = 0;

var count = 0;

var num = [];

if (n == 0) {

num.push(0);

} else {

while (n > 0) {

num.push(n % 10);

n = Math.floor(n / 10);

}

var j:Int = num.length - 1;

while (i <= j) {

if (num[i] == num[j]) {

count++;

}

i++;

j--;

}

Sys.stdout().writeString("" + count + "\n");

}

Ход решения:

Вначале считываем число. Затем раскладываем его по цифрам внутри массива (в обратном порядке, но для нашей задачи порядок цифр значения не имеет):

if (n == 0) {
	num.push(0);
} else {
	while (n > 0) {
		num.push(n % 10);
		n = Math.floor(n / 10);
	}
}

if (n == 0) {

num.push(0);

} else {

while (n > 0) {

num.push(n % 10);

n = Math.floor(n / 10);

}

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

var j:Int = num.length - 1;
while (i <= j) {
	if (num[i] == num[j]) {
		count++;
	}
	i++;
	j--;
}
Sys.stdout().writeString("" + count + "\n");

var j:Int = num.length - 1;

while (i <= j) {

if (num[i] == num[j]) {

count++;

}

i++;

j--;

}

Sys.stdout().writeString("" + count + "\n");

Ссылки:

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

MS10. Text encryption

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

Задача взята отсюда.

Условие

Зашифруйте текст из входного потока, заменяя каждый символ результатом сложения по модулю 2 его кода и кода предыдущего зашифрованного символа. Первый символ шифруется инверсией бит.

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

Символьная последовательность.

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

Зашифрованная символьная последовательность.

Тесты :

Входные данные	Выходные данные
Where is the table?	a8 c0 a5 d7 b2 92 fb 88 a8 dc b4 d1 f1 85 e4 86 ea 8f b0
What a nice day!	a8 c0 a1 d5 f5 94 b4 da b3 d0 b5 95 f1 90 e9 c8
Glad to see you!	b8 d4 b5 d1 f1 85 ea ca b9 dc b9 99 e0 8f fa db

Код на Haxe:

package;

import cpp.Int8;
import cpp.Lib;
import haxe.io.Bytes;

class Main 
{
	static function main() 
	{
		var c:Int8 = Sys.stdin().readInt8();
		c = ~c;
		var out:Bytes = Bytes.alloc(1);
		out.setUInt16(0, c);
		Sys.stdout().writeString(out.toHex());
		var c1:Int8;
		while (true) {
			c1 = Sys.stdin().readInt8();
			if (c1 == "\n".charCodeAt(0))
				break;
			c1 = c ^ c1;
			out.setUInt16(0, c1);
			Sys.stdout().writeString(" " + out.toHex());
			c = c1;
		}
		Sys.stdout().writeString("\n");
	}
}

package;

import cpp.Int8;

import cpp.Lib;

import haxe.io.Bytes;

class Main

{

static function main()

{

var c:Int8 = Sys.stdin().readInt8();

c = ~c;

var out:Bytes = Bytes.alloc(1);

out.setUInt16(0, c);

Sys.stdout().writeString(out.toHex());

var c1:Int8;

while (true) {

c1 = Sys.stdin().readInt8();

if (c1 == "\n".charCodeAt(0))

break;

c1 = c ^ c1;

out.setUInt16(0, c1);

Sys.stdout().writeString(" " + out.toHex());

c = c1;

}

Sys.stdout().writeString("\n");

}

Ход решения:

Считываем код первого символа, инвертируем его и выводим в шестнадцатеричной системе счисления:

var c:Int8 = Sys.stdin().readInt8();
c = ~c;
var out:Bytes = Bytes.alloc(1);
out.setUInt16(0, c);
Sys.stdout().writeString(out.toHex());

var c:Int8 = Sys.stdin().readInt8();

c = ~c;

var out:Bytes = Bytes.alloc(1);

out.setUInt16(0, c);

Sys.stdout().writeString(out.toHex());

Вводим вторую переменную и запускаем цикл, который будет работать, пока считывание не дойдет до переноса строки. Здесь мы считываем код очередного символа, складываем его по модулю 2 с шифром предыдущего символа, выводим через пробел шестнадцатеричное представление полученного кода и записываем этот код в первую переменную:

var c1:Int8;
while (true) {
	c1 = Sys.stdin().readInt8();
	if (c1 == "\n".charCodeAt(0))
		break;
	c1 = c ^ c1;
	out.setUInt16(0, c1);
	Sys.stdout().writeString(" " + out.toHex());
	c = c1;
}

var c1:Int8;

while (true) {

c1 = Sys.stdin().readInt8();

if (c1 == "\n".charCodeAt(0))

break;

c1 = c ^ c1;

out.setUInt16(0, c1);

Sys.stdout().writeString(" " + out.toHex());

c = c1;

}

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

Sys.stdout().writeString("\n");

27	Sys.stdout().writeString("\n");

Ссылки:

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

e-olymp 109. Numeration

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

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

Условие

Для нумерации $M$ страниц книги использовали $N$ цифр. По заданному $N$ вывести $M$ или $0$, если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число $N$. В книге не более $1001$ страницы.

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

Искомое количество страниц.

Тесты :

$N$	$8$	$21$	$22$	$113$	$999$	$1001$
$M$	$8$	$15$	$0$	$61$	$369$	$0$

Код на Haxe:

class Test {
    public var n:Int;
        
    public function new(n) {
        this.n = n;
    }
    
    static function main() {
        var tests = new Array();
        tests.push(new Test(8));
        tests.push(new Test(21));
        tests.push(new Test(22));
        tests.push(new Test(113));
        tests.push(new Test(999));
        tests.push(new Test(1001));
        var i:Test;
        for (i in tests) {
            var n:Int = i.n;
            var m:Int = 0;
            while (n > 0) {
                m++;
                if (m < 10) {	//1 digit
                    n -= 1;
                } else if (m < 100) {	//2 digits
                    n -= 2;
                } else if (m < 1000) {	//3 digits
                    n -= 3;
                } else {	//4 digits
                    n -= 4;
                }
                if (n < 0) {
                    m = 0;
                }				
            }
            trace(m);
        }
    }
}

class Test {

public var n:Int;

public function new(n) {

this.n = n;

}

static function main() {

var tests = new Array();

tests.push(new Test(8));

tests.push(new Test(21));

tests.push(new Test(22));

tests.push(new Test(113));

tests.push(new Test(999));

tests.push(new Test(1001));

var i:Test;

for (i in tests) {

var n:Int = i.n;

var m:Int = 0;

while (n > 0) {

m++;

if (m < 10) { //1 digit

n -= 1;

} else if (m < 100) { //2 digits

n -= 2;

} else if (m < 1000) { //3 digits

n -= 3;

} else { //4 digits

n -= 4;

}

if (n < 0) {

m = 0;

}

trace(m);

}

Ход решения:

Принимаем исходное количество страниц $M$ как $0$ и увеличиваем его в начале каждой итерации цикла. Цикл будет идти, пока мы не исчерпаем заданное количество цифр $N$, вычитаем необходимое их количество в зависимости от $M$:

var m:Int = 0;
while (n > 0) {
    m++;
    if (m < 10) {	//1 digit
        n -= 1;
    } else if (m < 100) {	//2 digits
        n -= 2;
    } else if (m < 1000) {	//3 digits
        n -= 3;
    } else {	//4 digits
        n -= 4;
    }

var m:Int = 0;

while (n > 0) {

m++;

if (m < 10) { //1 digit

n -= 1;

} else if (m < 100) { //2 digits

n -= 2;

} else if (m < 1000) { //3 digits

n -= 3;

} else { //4 digits

n -= 4;

}

Далее проверяем условие корректности исходных данных: если мы получили отрицательное значение $N$, значит, исходное его значение также было неверным, тогда количеству страниц присваиваем $0$:

if (n < 0) {
    m = 0;
}

if (n < 0) {

m = 0;

}

Выйдя из цикла, выводим $M$:

trace(m);

trace(m);

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

Ссылки:

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

e-olymp 4. Two circles

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

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

Условие

Определить количество точек пересечения двух окружностей.

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

Шесть чисел: $x_1$, $y_1$, $r_1$, $x_2$, $y_2$, $r_2$, где $x_1$, $y_1$, $x_2$, $y_2$ — координаты центров окружностей, а $r_1$, $r_2$ — их радиусы. Все числа — действительные, не превышают $10^9$, заданы не более чем с тремя знаками после запятой.

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

Количество точек пересечения. Если точек пересечения бесконечно много, то вывести $-1$.

Тесты:

$X_1$	$Y_1$	$R_1$	$X_2$	$Y_2$	$R_2$	$N$
0	0	5	5	0	1	2
0	0	5	0	0	6	0
0	1	6	0	3	6	2

Код на Haxe:

class Test {
    public var x1:Float;
    public var y1:Float;
    public var r1:Float;
    public var x2:Float;
    public var y2:Float;
    public var r2:Float;
    
    public function new(x1,y1,r1,x2,y2,r2) {
        this.x1 = x1;
        this.y1 = y1;
        this.r1 = r1;
        this.x2 = x2;
        this.y2 = y2;
        this.r2 = r2;
    }
    
    static function main() {
        var tests = new Array();
        tests.push(new Test(0, 0, 5, 5, 0, 1));
        tests.push(new Test(0, 0, 5, 0, 0, 6));
        tests.push(new Test(0, 1, 6, 0, 3, 6));
        var i:Test;
        for (i in tests) {
            var x1:Float = i.x1;
            var y1:Float = i.y1;
            var r1:Float = i.r1;
            var x2:Float = i.x2;
            var y2:Float = i.y2;
            var r2:Float = i.r2;
            
            var range_sqr:Float = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
            var rads_sqr:Float = (r1 + r2) * (r1 + r2);
            var D:Int;
            
            if (range_sqr == 0 && r1 == r2) {
                D = -1;
            }
            else if (range_sqr == rads_sqr || range_sqr == (r2 - r1) * (r2 - r1) || range_sqr == (r1 - r2) * (r1 - r2)) {
                D = 1;
            }
            else if ((range_sqr > rads_sqr) || ((range_sqr < rads_sqr) && ((range_sqr < r1 * r1 / 4 && range_sqr < (r1 - r2) * (r1 - r2)) || (range_sqr < r2 * r2 / 4 && range_sqr < (r2 - r1) * (r2 - r1))))) {
                D = 0;
            }
            else {
                D = 2;
            }
            trace(D); 
        }
    }
}

class Test {

public var x1:Float;

public var y1:Float;

public var r1:Float;

public var x2:Float;

public var y2:Float;

public var r2:Float;

public function new(x1,y1,r1,x2,y2,r2) {

this.x1 = x1;

this.y1 = y1;

this.r1 = r1;

this.x2 = x2;

this.y2 = y2;

this.r2 = r2;

}

static function main() {

var tests = new Array();

tests.push(new Test(0, 0, 5, 5, 0, 1));

tests.push(new Test(0, 0, 5, 0, 0, 6));

tests.push(new Test(0, 1, 6, 0, 3, 6));

var i:Test;

for (i in tests) {

var x1:Float = i.x1;

var y1:Float = i.y1;

var r1:Float = i.r1;

var x2:Float = i.x2;

var y2:Float = i.y2;

var r2:Float = i.r2;

var range_sqr:Float = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);

var rads_sqr:Float = (r1 + r2) * (r1 + r2);

var D:Int;

if (range_sqr == 0 && r1 == r2) {

D = -1;

}

else if (range_sqr == rads_sqr || range_sqr == (r2 - r1) * (r2 - r1) || range_sqr == (r1 - r2) * (r1 - r2)) {

D = 1;

}

else if ((range_sqr > rads_sqr) || ((range_sqr < rads_sqr) && ((range_sqr < r1 * r1 / 4 && range_sqr < (r1 - r2) * (r1 - r2)) || (range_sqr < r2 * r2 / 4 && range_sqr < (r2 - r1) * (r2 - r1))))) {

D = 0;

}

else {

D = 2;

}

trace(D);

}

Ход решения:

Высчитываем расстояние между центрами окружностей по формуле: $Range = \sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2}$ (храниться и обрабатываться оно будет в квадрате). Вычисление в одну строку:

var range_sqr:Float = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);

32	var range_sqr:Float = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);

Далее рассчитываем сумму радиусов окружностей (также в квадрате).
Если центры совпадают ($Range = 0$) и длины радиусов равны, значит, совпадают и окружности:

if (range_sqr == 0 && r1 == r2) {
    D = -1;
}

if (range_sqr == 0 && r1 == r2) {

D = -1;

}

Если расстояние между окружностями равно сумме радиусов, окружности имеют одну общую точку, касаясь друг друга снаружи. Также одна из окружностей может лежать внутри другой и касаться ее изнутри:

else if (range_sqr == rads_sqr || range_sqr == (r2 - r1) * (r2 - r1) || range_sqr == (r1 - r2) * (r1 - r2)) {
    D = 1;
}

else if (range_sqr == rads_sqr || range_sqr == (r2 - r1) * (r2 - r1) || range_sqr == (r1 - r2) * (r1 - r2)) {

D = 1;

}

Если расстояние между окружностями превышает сумму радиусов, это значит, что они не пересекаются. Также одна окружность может лежать внутри другой, но не касаться ее:

else if ((range_sqr > rads_sqr) || ((range_sqr < rads_sqr) && ((range_sqr < r1 * r1 / 4 && range_sqr < (r1 - r2) * (r1 - r2)) || (range_sqr < r2 * r2 / 4 && range_sqr < (r2 - r1) * (r2 - r1))))) {
    D = 0;
}

else if ((range_sqr > rads_sqr) || ((range_sqr < rads_sqr) && ((range_sqr < r1 * r1 / 4 && range_sqr < (r1 - r2) * (r1 - r2)) || (range_sqr < r2 * r2 / 4 && range_sqr < (r2 - r1) * (r2 - r1))))) {

D = 0;

}

В остальных случаях окружности пересекаются и имеют две общие точки:

else {
    D = 2;
}

else {

D = 2;

}

Ссылки:

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

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 !

5.13. Цикл for

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

По материалам официального руководства по Haxe 3

Haxe не поддерживает традиционные циклы $for$ из языка C. Здесь ключевое слово $for$ предполагает следующий синтаксис: вначале идет открывающая скобка $($, затем идентификатор переменной, ключевое слово $in$ и произвольное выражение, используемое в качестве итерационной коллекции. После закрывающей скобки $)$ следует тело цикла.

for (v in e1) e2;

1	for (v in e1) e2;

Программист при написании кода гарантирует, что тип $e1$ является итерируемым. Обычно это происходит в случае, если он содержит метод типа $iterator$, возвращающий $Iterator<T>$, или если он сам — $Iterator<T>$.

Переменная $v$ доступна внутри тела цикла $e2$ и хранит значения отдельных элементов коллекции $e1$.

У Haxe есть специальный оператор диапазона для итерации в пределах интервалов. Это бинарный оператор, который получает на вход два операнда типа $Int$: $min…max$, который возвращает экземпляр $IntIterator$, который итерирует от $min$ (включительно) до $max$ (не включительно). Отметим, что $max$ не должен быть меньше $min$.

for (i in 0...10) trace(i); //0 to 9

1	for (i in 0...10) trace(i); //0 to 9

Тип выражения $for$ — всегда $Void$, что означает, что оно не имеет собственного значения и не может быть использовано в качестве правой части выражения.

На управляющий поток цикла можно повлиять при помощи выражений $break$ и $continue$.

В общем, можно сказать, что цикл $for$ в Haxe напоминает циклы $foreach$ в некоторых других языках.

Пример: Программа, которая вычисляет и выводит значения $2^i$, где $i$ изменяется от 1 до 20.

class Test {
    static function main() {
        var a: Int = 1;
        for (i in 1...21) {
            a *= 2;
            trace(a);
        };
    }
}

class Test {

static function main() {

var a: Int = 1;

for (i in 1...21) {

a *= 2;

trace(a);

};

}

Протестировать код можно здесь: Try Haxe !

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