Информатика

Входные данные
Шесть чисел – координаты точек 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

 

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

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

Примеры

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

Требуется определить, можно ли от шоколадки размером n × m долек отломить k долек, если разрешается сделать один разлом по прямой между дольками (то есть разломить шоколадку на два прямоугольника).

Входные данные
Вводятся 3 числа: n, m и k; k не равно n × m. Гарантируется, что количество долек в шоколадке не превосходит 30000.

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

Примеры

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

Даны координаты двух точек на плоскости, требуется определить, лежат ли они в одной координатной четверти или нет (все координаты отличны от нуля).

Входные данные
Вводятся 4 числа: координаты первой точки (x1, y1) и координаты второй точки (x2, y2).

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

Примеры

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

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

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

Входные данные
Вводятся четыре числа: координаты ферзя и координаты другой фигуры. Координаты - целые числа в интервале от 1 до 8.

Выходные данные
Требуется вывести слово YES, если ферзь может побить фигуру за 1 ход, в противном случае вывести слово NO
 

Примеры

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

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

Входные данные
Вводятся четыре числа: координаты ладьи (два числа) и координаты другой фигуры (два числа), каждое число вводится в отдельной строке. Координаты - целые числа в интервале от 1 до 8.

Выходные данные
Требуется вывести слово YES, если ладья сможет побить фигуру за 1 ход и NO - в противном случае.
 

Примеры

№	Входные данные	Выходные данные
1	1 1 2 2	NO
2	1 1 2 1	YES

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

Узнав об этом, волк сказал Красной Шапочке, что ей совершенно незачем тратить пирожки на Лесничего. За половину тех пирожков, которые Красная Шапочка несет бабушке, Волк пообещал не трогать ее.

Сегодня (26 ноября) в России отмечается день матери. Мама испекла несколько пирожков, и попросила Красную Шапочку отнести их бабушке. Требуется определить, сколько пирожков Красная Шапочка сможет донести до бабушки.

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

Выходные данные
Программа должна вывести  одно число - количество пирожков, которые Красная Шапочка сможет донести до бабушки.

Примеры

№	Входные данные	Выходные данные
1	12	6
2	100	90

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


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

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

Примеры

№	Входные данные	Выходные данные
1	2 3	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

Найдите перестановку по её номеру в лексикографическом порядке.

Входные данные
В первой строке входных данных содержится число N (1 <= N <= 12) – количество элементов в перестановке, во второй – число K (1 <= K <= N!) – номер перестановки.

Выходные данные
Выведите N чисел – искомую перестановку.

Примеры

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