Байтландские шаманы

Ограничение времени 2 секунды
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Легенда

Шаманы племён, обитавших в древности на территории нынешней Байтландии, практиковали следующий способ построения заклинаний.

В основу брались две ключевых фразы — A и B. Каждая фраза могла состоять из нескольких слов. После этого строилась такая последовательность заклинаний: T0 = A, T1 = B, T2 = A B, T3 = B A B, …, Tn = Tn - 2 Tn - 1.

Таким образом, каждое заклинание Ti, начиная с i = 2, состояло из последовательного исполнения заклинаний Ti - 2 и Ti - 1. При последовательном исполнении заклинаний между ними делалась небольшая пауза, так что новые слова при конкатенации образовываться не могли.

В разных случаях использовались разные заклинания: например, для проведения обряда инициации шаман должен был произнести заклинание так, чтобы имя духа S, встречавшееся как минимум в одной из ключевых фраз, было произнесено ровно K раз.

Антропологи обратились к вам с просьбой: зная начальные ключевые фразы A и B, имя духа S, встречающееся в одной или обеих из них, а также число K, определить число N — наименьший номер заклинания TN, в котором слово S встречается ровно K раз.

Формат ввода

Первая строка содержит ключевую фразу A — строку из не более 255 ASCII-символов с кодами от 32 до 127 включительно. Фраза содержит от одного до десяти слов.

Словом считается последовательность английских букв, ограниченная символами-разделителями, к которым относятся все остальные символы. При этом большие и маленькие английские буквы не различаются.

Во второй строке в том же формате задана фраза B.

В третьей строке задано имя духа S — слово, представляющее собой последовательность маленьких английских букв. Гарантируется, что слово S содержится как минимум в одной из ключевых фраз A или B.

Четвёртая строка содержит одно целое положительное число K. Длина строки, содержащей число K, не превосходит 3000 символов.

Формат вывода

Требуется вывести единственное число N — наименьший номер заклинания, в котором слово S встречается ровно K раз. Если такого номера не существует, следует вывести “Impossible”.

Пример 1
Ввод

Python is great!
Python-Die-Grosse-Shlange
python
5

Вывод

4

Пример 2
Ввод

Great Python, answer to me!
Help us, Python
python
4

Вывод

Impossible

Окружности-2

Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Легенда

Задано n треугольников, длины сторон которых являются целыми числами. Найдите наибольшее количество треугольников, имеющих один и тот же радиус вписанной окружности.

Формат ввода

В первой строке входного файла задано целое число n (1 ≤ n ≤ 1000) — количество треугольников. Каждая из последующих n строк содержит три целых числа ai, bi и ci — длины сторон i-го треугольника. Гарантируется, что треугольники невырождены и 1 ≤ ai, bi, ci ≤ 1000.
Формат вывода

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

Пример
Ввод

3
3 4 5
5 4 3
10 10 10

Вывод

2

После финала

Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Легенда

Финал Чемпионата Байтландии по программированию впервые проводился в городе . Дорожная сеть города представляет собой N перекрёстков, соединённых M дорогами с двусторонним движением. Программа финала была столь насыщенной, что участники не успели осмотреть город. Более того, церемония закрытия затянулась, так что при отъезде команды-победителя времени оставалось только на то, чтобы добраться до аэропорта кратчайшим по суммарной длине путём. При этом, чтобы хотя бы немного посмотреть город, из всех таких маршрутов выбрали тот, который включает в себя целиком наибольшее количество дорог.

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

Формат ввода

Первая строка содержит два целых числа N и M — количество перекрёстков в городе и количество дорог соответственно (2 ≤ N ≤ 1000, 1 ≤ M ≤ 2 ⋅ 105).

Каждая из следующих M строк содержит три целых числа ai, bi и ci (1 ≤ ai, bi ≤ N, ai ≠ bi, 1 ≤ ci ≤ 1000) — номера перекрёстков, соединяемых i-й дорогой, и длину этой дороги. Два различных перекрёстка могут быть соединены более чем одной дорогой. Место проведения финала находится на перекрёстке с номером 1, аэропорт — на перекрёстке с номером N.

Гарантируется, что существует хотя бы один путь от места проведения финала в аэропорт.

Формат вывода

Выведите два целых числа P и Q — длину кратчайшего пути от места проведения финала в аэропорт и максимальное число дорог, которые может включать в себя кратчайший путь.

Пример
Ввод

3 3
1 2 1
1 3 2
2 3 1

Вывод

2 2

Факториалы

Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Легенда

Миша недавно узнал, что факториал числа n — это произведение всех натуральных чисел от 1 до n включительно. Факториал числа n имеет обозначение ; так, например, , , . По определению .

Мише понравилось вычислять факториалы маленьких чисел. Однако он быстро понял, что факториалы чисел, больших десяти, очень сложно вычислять вручную. Тогда он стал искать лишь несколько последних цифр, но обнаружил, что они слишком часто оказываются нулями: к примеру, в числе , если верить его подсчётам, последние шесть цифр — нули. Гораздо более интересной задачей оказалось найти последнюю ненулевую цифру , но Миша справился и с ней.

Руководитель математического кружка, в котором учится Миша, узнал о его успехах и дал ему более сложную задачу: найти последнюю ненулевую цифру суммы k-х степеней факториалов целых чисел от 0 до n, где k — неотрицательное целое число. Правда, руководитель сделал скидку на то, что Миша ещё учится в шестом классе, и поставил ограничение k ≤ 3, n ≤ 100. Впрочем, считать Мише всё равно придётся очень долго...

Помогите Мише с помощью компьютера решить поставленную задачу. Напишите программу, которая по заданным значениям n и k вычисляет последнюю ненулевую цифру суммы k-х степеней факториалов всех целых чисел в промежутке от 0 до n.

Формат ввода

В первой строке заданы два целых числа — положительное число n, не превосходящее 100, и неотрицательное число k, не превосходящее трёх.
Формат вывода

Выведите одно число — последнюю ненулевую цифру суммы k-х степеней факториалов целых чисел от 0 до n включительно.

Пример 1
Ввод

4 1

Вывод

4

Пример 2
Ввод

3 2

Вывод

2

Противоположная цепная дробь

Ограничение времени 1 секунда
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Легенда

Конечная цепная дробь — это последовательность вида [a0; a1, a2, …, an]. На элементы цепной дроби и её размер накладываются следующие ограничения:

n — неотрицательное конечное целое число,
элементы a0, a1, a2, …, an — целые числа,
ai > 0 при i > 0,
an > 1, если n > 0.

Эти ограничения позволяют установить взаимно однозначное соответствие между рациональными числами и конечными цепными дробями: каждому вещественному числу x соответствует единственная цепная дробь [a0; a1, a2, …, an] такая, что
Для обозначения соответствия используется знак равенства: x = [a0; a1, a2, …, an].

Дано рациональное число x (0 < x < 1), записанное в виде цепной дроби. Требуется найти цепную дробь числа (1 - x).

Формат ввода

В первой строке задано целое число n (1 ≤ n ≤ 100 000). Во второй строке дано (n + 1) целых чисел: a0, a1, a2, …, an — элементы исходной цепной дроби. Гарантируется, что цепная дробь задана корректно, то есть заданные числа удовлетворяют всем ограничениям из определения. Заданная цепная дробь соответствует такому рациональному числу x, что 0 < x < 1, и для каждого i выполнено неравенство ai ≤ 100.

Формат вывода

В первой строке выведите целое число m, а во второй строке — (m + 1) положительных целых чисел: b0, b1, b2, …, bm — элементы полученной цепной дроби. Цепная дробь должна быть задана корректно, то есть выведенные числа должны удовлетворять всем ограничениям из определения. Для цепных дробей должно выполняться равенство

Пример 1
Ввод

2
0 1 2

Вывод

1
0 3

Пример 2
Ввод

2
0 2 3

Вывод

3
0 1 1 3

Разминочные задачи 2017-го года
Дано целое положительное число n. Требуется найти наименьшее целое положительное k, такое, что n не делится на k.

Ввод. в программу вводится число n в диапозоне 1....10^9
Вывод: программа должна вывести одно целое число.

Примеры
Ввод 22
Вывод 3
====
Ввод 4
Вывод 3

Ввод 2017
Вывод 2

Цирцея — хозяйка магазина контактных линз в Стране Циклопов. Она собирает заказы на линзы от циклопов (как известно, у циклопа один глаз, так что ему нужна одна линза) и потом покупает линзы у производителя. При этом если циклопу рекомендовано ношение линз в k диоптрий, его устроят линзы и в k−1 диоптрию, и в k+1 диоптрию.
Цирцея заказывает линзы у производителя обычных контактных линз, который продаёт линзы только парами линз одинаковой оптической силы. Цирцея хочет купить минимальное количество пар линз так, чтобы удовлетворить все поступившие заказы.

Ввод. Первая строка входных данных содержит одно целое число n ( 1≤n≤2500) — количество заказов от циклопов. Вторая строка содержит n целых чисел l[i] ( −1000≤l[i]≤1000) — рекомендованная оптическая сила линзы для i-го циклопа.

Вывод. одно целое число — наименьшее количество пар линз, которое Цирцея должна купить для того, чтобы выполнить все заказы циклопов.

Примеры
Ввод
5
0 1 -1 -1 -1
Вывод
3

Ввод
4
-3 6 3 0
Вывод
4

Мое решение первой задачи:

Мое решение второй задачи: