Задача A. Устойчивость числа ≡

Условие

Рассмотрим число k₁. Произведением всех цифр из него получим число k₂. Из k₂ таким же образом получим k₃, и процесс остановится на k_n, состоящем из одной цифры. Число n называется устойчивостью числа k₁.

Напишите программу для нахождения устойчивости заданного числа k.

Формат входного файла

Входной файл содержит единственное целое число k.

Формат выходного файла

Выходной файл должен содержать единственное целое число — устойчивость числа k.

Ограничения

1 ≤ k ≤ 2 ⋅ 10⁹.

Примеры тестов

2

1

25

3

Задача B. Рисунки инопланетян ≡

Условие

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

Помимо того, что инопланетяне портят поля, они умудрились перессорить жителей деревень. Дело в том, что инопланетяне оставляют рисунки трёх типов: состоящие из квадратов, кругов и треугольников. Возле первой деревни рисунки чередуются так: в первый день квадраты, во второй день круги, в третий день треугольники, в четвёртый день опять квадраты, дальше круги, потом треугольники и так далее. Возле второй деревни периодичность другая: первый и второй дни квадраты, третий и четвёртый дни круги, пятый и шестой дни треугольники, далее рисунки повторяются. Возле третьей деревни рисунки чередуются так: три дня квадраты, три дня круги, три дня треугольники и так далее. Жители разных деревень спорят, у кого рисунки красивее и сложнее. Дело доходит даже до ссоры. Но бывают дни, когда рисунки возле всех трёх деревень состоят из одинаковых геометрических фигур. И жители заметили, что в такие дни страсти затихают, соседи перестают ссориться и общаются вполне миролюбиво.

Поэтому для жителей этой части Англии очень важно выяснить, как часто могут повторяться такие дни. Например, если визиты инопланетян будут продолжаться N дней, то сколько из этих дней все рисунки будут состоять из одинаковых элементов и в деревнях будет мирно? Напишите программу для ответа на этот вопрос.

Формат входного файла

Входной файл содержит единственное целое число N.

Формат выходного файла

Требуется вывести в выходной файл единственное целое число — количество дней, когда все рисунки состоят из одинаковых геометрических фигур.

Ограничения

Примеры тестов

3

1

18

2

25

3

Задача C. Отрезки с наложением ≡

Условие

Дано N отрезков с длинами w₁, …, w_N. Требуется расположить их на интервале числовой оси [0, L] так, чтобы они покрыли этот интервал без пропусков и не выходили за его границы.

Необходимо использовать все отрезки. Отрезки можно накладывать друг на друга.

Формат входного файла

Первая строка входного файла содержит целые числа N и L.

Вторая строка содержит N целых чисел w₁ w₂… w_N.

Формат выходного файла

Выходной файл должен содержать N целых чисел x₁ x₂… x_N — координаты левых концов отрезков.

Если решения не существует, то выходной файл должен содержать единственное число −1. Если существует несколько решений, вывести любое из них.

Ограничения

1 ≤ N ≤ 1000, 1 ≤ L ≤ 10000, 1 ≤ w_i ≤ 10000.

Примеры тестов

2 3
2 2

0 1

Задача D. В лесу родилась ёлочка ≡

Условие

Скоро Новый год, и Марфа Геннадьевна послала своих сыновей срубить несколько ёлок на продажу.

Хорошие, толстые, густые ёлки стоят на рынке 5000 руб., а ёлки похуже, тонкие, менее густые стоят 2000 руб.

На всё про всё у ребят есть ровно T минут. Хорошие ёлки растут подальше, и рубить их дольше. Ёлки похуже растут поближе, и рубить их быстрее. На то, чтобы дойти до i-й ёлки, срубить её и вернуться домой, нужно затратить t_i минут.

У ребят есть электронная карта участка леса, на которой отмечены ёлки. Сейчас им ой как нужна программа, вычисляющая максимально возможную выручку.

Формат входного файла

Входной файл содержит целое число T. Далее идёт целое число N — количество хороших ёлок, за которым следуют N целых чисел t_i.

Далее следует число M — количество ёлок похуже. За ним следуют M целых чисел t_i.

Формат выходного файла

Требуется вывести в выходной файл целое число — максимально возможную выручку.

Ограничения

1 ≤ N, M ≤ 1000

1 ≤ T ≤ 10000

1 ≤ t_i ≤ 10000

Примеры тестов

250
1
240
2
120 100

5000

250
1
240
3
60 80 70

6000

Задача E. Сложение неотрицательных длинных чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
5

8

100000000000000000000
29

100000000000000000029

Задача F. (20081220) A + (-B) ≡

Формат входного файла

Во входном файле заданы два целых неотрицательных числа A и B (A,  B ≤ 10^10 000), каждое на отдельной строке.

Формат выходного файла

В выходной файл выведите одно число, равное разности A и B.

Примеры тестов

5
3

2

Задача G. Умножение неотрицательных длинных чисел ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3
5

15

100000000000000000000
29

2900000000000000000000

Задача H. НОД и числа Фибоначчи (исправленная) ≡

Условие

k-тым числом Фибоначчи называется k-тый член последовательности F_k = F_k−1 + F_k−2 , F₀ = 0 , F₁ = 1

Формат входного файла

Формат выходного файла

В выходном файле должно содержаться единственное число — наибольший общий делитель F_n и F_k.

Ограничения

Примеры тестов

1 2

1

6 9

2

Задача I. Две пешки и слон ≡

Условие

На шахматной доске расположены две пешки. Требуется поставить на доску слона так, чтобы обе пешки оказались под боем.

Шахматная доска имеет размер 8 на 8. Слон бьет ближайшую фигуру на каждом из четырех диагональных направлений от себя.

Формат входного файла

Входной файл содержит числа x₁ y₁ x₂ y₂ — координаты первой и второй пешек.

Формат выходного файла

Если задача имеет решение, то выходной файл должен содержать два числа — координаты слона. Если решений несколько, вывести любое из них. Если задача не имеет решения, вывести единственное число 0.

Примеры тестов

3 6 7 5

0

3 4 5 6

4 5

4 5 5 6

0

Задача J. Судьба математика ≡

Условие

Любимая девушка одного математика сообщила ему номер своего телефона. Как истинный представитель своей профессии, он тут же забыл этот номер, однако успел заметить и запомнить целый ряд соотношений между цифрами. Дальнейшая судьба математика зависит от того, сможет ли он по этим соотношениям определить достаточно узкое множество подходящих номеров, чтобы успеть обзвонить их за приемлемое время.

В городе, где они живут, телефонные номера состоят из 6 цифр от 0 до 9 в любой комбинации (например, 000999 — правильный телефонный номер).

Между цифрами номера возможны 6 видов отношений: >, <, =, <=, >=, <>. Например, 2>5 означает, что вторая цифра в номере больше, чем пятая.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1<2
3=1
3>4

12000

Задача K. Марфа Геннадьевна и angry birds ≡

Условие

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

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

Тело имеет массу m кг, начальная скорость равна v₀ м/с и направлена под углом α градусов к горизонту. Ускорение свободного падения принять равным g = 9.8 м/с². Сила сопротивления воздуха равна .

Требуется определить время и дальность полёта курицы.

Формат входного файла

Входной файл содержит вещественные числа m v₀α k.

Формат выходного файла

Требуется вывести в выходной файл вещественные числа T L — время и дальность полёта соответственно с как минимум 2-мя точными знаками после запятой.

Ограничения

0.1 ≤ m ≤ 10

0.1 ≤ v₀ ≤ 20

1 ≤ α ≤ 90

0 ≤ k ≤ 10

Примеры тестов

1 10 45 0

1.443 10.204

1 10 45 1

1.206 4.955

Задача L. Числовые ребусы ≡

Условие

Однажды юному программисту Серёже попалась книга с головоломками. Ему особенно понравилось решать числовые ребусы. Он решил большое количество ребусов, но иногда у него получались ответы, не совпадающие с ответами в книге. Поэтому Серёже очень пригодилась бы программа, вычисляющая все возможные ответы к данному числовому ребусу.

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

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

Во 2-м примере должно быть написано 2014 + ГОД = СОЧИ, но из-за того, что русские буквы в примерах не отображаются, они были заменены на другие буквы.

Формат входного файла

Входной файл содержит 3 строки, представляющие собой числа, в которых некоторые цифры заменены на не цифровые символы с ASCII-кодом больше 32.

Формат выходного файла

Выходной файл должен содержать все возможные ответы на ребус в произвольном порядке, по одному в каждых 3-х строках, ответы нужно разделять пустыми строками.

Выводить следует те ответы, в которых нет незначащих нулей в начале чисел.

Ограничения

Количество символов в каждом числе во входном файле не превосходит 9.

Общее количество не цифровых символов во всех числах находится в пределах от 1 до 6.

Примеры тестов

drama
drama
teatr

18969
18969
37938

2014
AOB
CODE

2014
789
2803

2014
891
2905

2014
893
2907

2014
896
2910

OXOXO
AXAXA
AXAXAX

90909
10101
101010

2A14
AAB
AODE

2214
221
2435

2214
225
2439

Задача M. Двоичные последовательности ≡

Условие

Здравствуй, юный падаван!

Прошу тебя вывести все двоичные последовательности длины N.

Реши задачу двумя способами:

• рекурсивным перебором
• прибавлением 1 к числу в двоичной системе счисления

Да пребудет с тобой произведение массы на ускорение!

Формат входного файла

Входной файл содержит единственное целое число N.

Формат выходного файла

Требуется вывести в выходной файл все двоичные строки длины N в лексикографическом порядке, по одному в каждой строке.

Ограничения

1 ≤ N ≤ 15

Примеры тестов

2

00
01
10
11

Задача N. Семь колонн Владивостока ≡

Условие

Когда абитуриент Дима пришёл в кампус ДВФУ на день открытых дверей, его внимание привлекла инсталляция "Семь колонн Владивостока".

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

Каждому объекту данной скульптурной группы соответствует одна из семи самых высоких сопок города Владивостока. Высоты объектов, а также расстояния между объектами пропорциональны реальным высотам и расстояниям. На вершине каждого объекта находится фрагмент породы соответствующей сопки. Высоты выполнены в масштабе 1:75, расстояния между объектами соответственно 1:100.

Поскольку Дима дополнительно изучает информатику, он быстро смекнул, что данная конструкция может быть представлена как планарный граф, т.е. граф, который можно нарисовать на плоскости без пересечений рёбер.

Дима знает, как посчитать число граней этого планарного графа, для этого нужно применить формулу Эйлера V − E + F = 2, где V — число вершин, E — число рёбер, F — число граней, включая внешнюю грань. В нашем случае V = 7, E = 13, отсюда F = 8, поэтому треугольных граней всего 7, что легко проверить.

Но теперь Дима хочет посчитать общее число элементарных циклов в этом графе. Путь в графе — это последовательность вершин графа, в которой каждая пара последующих вершин соединена ребром. Циклом называется путь, в котором первая и последняя вершины совпадают. Цикл называется элементарным, если в нём вершины и рёбра не повторяются.

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

Формат входного файла

Входной файл содержит целые числа N M — количество вершин и количество рёбер соответственно. Далее следуют M пар целых чисел — рёбра графа.

Ребро не может идти из вершины в неё саму. В графе нет повторяющихся рёбер. Ребра (u, v) и (v, u) — это одно и то же ребро.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество элементарных циклов.

Ограничения

2 ≤ N ≤ 7

M ≥ 1

Примеры тестов

7 13
1 2
1 3
2 3
2 5
2 6
3 4
3 5
3 7
4 5
4 6
4 7
5 6
6 7

56

6 6
1 2
2 3
3 1
4 6
6 5
5 4

2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

7