e-olymp 128. Счастливые билеты

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

Задача

Подсчитайте количество счастливых билетов, у которых сума первых трёх цифр равна [latex]N[/latex].

Счастливым билетом называется билет с шестизначным номером, у которого сумма первых трёх цифр равна сумме трёх последних.

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

В единственной строке задано натуральное число [latex] N (N ≤ 27). [/latex]

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

Единственное число — количество счастливых билетов.

Тесты

Входные данные (число [latex] N [/latex]) Выходные данные (число билетов)
1. 1 9
2. 27 1
3. 0 1
4. 10 3969
5. 3 100

Код программы

Решение
Любой шестизначный номер можно представить как 2 трехзначных номера.

Для решения задачи рассмотрим все варианты трехзначных номеров. Две первые цифры такого номера могут быть любыми. Переберем все их комбинации с помощью двух  циклов. А для определения третьей цифры будем использовать специальное условие. Она должна быть результатом вычитания двух первых цифр из [latex]N[/latex], и быть именно цифрой, то есть меньше 10.

Когда в цикле встречается подходящая комбинация, счетчик [latex]c[/latex] увеличивается на 1. Так как номер шестизначный, а счетчик [latex]c[/latex] подсчитывает удачные комбинации для трехзначного числа первой части, то и для трехзначного числа второй части он будет соответствовать. Следовательно, окончательное число комбинаций будет равно [latex]c \cdot c[/latex].

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

e-olymp 916. Интересное произведение

Ссылка на оригинальную статью
Ссылка на e-olymp.com.

Задача
Определить все возможные значения произведения $i·j$, если целочисленные значения переменных $i$ и $j$ меняются соответственно $i$ от $a$ до $b$ и $j$ от $c$ до $d (1 ≤ a, b, c, d ≤ 10)$.

Входные данные
В одной строке заданы $4$ числа $a, b, c$ и $d$ ($a$ может быть больше $b$, $c$ может быть больше $d$).

Выходные данные
Вывести количество возможных вариантов произведения.

Тесты

Входные данные Выходные данные
1 1 10 1 10 42
2 5 7 4 3 6
3 6 3 8 4 16
4 2 8 4 1 19

Код

Решение
Для начала присваивается $a$ и $c$ минимальные значения из пары, а $b$ и $d$ — максимальные. Переменной $p$ присваивается произведение минимальных значений, а $i$ присваивается минимальное значение из первой пары. Далее в цикле проверяется делится ли число $p$, которое находится в диапазоне от произведения минимальных значений до произведения максимальных, на $i$ и $j$. Если условие выполняется, то временной переменной присваивается единица, а счетчик (результат) увеличивается на $1$.

e-olymp 60. Площадь многоугольника

Задача e-olymp 60.
Тест на tryHaxe.

Условие задачи

Заданы координаты [latex] n [/latex] последовательных вершин многоугольника. Определить его площадь.

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

Первая строка содержит количество вершин многоугольника [latex] n [/latex]. В следующих [latex] n [/latex] строках через пробел заданы целочисленные координаты его последовательных вершин [latex] x_i, y_i. [/latex] Известно, что [latex] 3≤n≤1000,−1000≤x[i],y[i]≤1000.[/latex]

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

Площадь многоугольника [latex] S [/latex].

Тесты

Входные данные Выходные данные
3, (0, 0), (0, 2), (2, 0) 2
4, (-1000, 500), (-500, 1000), (2, 10), (35, 60) 339865
5, (13, -92), (44, 0), (-800, 30), (27, 2), (1, 2) 1446.000

Для подсчёта площади необходима специальная формула которую можно найти тут а так же некоторое её обоснование.

e-olymp 5072. Подсчет количества ребер

Задача

Ориентированный граф задан матрицей смежности.
Найдите количество ребер в графе.

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

Входной файл содержит число n (1n 100) — число вершин в графе, и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

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

Выведите в выходной файл количество ребер заданного графа.

Решение

30 1 11 0 1

0 1 1

6
50 1 1 1 11 0 0 0 0

1 0 0 0 0

0 0 1 0 1

1 0 0 0 0

9
21 11 1 4

Алгоритм решения

Количество ребер ориентированного графа равно количеству единиц в его матрице смежности. Поэтому просто считываем, суммируем найденные 1-цы, и выводим ответ.

Выполнение кода на Try Haxe !
Решение задачи на С++.

e-olymp 127. Баксы в банке

Ссылка на оригинальную статью
Ссылка на e-olymp
Ссылка на Try Haxe!

Задача
Папа Карло подарил Буратино 1 доллар в его первый день рождения, а экономный Буратино сложил подарок в банку. Каждый последующий год папа Карло удваивал свой предыдущий подарок и прибавлял к нему столько долларов, сколько лет исполнилось Буратино, а тот в свою очередь продолжал складывать баксы в банку. На какой $N$-й день рождения в банке будет не менее, чем $S$ долларов?

Входные данные
Единственное число — значение $S$ ([latex]1 \le S \le 240[/latex]).

Выходные данные
Искомое значение $N$.

Тесты

Входные данные Выходные данные
15 3
25 4
9 3
99 5
199 6
333 7

Код

Решение
В данной задаче $sum$ — сколько долларов в банке, $p$ — сколько долларов Папа Карло подарил Буратино. Пока $s > sum$ мы инкрементируем $n$ и считаем сколько Папа Карло подарит Буратино $p = p * 2 + n$ и суммируем его с тем что лежит в банке — $sum += p$. После этого в выходной поток подаётся $n$.

Алгоритм шифрования MARS

MARS — шифр-кандидат в AES был разработан коллективом криптологов из корпорации IBM. Именно IBM в свое время разработала семейство алгоритмов Lucifer, которое легло в основу прошлого стандарта шифрования США — DES.

Cтруктура алгоритма:

  1. Предварительное наложение ключа: на [latex]32[/latex]-битные субблоки [latex]A, B, C, D[/latex] накладываются [latex]4[/latex] фрагмента расширенного ключа [latex]k_{0}…k_{3}[/latex] операцией сложения по модулю [latex]2^{32}[/latex];
  2. Выполняются [latex]8[/latex] раундов прямого перемешивания (без участия ключа шифрования);
  3. Выполняются [latex]8[/latex] раундов прямого криптопреобразования;
  4. Выполняются [latex]8[/latex] раундов обратного криптопреобразования;
  5. Выполняются [latex]8[/latex] раундов обратного перемешивания, также без участия ключа шифрования;
  6. Финальное наложение фрагментов расширенного ключа [latex]k_{36}…k_{39}[/latex] операцией вычитания по модулю [latex]2^{32}[/latex].

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

  • простейшие операции сложение, вычитание, исключающее или
  • подстановки с использованием таблицы замен
  • фиксированный циклический сдвиг
  • зависимый от данных циклический сдвиг
  • умножение по модулю [latex]2^{32}[/latex]
  • ключевое забеливание
Следовательно, для реализации алгоритма было бы удобно завести некоторую «обертку» над [latex]32[/latex] битным интом (поскольку мы оперируем [latex]32[/latex]-битными субблоками).

Нам понадобится реализовать:

  • циклический сдвиг влево/вправо на [latex]n[/latex]-ое кол-во бит
  • выделение [latex]n[/latex]-ого байта из субблока
  • выделение последних [latex]n[/latex] бит из субблока

Реализуем новый абстрактный тип Integer (прежде стоит ознакомиться с логическими операциями):

Добавим методы циклического сдвига:

Для наглядности подробно разберем принцип работы одного из методов, основанных на битовых операциях, для краткости возьмем не [latex]32[/latex]-битное число, а [latex]8[/latex]-битное. Пусть нам нужен циклический сдвиг влево на [latex]4[/latex] бита.
Из этого следует что, нам нужно сдвинуть входное число на [latex]4[/latex] бита влево, предварительно сохранив [latex]4[/latex] старших бита, чтобы не потерять их. Для этого воспользуемся операцией сдвига вправо на [latex]n — 4[/latex] бита с заполнением нулями, где [latex]n[/latex] — максимальное кол-во бит в числе. Сохраним результат  в переменную  ones  .
Далее сдвинем исходное слово на [latex]4[/latex] бита влево и операцией «побитовое или» соединим с   ones.
Аналогично реализуем метод циклического сдвига вправо:

Так же нам потребуется реализовать метод выделения [latex]n[/latex]-ого байта из субблока. Для этого мы будем сдвигать требуемый байт на место младшего байта и выделим его с помощью операции «логическое и» маской [latex]255[/latex] (в битовом представлении подряд идущих [latex]8[/latex] единиц, начиная с младшего бита) .

Осталось реализовать метод выделения последних [latex]n[/latex] бит из субблока. Для этого мы сначала сдвинем число влево на ([latex]32 — n[/latex]), чтобы на место старших бит встали искомые биты (таким образом стерев ненужные биты). А затем сдвинем их на место младших битов (то есть вправо с заполнением нулями на [latex]32 — n[/latex]).

Для работы алгоритма потребуется объявить некоторые элементы ([latex]S[/latex] и [latex]B[/latex] блоки) — они описаны в конце статьи.

Прямое перемешивание:

Раунд прямого перемешивания показан на рисунке [latex]1[/latex], в раунде выполняются следующие действия:

  1. Значение субблока [latex]A[/latex] прогоняется через таблицу замен [latex]S0[/latex] и накладывается на субблок [latex]B[/latex] операцией [latex]XOR[/latex].
  2. Исходное значение субблока [latex]A[/latex] вращается на [latex]8[/latex] бит вправо.
  3. Результат предыдущего шага обрабатывается таблицей замен [latex]S1[/latex] и снова накладывается на субблок [latex]B[/latex] операцией сложения по модулю [latex]32[/latex].
  4. Результат шага [latex]2[/latex] вращается на [latex]8[/latex] бит вправо.
  5. Результат предыдущего шага обрабатывается таблицей замен [latex]S0[/latex] и накладывается на субблок [latex]С[/latex] операцией сложения по модулю [latex]32[/latex].
  6. Результат шага [latex]4[/latex] вращается на [latex]8[/latex] бит вправо.
  7. Результат предыдущего шага обрабатывается таблицей замен [latex]S1[/latex] и накладывается на субблок [latex]D[/latex] операцией [latex]XOR[/latex].
  8. Субблоки меняются местами, как показано на рис. [latex]1[/latex].

Кроме того, в некоторых раундах прямого перемешивания выполняются следующие дополнительные операции (не приведены на рис. [latex]1[/latex]):
В раундах [latex]0[/latex] и [latex]4[/latex] после шага [latex]7[/latex] выполняется наложение значения субблока [latex]D[/latex] на субблок [latex]A[/latex] операцией сложения по модулю .
В раундах [latex]1[/latex] и [latex]5[/latex] субблок [latex]B[/latex] аналогичным образом накладывается на субблок [latex]A[/latex].


рис. 1.

Стоит заметить, что каждый раз, «прогоняя» [latex]i[/latex]-ий субблок через [latex]S[/latex] блоки мы берем последние [latex]8[/latex] бит, то есть байт субблока и его значение используем в качестве индексного обращения к блоку [latex]S[/latex]. (Понятно, что в блоках [latex]256[/latex]  элементов. О правилах их получения  рассказывается ниже).

Для простоты, мы будем возвращать для «прогона» каждый раз не последний байт, а младший, первый, второй и старший. Потом мы подвинем субблок вправо сразу на [latex]24[/latex] бита.

Заведем класс subblock, который будет содержать четыре [latex]32[/latex]-битные посылки и расширенный ключ (о его получении мы поговорим ниже).

Теперь добавим в него метод прямого перемешивания:

Процесс кодирования алгоритма Mars обратен процессу декодирования. По этому сразу добавим обратный метод. Назовем его backward pass, чтобы не менять порядок следования функции в методе дешифрования, и добавим, в начало названия префикс [latex]d[/latex], чтобы обозначить его принадлежность к методам декодирования. Стоит отметить, что перед этим стоит ознакомиться с понятием обратных операций.

Криптографическое преобразование:

Криптографическое ядро MARS — сеть Фейстеля 3-го типа, содержащая в себе [latex]16[/latex] раундов. [latex]8[/latex] раундов прямого (рис. 2) и [latex]8[/latex] раундов обратного криптопреобразования (рис. 3). В каждом раунде мы используем ключевую [latex]Е[/latex]-функцию, которая является комбинацией умножений, вращений, а также обращений к [latex]S[/latex]-блокам. Функция принимает на вход одно слово данных, а возвращает три слова, с которыми впоследствии будет осуществлена операция сложения или [latex]XOR[/latex] к другим трем словам данным. В дополнении исходное слово вращается на [latex]13[/latex] бит влево.

рис.2.

Для обеспечения, серьёзного сопротивления к криптоатакам, три выходных значения [latex]Е[/latex]-функции ([latex]O_{1}[/latex], [latex]O_{2}[/latex], [latex]O_{3}[/latex]) используются в первых восьми раундах и в последних восьми раундах в разных порядках. В первые восемь раундов мы добавляем [latex]O_{1}[/latex] и [latex]O_{2}[/latex] к первому и второму целевому слову, соответственно, и [latex]XOR[/latex] [latex]O_{3}[/latex] к третьему целевому слову. За последние восемь раундов, мы добавляем [latex]O_{1}[/latex] и [latex]O_{2}[/latex] к третьему и второму целевому слову, соответственно, и [latex]XOR[/latex] [latex]O_{3}[/latex] к первому целевому слову.

рис.3.

Для декодирования:

 

[latex]E[/latex]-функция

[latex]E[/latex]-функция принимает в качестве входных данных одно слово данных и использует ещё два слова расширенного ключа с индексами [latex]2*i + 4[/latex] и [latex]2*i + 5[/latex] , производя на выходе три слова. В этой функции мы используем три временные переменные, обозначаемые [latex]L[/latex], [latex]M[/latex] и [latex]R[/latex] (для левой, средней и правой).

<p\>Изначально мы устанавливаем в [latex]R[/latex] значение исходного слова смещенного на [latex]13[/latex] бит влево, а в [latex]M[/latex] — сумма исходных слов и первого ключевого слова. Затем мы используем первые девять битов [latex]M[/latex] как индекс к одной из [latex]512[/latex] [latex]S[/latex]-блоков (которое получается совмещением [latex]S0[/latex] и [latex]S1[/latex] смешиванием фазы), и сохраняем в [latex]L[/latex] значение соответствующего [latex]S[/latex]-блока.

Затем умножим второе ключевое слово на [latex]R[/latex], сохранив значение в [latex]R[/latex]. Затем вращаем [latex]R[/latex] на [latex]5[/latex] позиций влево (так, [latex]5[/latex] старших битов становятся [latex]5[/latex] нижними битами [latex]R[/latex] после вращения). Тогда мы делаем [latex]XOR[/latex] [latex]R[/latex] в [latex]L[/latex], а также просматриваем пять нижних бит [latex]R[/latex] для определения величины сдвига (от [latex]0[/latex] до [latex]31[/latex]), и вращаем [latex]M[/latex] влево на эту величину. Далее мы вращаем [latex]R[/latex] ещё на [latex]5[/latex] позиций влево и делаем [latex]XOR[/latex] в [latex]L[/latex]. В заключении, мы вновь смотрим на [latex]5[/latex] младших битов [latex]R[/latex], как на величину вращения и вращаем [latex]L[/latex] на эту величину влево. Таким образом результат работы [latex]E[/latex]-функции — [latex]3[/latex] слова (по порядку): [latex]L, M, R[/latex].

 

Обратное перемешивание:

Раунд обратного перемешивания (см. рис. 4) более существенно отличается от прямого. Фактически, обратное перемешивание выполняет обратные операции в обратной последовательности (см. рис. 1 и 4):

  1. Значение субблока [latex]A[/latex] прогоняется через таблицу замен [latex]S1[/latex] и накладывается на субблок [latex]B[/latex] операцией XOR.
  2. Исходное значение субблока [latex]A[/latex] вращается на [latex]8[/latex] бит влево.
  3. Результат предыдущего шага обрабатывается таблицей замен [latex]S0[/latex] и накладывается на субблок [latex]C[/latex] операцией вычитания по модулю [latex]2^{32}[/latex]/>.
  4. Результат шага [latex]2[/latex] вращается на [latex]8[/latex] бит влево.
  5. Результат предыдущего шага обрабатывается таблицей замен [latex]S1[/latex] и накладывается на субблок [latex]D[/latex] операцией вычитания по модулю [latex]2^{32}[/latex] />.
  6. Результат шага [latex]4[/latex] вращается на [latex]8[/latex] бит влево.
  7. Результат предыдущего шага обрабатывается таблицей замен [latex]S0[/latex] и накладывается на субблок [latex]D[/latex] операцией [latex]XOR[/latex].
  8. Субблоки меняются местами, как показано на рис. 4.

Аналогично прямому перемешиванию, в некоторых раундах выполняются следующие дополнительные операции, не показанные на рис. 4:
— В раундах [latex]1[/latex] и [latex]5[/latex] после шага [latex]7[/latex] выполняется наложение значения субблока [latex]A[/latex] на субблок [latex]B[/latex] операцией вычитания по модулю [latex]2^{32}[/latex].

— В раундах [latex]2[/latex] и [latex]6[/latex] субблок [latex]C[/latex] аналогичным образом накладывается на субблок [latex]B[/latex].

и для декодирования:

Финальная реализиция класса Block:

Добавив методы для сложения посылок с подключами мы получаем финальную реализацию класса Block.

 

Свойства [latex]S[/latex]-блоков:

Стоит отметить, что [latex]S[/latex]-блок — это конкатенация блоков [latex]S0[/latex] и [latex]S1[/latex].

  1. [latex]S[/latex]-блок не должен содержать слова, состоящие все [latex]0[/latex] или [latex]1[/latex]
  2. Каждые два [latex]S[/latex]-блока [latex]S0[/latex], [latex]S1[/latex] должны отличаться друг от друга как минимум в [latex]3[/latex] из [latex]4[/latex] байтах.(так как выполнение этого условия для псевдослучайных [latex]S[/latex]-блоков крайне маловероятно, то один из двух [latex]S[/latex]-блоков модифицируется)
  3. S-блок не содержит двух элементов [latex]S[i],S[j](i\neq j)[/latex] таких, что [latex] S\left[i\right]=S\left[j\right][/latex]; [latex]S\left[i\right]=-S\left[j\right][/latex] или [latex] S\left[i\right]=-S\left[j\right][/latex]
  4. В [latex]S[/latex]-блоке не существует двух пар элементов [latex]XOR[/latex]-отличия которых равны и двух пар элементов упорядоченная разность которых равна
  5. Каждые два элемента [latex]S[/latex]-блока должны отличаться хотя бы [latex]4[/latex] битами

В данном программе будем использовать блок, предложенный в реализации IBM для AES.

Расширение ключа:

Процедура расширения ключа расширяет заданный массив ключей [latex]T[][/latex], состоящий из [latex]n[/latex] [latex]32[/latex]-битных слов (где [latex]n[/latex] целое число от [latex]4[/latex] до [latex]14[/latex]) в массив [latex]K[][/latex] из [latex]40[/latex] элементов. Исходный ключ не должен придерживаться какой-либо структуры. В дополнение, процедура расширения ключа гарантирует следующие свойства ключевого слова, используемого при перемножении в криптографическом ядре алгоритма:

  • два младших бита ключевого слова будут всегда единицами
  • ни одно из ключевых слов не будет содержать десять подряд идущих [latex]0[/latex] или [latex]1[/latex]

Опишем алгоритм расширения ключа.

Сначала массив [latex]T[][/latex] дополняется до 15 элементов следующим образом: [latex]T[n]=n[/latex];[latex]T[n+1\ldots 14]=0[/latex]

 

Далее данный процесс повторяется [latex]4[/latex] раза:

    • На каждой итерации генерируются [latex]10[/latex] слов расширенного ключа. [latex]j[/latex] переменная отображающая текущий номер итерации.(для первой итерации [latex]0[/latex], для второй [latex]1[/latex] и т. д.)
      Массив [latex]T[][/latex] преобразуется по следующему правилу: [latex]i=0\ldots 14,T[i]=T[i]\oplus ((T[i-7\mod 15]\oplus T[i-2\mod 15])\lll 3)\oplus (4i+j)[/latex]

 

    • Далее мы перемешиваем массив [latex]T[][/latex] при помощи [latex]4[/latex] раундов Сети Фейстеля 1-го типа. Повторяем четыре раза следующую операцию: [latex]T[i]=(T[i]+S[low~9~bits~of~T[i-1\mod 15]])\lll 9;i=0,1\ldots 14[/latex]

 

  • Далее берем десять слов из массива [latex]T[][/latex] и вставляем их в качестве следующих десяти слов в массив [latex]K[][/latex] ещё раз перемешав: [latex]K[10j+i]=T[4i\mod 15];i=0,1\ldots 9[/latex]

Окончательно, мы пробегаемся по шестнадцати словам, используемыми для перемножения[latex](K[5],K[7]…K[35])[/latex] и модифицируем их для того, чтобы они соответствовали двум свойствам, описанным выше.
Записываем два младших бита [latex]K[i][/latex], по формуле [latex] j=K[i]\land 3[/latex] , а затем записываем вместо этих двух бит единицы, [latex] w=K[i]\lor 3[/latex] .
Собираем маску [latex]M[/latex] для битов [latex]w[/latex], которые принадлежат последовательностям из десяти и более нулей или единиц. К примеру, [latex] M_{l}=1[/latex] , тогда и только тогда, когда [latex]w_{l}[/latex] принадлежит последовательности из [latex]10[/latex] или более одинаковых элементов. Тогда мы сбрасываем (выставляем их в [latex]0[/latex]) значения тех единиц [latex]M[/latex], которые находятся на границах нулевых или единичных последовательностей, а также тех единиц, которые находятся в старшем и младшем битах. К примеру, пусть наше слово выглядит так: [latex] w=0^{3}1^{13}0^{12}1011[/latex] (выражение [latex]0^{i}[/latex] или же [latex] 1^{i}[/latex] обозначает, что [latex]0[/latex] или [latex]1[/latex] будут повторены в слове [latex]i[/latex] раз). Тогда маска [latex]M[/latex] будет выглядеть следующим образом: [latex] 0^{3}1^{25}0^{4}[/latex] . А значит мы сбрасываем биты в [latex]4, 15, 16, 28[/latex] позициях, то есть [latex]M=0^{4}1^{11}001^{10}0^{5}[/latex]
Далее, для исправления, мы используем таблицу из четырёх слов [latex]B[][/latex]. Все элементы таблицы [latex]B[/latex] подобраны так, что для них и для всех их цикличных сдвигов выполняется свойство, что в них нет семи подряд идущих [latex]0[/latex] или [latex]1[/latex]. В реализации IBM использовалась таблица [latex]B[]=\left\{0xa4a8d57b,0x5b5d193b,0xc8a8309b,0x73f9a978\right\}[/latex] . Далее используются два записанных бита [latex]j[/latex] для выбора слова из таблицы [latex]B[/latex], и используются младшие пять бит слова [latex]K[i-1][/latex] для вращения его элементов, [latex]p=B[j]\lll (lowest~5~bits~of~K[i-1])[/latex].
Окончательно, делается [latex]XOR[/latex] шаблона [latex]p[/latex] на исходное слово, при учете маски [latex]М[/latex]: [latex]K[i] = w\oplus (p\land M)[/latex] .

Сначала выделяем маской последовательность из [latex]10[/latex] нулей или единиц, и потом выставляем в маске [latex]1[/latex]-цы пока последовательность не прерывается.

Реализация класса Key:

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

Осталась последняя проблема, наш алгоритм кодирует только массивы из целочисленных [latex]32[/latex] битных элементов, а хотелось бы сообщения. Исправить эту ситуацию помогут следующие функции:

[latex]S0[/latex], [latex]S1[/latex], [latex]B[/latex] блоки я хранила в классе   MarsInfo, где все поля были статическими:

 

try MARS online

e-olymp 1154. Кружок хорового пения

Условие задачи:

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex] -й для распевки поёт гамму.

Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]M[/latex] и [latex]N[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]M[/latex] и [latex]N[/latex].

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

Для каждого тестового случая в отдельной строке выведите «Yes», если в разминке примут участие все участники хора, в противном случае выведите «No».

Тесты:

n m answer
 4   1  Yes
 6   3  No

Код:

Ход решения:

Для начала нам надо найти наибольший общий делитель (НОД). Для этого хорошо подойдет алгоритм Евклида и если НОД равен единице, то все ученики распоются и на выходе подаётся «Yes», иначе «No».

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 !

А119(а)

Задача

Вычислить бесконечную сумму с заданной точностью $ \varepsilon \left(\varepsilon > 0\right) $. Считать, что требуемая точность достигнута, если очередное слагаемое оказалось по модулю меньше, чем $ \varepsilon $.

$$\sum_{i = 1}^\infty \frac{1}{i ^ 2}$$

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

Точность $ \varepsilon $.

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

Бесконечная сумма с заданной точностью $ \varepsilon $.

Тесты

Входные данные Выходные данные
1 0.0000000000000045 1.6449339997656687
2 0.45 1
3 0.123123 1.25
4 1e-9 1.6449024437950241

Код программы

Ссылка на tryhaxe

 

Решение

На каждом шаге текущее слагаемое равно $ \frac{1}{i^2} $. Пока оно не меньше заданной точности, прибавляем к ответу.
Если заданная точность отрицательна либо равна нулю, цикл станет бесконечным, потому что $ \frac{1}{i^2} > 0, \forall i > 0 $.

Реальная же сумма ряда равна $\frac{\pi^2}{6}$, что в десятичном приближении представляет собой число 1.64493406684822643647241516664602518921894990120679843773555…

Ю3.45

Условие

Ю3.45. Гуси и кролики. У гусей и кроликов вместе $2n$ лап. Сколько может быть гусей и кроликов (вывести все возможные сочетания)?

Тесты

n   Кроликов Гусей Комментарий
4 0, 2, 4 2, 1, 0 Тест пройден
3 1, 3 1, 0 Тест пройден
0 0 0 Тест пройден
7 1, 3, 5, 7 3, 2, 1, 0 Тест пройден

Код

Решение

По условию задачи необходимо вывести все возможные варианты сочетаний количества кроликов и гусей.

Для того, чтобы это сделать используется 1 цикл. В нем проверяется условие (количество кроликов не превышает [latex]\frac{n}{2}[/latex]) — количество кроликов не может превышать $n/2$. Изначально переменным $k$ и $g$ присваивается значение 0. В теле цикла считаем количество гусей по формуле $(2n — 4k)/2$.

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

Ссылка на условие задания: cpp.mazurok.com
Try Haxe