Алгоритмы

Входные данные
Шесть чисел – координаты центра и радиусы двух окружностей.

Выходные данные
В случае, если количество общих точек окружностей конечно, в первой строке вывести одно число K, равное этому количеству, далее в K строках координаты самих точек. Если указанных точек бесконечно много, вывести единственное число “3”.
 

Примеры

№	Входные данные	Выходные данные
1	3 4 5 11 4 2	0
2	3 4 5 9 4 2	2 7.75000 5.56125 7.75000 2.43875

Увлекшись машинным обучением, Вася совсем забыл про свои экзамены в университете, завалил их и пошел служить в армию. Однако, и тут ему пригодились его навыки программиста — у работников столовой возникла проблема с тем, что блюда постоянно повторяются, и солдаты начали слишком этому возмущаться. Узнав, что Вася разбирается в программировании, работники попросили его написать программу, которая сделает распределение блюд.
Работники столовой считают, что единственное, что характеризует распределение блюд — их «степень немонотонности» — число разных блюд, которые даются в последовательные приемы пищи. То есть, если представить расписание блюд как массив a, то «степень немонотонности» будет равна количеству индексов i, таких что \(a_i \neq a_{i-1}\) . Для начала вас просят найти не само распределение блюд, а хотя бы максимальную возможную «степень немонотонности», которую можно было бы получить некоторой перестановкой заданного набора блюд. Помогите армейской столовой!
Входные данные
В первой строке содержится число n — количество блюд, которые должны войти в расписание (1 ≤ n ≤ 100).
В следующей строке содержится n чисел a_i — блюда (1 ≤ a_i  ≤ 100). Одинаковые блюда обозначены одинаковыми числами, разные — разными.
Выходные данные
В единственной строке выведите одно число — максимальное возможное значение «степени немонотонности».
 

Ввод	Вывод
5 1 2 3 1 1	4
4 1 1 1 2	2

Входные данные
Шесть чисел – координаты центра и радиус окружности и коэффициенты A, B и C нормального уравнения прямой.

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

Примеры

№	Входные данные	Выходные данные
1	2 3 1 1 -1 0	2 3.00000 3.00000 2.00000 2.00000

Входные данные
Пять чисел – координаты центра и радиус окружности, координаты точки.

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

Примеры

№	Входные данные	Выходные данные
1	2 2 2 2 5	2 0.50929 3.33333 3.49071 3.33333

Входные данные
Шесть чисел – координаты точек X, Y и Z.

Выходные данные
Три числа – коэффициенты уравнения биссектрисы угла YXZ.

Примеры

№	Входные данные	Выходные данные
1	0 0 1 0 0 1	1.000000 -1.000000 0.000000
2	0 0 1 3 1 -3	0.000000 -0.632456 0.000000

Входные данные
Шесть чисел – коэффициенты A, B и C нормального уравнения двух различных непараллельных прямых (сначала для одной прямой, затем для другой).

Выходные данные
Два числа – координаты точки их пересечения.

Примеры

№	Входные данные	Выходные данные
1	4 -4 0 0 -3 6	2.00000 2.00000

Входные данные
Восемь чисел – координаты концов двух отрезков.

Выходные данные
Одна строка “YES”, если отрезки имеют общие точки, и “NO” в противном случае.
 

Примеры

№	Входные данные	Выходные данные
1	1 2 1 2 1 2 1 2	YES
2	3 3 5 6 5 6 3 3	YES

Входные данные
Шесть чисел – координаты точки и координаты концов отрезка.

Выходные данные
Одно число – расстояние от точки до отрезка.
 

Примеры

№	Входные данные	Выходные данные
1	0 0 0 0 4 0	0.00000
2	4 0 0 0 4 0	0.00000

Входные данные
Шесть чисел – координаты точки и координаты начала и конца вектора.

Выходные данные
Одно число – расстояние от точки до луча, определяемого вектором.
 

Примеры

№	Входные данные	Выходные данные
1	2 3 0 0 4 0	3.00000
2	-1 1 0 0 4 0	1.41421

Входные данные
Пять чисел – координаты точки и коэффициенты A, B и C уравнения прямой.

Выходные данные
Одно число – расстояние от точки до прямой.
 

Примеры

№	Входные данные	Выходные данные
1	1 5 0 -4 8	3.00000

Входные данные
Пять чисел – координаты точки и коэффициенты A, B и C уравнения прямой.

Выходные данные
Одна строка “YES”, если точка принадлежит прямой, и “NO” в противном случае.

Примеры

№	Входные данные	Выходные данные
1	8 7 2 -3 5	YES

Входные данные
Четыре числа – координаты точки на прямой и координаты вектора нормали к этой прямой.

Выходные данные
Три числа – коэффициенты A, B и C уравнения этой прямой.
 

Примеры

№	Входные данные	Выходные данные
1	0 0 1 1	1 1 0

Молчун, Ворчун и Пилюлькин играют в карточную игру на троих. Правила игры следующие.
Сначала у каждого из трех игроков есть колода, состоящая из некоторого количества карт.
В колоде Пилюлькина N карт, в колоде Молчуна M карт, а в колоде Ворчуна K карт. На каждой карточке написана буква p, m или v. Порядок карт в колодах не может быть изменен. Игроки ходят по очереди. Пилюлькин ходит первым.
Если в колоде текущего игрока есть хотя бы одна карта, сбросьте верхнюю карту в колоде.
Затем следующий ход переходит к игроку, имя которого начинается с буквы на сброшенной карте.Например, если на карте написано «p», следующий ход переходит Пилюлькину.
Если колода текущего игрока пуста, игра заканчивается, и текущий игрок выигрывает игру.
Есть 3N + M + K возможных вариантов раскладки начальных колод трех игроков.
Сколько из этих шаблонов приведет к победе Пилюлькина? Поскольку ответ может быть большим, выведите его по модулю 1000000007 (= 10⁹ +7).

Входные данные
На вход подается три целых числа N, M и K (2<=N, M, K <=3*10⁵).

Выходные данные
Выведите количество победных для Пилюлькина шаблонов по модулю 1000000007 (= 10⁹ +7).

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	1 1 1	17	Если карта Пилюлькина - p, то Пилюлькин выиграет независимо от карты Молчуна и Ворчуна. Таких вариантов 3 × 3 = 9. Если карта Пилюлькина - m, Пилюлькин выиграет только тогда, когда карта Молчуна - p, или когда карта Молчуна - v, а карта Ворчуна - p. Всего таких шаблоно 3 + 1 = 4. Если карта Пилюлькина - v, Пилюлькин выиграет только тогда, когда карта Ворчуна - p, или когда карта Ворчуна - m, а карта Ворчуна - p. Всего таких шаблонов 3 + 1 = 4. Таким образом, всего 9 + 4 + 4 = 17 шаблонов, которые приведут к победе Пилюлькина.
2	4 2 2	1227
3	1000 1000 1000	261790852

 

Художник Тюбик учит Незнайку рисовать. Он дал ему сетку с H строками и W столбцами. Все клетки сетки изначально выкрашены в белый цвет. Тюбик попросил Незнайку закрасить N из этих ячеек в черный цвет. I-я (1<=i<=N) ячейка, которую закрасил Незнайка, является ячейкой в a_i-й строке и b_i -м столбце. Для каждого целого числа j (0<=j<=9), определите сколько в сетке подпрямоугольников размером 3×3 содержит ровно j черных ячеек после того, как Незнайка закрасил N ячеек?

Входные данные
В первой строке заданы 3 целых числа: H, W (3<=H,W<=10⁹) и N (0<=N<=min(10⁵,H×W)). Далее идут N строк по 2 числа в каждом a_i (1<=a_i<=H) и b_i (1<=b_i<=W), 1<=i<=N, (a_i,b_i)≠(a_j,b_j), i ≠ j.

Выходные данные
Выведите 10 строк. В (j + 1)-й (0<=j<=9) строке должно быть указано количество подпрямоугольников размером 3 × 3 сетки, содержащей ровно j черных ячеек.
 

 

Примеры

№	Входные данные	Выходные данные
1	4 5 8 1 1 1 4 1 5 2 3 3 1 3 2 3 4 4 4	0 0 0 2 4 0 0 0 0 0
2	10 10 20 1 1 1 4 1 9 2 5 3 10 4 2 4 7 5 9 6 4 6 6 6 7 7 1 7 3 7 7 8 1 8 5 8 10 9 2 10 4 10 9	4 26 22 10 2 0 0 0 0 0
3	1000000000 1000000000 0	999999996000000004 0 0 0 0 0 0 0 0 0

 

Вам дана строка S, состоящая из цифр от 1 до 9 включительно. Вы можете вставить символ + в некоторые позиции (возможно, ни в одну) между двумя цифрами в этой строке. Здесь знак + не должен появляться последовательно после вставки (т.е. не должно быть два и больше знака + подряд). Все строки, которые можно получить таким образом, можно оценить как формулы. Оцените все возможные формулы и распечатайте сумму результатов, полученных при вычислении всех возможных формул.

Входные данные
На вход подается непустая строка S, состоящая из цифр от 1 до 9 включительно. Длина строки не более 10 символов.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	125	176	Всего можно получить 4 формулы: 125, 1 + 25, 12 + 5 и 1 + 2 + 5. Результат после вычисления каждой формулы: 125 1 + 25 = 26 12 + 5 = 17 1 + 2 + 5 = 8 Таким образом, сумма 125 + 26 + 17 + 8 = 176.
2	9999999999	12656242944

 

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

Выходные данные
Три числа – коэффициенты A, B и C уравнения этой прямой.

Примеры

№	Входные данные	Выходные данные
1	1 0 2 1	1 -1 -1

Сегодня на уроке Петя узнал про бессуффиксные коды. Множество строк называется бессуффиксным кодом, если
- Все строки в множестве различны
- Не существует такой пары различных строк, что одна строка является суффиксом другой
Строка s называется префиксом строки t, если длина строки s не больше длины t, а также для любого i, i-й символ строки s совпадает с i-м символом строки t. Например, ab является префиксом ab и abc, но не является префиксом a и ac.
Петя же решил придумать что-то новое и ввел новое понятие — k-бессуффиксный код. Таким кодом он назвал множество строк, такое, что:
- Все строки в множестве различны
- У любых двух различных строк наибольший общий префикс имеет длину не больше k
Наибольшим общим префиксом двух строк s и t называется наибольшая по длине строка, являющаяся префиксом обеих строк.
Теперь по данному множеству строк s1, s2, ..., sn и числу k Петя хочет найти в этом множестве k-бессуффиксный код, состоящий из максимально возможного количества строк. Помогите ему — найдите этот код.
Входные данные
В первой строке содержится два числа n и k — количество строк в множестве и максимальная длина общего префикса соответственно (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 100).
В i-й из следующих n строк содержится строка из строчных латинских букв si — i-е слово из множества (1 ≤ |si| ≤ 100).
Гарантируется, что суммарная длина всех строк в множестве не превосходит 10⁶.
Выходные данные
В первой строке выведите число m - максимально возможное количество строк в k-бессуффиксном коде. В i-й из следующих m строк выведите i-й элемент этого кода. Элементы кода можно выводить в любом порядке.
Если существует несколько ответов с максимальным m, разрешается вывести любой.
 

Ввод	Вывод
5 2 cbaa dbca caa abca baa	3 baa caa abca
4 2 aa cba aa bba	3 aa bba cba

Замечание
В первом примере у строк 1 и 5, а также у строк 2 и 4 наибольший общий префикс больше k, поэтому максимальное количество строк, из которых может состоять k-беспрефиксный код - 3. Во втором примере у любой пары подстрок наибольший общий префикс не больше 2, однако, так как код не может содержать одинаковые строки, больше 3 строк в него не включить.

В прямоугольной таблице NxM в левой верхней клетке стоит шашка. За один ход разрешается переместить шашку в соседнюю клетку либо вправо, либо вниз (влево и вверх перемещаться запрещено). Посчитайте, сколько есть вариантов переместить шашку в правую нижнюю клетку.


Входные данные
Вводятся два числа N и M - размеры таблицы (1<=N<=10, 1<=M<=10).

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

Примеры

№	Входные данные	Выходные данные
1	2 3	3

 

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

Входные данные
В первой строке  вводится число N – размер лабиринта (3 <= N <= 10). В следующих N строках задан лабиринт (‘.’ – пустая клетка, ‘*’ – стенка). И наконец, последняя строка содержит  два числа – номер строки и столбца клетки, находящейся в комнате, площадь которой необходимо вычислить. Гарантируется, что эта клетка пустая и что лабиринт окружен стенками со всех сторон.

Выходные данные
Требуется вывести единственное число – количество пустых клеток в данной комнате.

 

Примеры

№	Входные данные	Выходные данные
1	5 ***** **..* *.*.* *..** ***** 2 4	3

Вам дана перестановка из первых N натуральных чисел. Найдите по ней следующую в лексикографическом порядке (будем считать, что за перестановкой N N-1 ... 3 2 1 следует тождественная перестановка, то есть, 1 2 3 ... N).

Входные данные
В первой строке входных данных содержится число N (1 <= N <= 10000). Во второй строке находится перестановка (последовательность натуральных чисел от 1 до N, разделенных пробелами).

Выходные данные
Требуется вывести искомую перестановку.

Примеры

№	Входные данные	Выходные данные
1	3 1 3 2	2 1 3