e-olimp 3966. An ardent collector of butterflies

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

Ход решения:

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

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

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

Ссылки:

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

e-olymp 1078. The line degree

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

Ход решения:

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

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

Ссылки:

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

A704

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

Условие

Даны квадратные матрицы с целыми числами $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:

Ход решения:

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

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

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

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

Ссылки:

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

e-olymp 19. The degree of symmetry

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

Условие

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

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

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

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

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

Тесты:

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

Код на Haxe:

Ход решения:

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

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

Ссылки:

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

MS10. Text encryption

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

Условие

Зашифруйте текст из входного потока, заменяя каждый символ результатом сложения по модулю 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:

Ход решения:

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

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

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

Ссылки:

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

e-olymp 109. Numeration

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

Ход решения:

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

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

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

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

Ссылки:

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

e-olymp 4. Two circles

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

Ход решения:

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

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

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

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

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

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

Ссылки:

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

e-olymp 57. Butterfly-orderly

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

Ход решения:

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

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

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

Ссылки:

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

5.13. Цикл for

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

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

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

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

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

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

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

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

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

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