Задача A. Сколько лепестков? ≡

Условие

Здесь можно узнать, любит ли тебя он/она. Введи ваши дни рождения, скрипт нарисует цветок, и тебе только останется сосчитать лепестки.

Примечание. Вопросы по всем задачам турнира вы можете задавать здесь.

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

Входной файл содержит 4 целых числа: день и месяц (М) и день и месяц (Ж).

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

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

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

1 1  15 5

7

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

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 15

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

2

00
01
10
11

Задача C. Принтер - 2 ≡

Условие

Аполлинарий Матвеевич недавно купил новый принтер и решил распечатать на нём одну главу из своей любимой книги по микроэлектронике.

Входной и выходной лотки принтера горизонтальные. Принтер работает так: стопка бумаги загружается во входной лоток, принтер берёт по очереди листы от верхнего до нижнего и печатает на них страницы от последней до первой. Принтер печатает на той стороне листа, которая находится сверху во входном лотке, и в выходном лотке эта сторона листа тоже будет сверху. Таким образом, если положить в лоток 3 чистых листа бумаги и распечатать страницы с 1-й по 3-ю, то в выходном лотке страницы будут в таком порядке: 1, 2, 3.

Чтобы использовать меньше бумаги и чтобы распечатки было легче переплести, Аполлинарий Матвеевич предпочитает двустороннюю печать. Такой способ печати обычно вызывает у Аполлинария Матвеевича головную боль, если рядом нет внука-программиста, — текст распечатывается не так, как нужно.

Возможные дефекты:

1. При перелистывании распечатки может оказаться, что страницы расположены в неправильном порядке: 2, 1, 4, 3, ... вместо 1, 2, 3, 4, из-за чего приходится переворачивать каждый лист.
2. Первый лист может оказаться пустым с одной стороны, и Аполлинарий Матвеевич хочет, чтобы пустота была только на последнем листе.

Напишите программу, принимающую на вход диапазон страниц a… b и выводящую минимальную по длине последовательность инструкций для Аполлинария Матвеевича. В начальный момент времени во входном лотке лежит достаточно много чистых листов бумаги.

Коды инструкций:

• 1 — распечатать только нечётные страницы;
• 2 — распечатать только чётные страницы;
• 0 — положить чистый лист сверху стопки, лежащей на столе;
• −1 — достать стопку из выходного лотка и положить на стол;
• −2 — положить стопку со стола во входной лоток;
• 3 — перевернуть стопку, лежащую на столе.
• 100 — стопка бумаги лежит на столе, и при перелистывании будут просмотрены страницы a,a+1,…,b. Пойти выпить чаю и съесть французских булок.

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

Входной файл содержит целые числа a b.

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

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

Ограничения

1 ≤ a ≤ b ≤ 1000.

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

1 1

1 -1 100

1 10

2 -1 3 -2 1 -1 100

Задача D. Лена и зеркало ≡

Условие

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

Так как Солнце находится на достаточно большом расстоянии от Земли, при расчётах часто считают Солнце бесконечно удалённой точкой. В этом случае световые лучи, испускаемые Солнцем, считают параллельными друг другу.

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

Пусть зеркало наклонено так, что в некоторой системе координат его можно задать как прямую, имеющую уравнение y = kx + b. Направление падения солнечных лучей задаётся единичным вектором a.

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

Примечание. По законам оптики, свет отражается так, что угол падения равен углу отражения (α = β на рисунке).

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

Входной файл содержит три вещественных числа k x₁ y₁ — угловой коэффициент прямой и координаты вектора a.

Длина вектора a приближённо равна 1.

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

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

Длина вектора c должна быть приближённо равна 1.

Координаты вектора c должны быть выведены с точностью до 3-х знаков после запятой.

Ограничения

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

0 0.7071067812 -0.7071067812

0.7071067812 0.7071067812

1 1 0

0 1

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

Условие

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

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

Каждому объекту данной скульптурной группы соответствует одна из семи самых высоких сопок города Владивостока. Высоты объектов, а также расстояния между объектами пропорциональны реальным высотам и расстояниям. На вершине каждого объекта находится фрагмент породы соответствующей сопки. Высоты выполнены в масштабе 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

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

Условие

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

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

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

Во 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

Задача G. Марфа Геннадьевна и 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

Задача H. Снежинки ≡

Условие

Здесь вы можете вырезать свою снежинку.

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

Левая вершина треугольника имеет барицентрические координаты (1, 0, 0), правая верхняя — (0, 1, 0), и правая нижняя — (0, 0, 1).

Ваша задача — указать для каждой снежинки номер файла с координатами, который ей соответствует.

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

Входной файл пустой.

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

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

Задача I. Кампусный квест ≡

Условие

Вход в кампус ДВФУ открытый, поэтому многие жители и гости Владивостока ходят гулять по кампусу и на набережную. Там красивая природа, искусственные водопады, парки.

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

В каждой группе мостиков интервал изменения длин порядка 2 м.

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

Входной файл пустой.

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

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

Задача J. Логика В.О. Ключевского ≡

Условие

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

(В.О. Ключевский "Афоризмы и мысли об истории")

Введём множество I = {О, У, Д}. Положим D ⊂ I × I равным D = {(Д, О), (У, О), (О, У)}. Определим на множестве D многозначные функции Ключевского K_Y(a, b), K_O(a, b), значения которых равны множеству возможных приращений количеств умных и остроумных людей соответственно, если "a считает себя b".

Дано N пар (a_i, b_i) ∈ D. Определить нижнюю и верхнюю границы сумм N∑i=1K_Y(a_i, b_i) и N∑i=1K_O(a_i, b_i).

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

Входной файл содержит целое число N. Далее следуют N пар целых чисел A_i B_i. Таблица соответствия: О — 0, У — 1, Д — 2.

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

Выходной файл должен содержать 4 числа: m_Y M_Y m_O M_O.

Ограничения

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

1
1 0

-1 -1   0 1

3
0 1
2 0
1 0

-1 -1   -1 0

Задача K. Bad game ≡

Условие

В ДВФУ при оценке выполнения студентами заданий используется система AWorks, которая снижает баллы за не вовремя сданное задание. Однажды преподаватель решил больше не мучить студентов и разработал игру, в которой нужно уничтожать монстров, давая им задания.

Всего в игре M монстров, им даётся N заданий. Каждый монстр характеризуется успешностью p_i — это вероятность, с которой он сдаст задание вовремя. За вовремя сданное задание монстр получает 1 балл, за не вовремя сданное задание — 0.5 балла. Монстру необходимо заработать не менее A баллов.

Какое количество монстров заработает не менее A баллов и не будут уничтоженными? Найдите распределение вероятностей.

Монстры действуют независимо друг от друга, и сдача одного задания не зависит от сдачи другого задания.

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

Входной файл содержит целые числа N A M, за которыми следуют M вещественных чисел p_i.

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

Требуется вывести в выходной файл M + 1 пар чисел k c_k, где k = 0, 1, ..., M, а c_k — вероятность того, что ровно k монстров не будут уничтожены, с точностью до 5-ти знаков после запятой.

Ограничения

1 ≤ A ≤ N ≤ 10

1 ≤ M ≤ 10

0.01 ≤ p_i ≤ 1

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

4 3 2
0.5 0.3

0 0.20366
1 0.55689
2 0.23946

3 1 1
0.1

0 0.00000
1 1.00000

Задача L. Логический тест ≡

Условие

Пройдите тесты "Логический тест 1" и "Логический тест 2" в тестирующей системе.

Для этого вы должны зарегистрироваться в системе. При регистрации укажите название своей команды в CATS в поле "Фамилия, имя".

Проходить тесты можно сколько угодно раз. Когда в статистике у вас будут плюсы за все вопросы по обоим тестам, вы получите Solution accepted по этой задаче.

Как пройдёте оба теста на 100 баллов, напишите произвольную заглушку на любом языке программирования, лишь бы она компилировалась, и отправьте в качестве решения этой задачи. Вы держитесь там, число попыток не ограничено.

Затем напишите в консоль CATS или в обсуждение, что вы справились с заданием, и результат "Awaiting manual verification" будет исправлен на "Solution accepted".

Задача M. Кепка ≡

Условие

Если положить α = 0, то поверхность K будет описываться формулами в последней строке, где нужно принять z равным 0.

Вот пример кепки при R = 10, L = 20.

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

Входной файл содержит целые числа R L.

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

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

Ограничения

1 ≤ R ≤ L ≤ 100

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

10 20

785.39816340

10 10

628.31853072

Задача N. Оптимальный план ≡

Условие

Дядя Коля стал замечать, что он не успевает делать все дела в срок. Тут ему в голову пришла идея придать планированию времени математически точную формулировку.

У дяди Коли есть N дел. Каждую минуту он может посвятить одному из них. Для каждого дела известен срок сдачи t_i, длительность выполнения дела l_i и приоритет p_i. Таким образом, на выполнение всех дел у дяди Коли уйдёт T = N∑i=1l_i минут.

Составим функционал стоимости:

∫T0C(t)dt,

C(t) = N∑i=1p_iexp [(l_i − d_i(t)) − (t_i − t)].

Здесь d_i(t) — количество времени, потраченное на i-е дело до момента времени t. В этой формуле (l_i − d_i(t)) — это сколько осталось сделать, а (t_i − t) — это сколько осталось времени до срока сдачи. В каждый момент времени t суммирование производится по номерам i, для которых d_i(t) < l_i, т.е. по не завершённым делам.

Требуется найти оптимальный план, то есть для каждой из T минут указать номер дела, которое нужно выполнить в данную минуту, чтобы функционал стоимости (интеграл) достигал наименьшего значения.

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

Входной файл содержит целое число N. Далее следуют N троек чисел t_i l_i p_i. Здесь t_i и l_i — целые числа, p_i — вещественное число.

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

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

Ограничения

1 ≤ N ≤ 10

1 ≤ T ≤ 100

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

2
3 2 1
2 3 1

34.62491

Задача O. Шифр ≡

Условие

В файле input.txt зашифрованное стихотворение.

Выходной файл output.txt должен содержать пятое слово с конца.

Задача P. В пределе ≡

Условие

Здесь вы можете нарисовать звездочку.

Пусть числа R, r фиксированы. Площадь фигуры, ограниченной звездой с n лучами, обозначим через S_n. Положим S = limn ↦ ∞S_n.

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

Входной файл содержит вещественные числа R r.

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

Выходной файл должен содержать число S с точностью не менее 3 знаков после десятичной точки.

Ограничения

0 < r ≤ R ≤ 100

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

1 0.4

1.25664