Информатика

Художник Тюбик учит Незнайку рисовать. Он дал ему сетку с 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 и cab, но не является суффиксом строк a и ac.

Петя же решил придумать что-то новое и ввёл новое понятие — k-бессуффиксный код. Таким кодом он назвал множество строк, такое что:

• все строки в множестве различны;
• у любых двух различных строк наибольший общий суффикс имеет длину не больше k.

Наибольшим общим суффиксом двух строк s и t называется наибольшая по длине строка, являющаяся суффиксом обеих строк.

Теперь по данному набору строк s1, s2, ..., sn и числу k Петя хочет найти в этом наборе k-бессуффиксный код, состоящий из максимально возможного количества строк.

Помогите ему — найдите этот код.
 

Входные данные

В первой строке содержатся два числа n и k — количество строк в наборе и максимальная длина общего суффикса соответственно (1 ≤ n ≤ 105, 1 ≤ k ≤ 100). В i-й из следующих n строк содержится строка si — i-е слово из набора (1 ≤ |si| ≤ 100). Все строки состоят из строчных латинских букв. Гарантируется, что суммарная длина всех строк не превосходит 106.
 

Выходные данные

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

Примечание
В первом примере у строк 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

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

Входные данные
Вводится слово, составленное Петей – строка из маленьких латинских букв не длиннее 15 символов.

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

Примеры

№	Входные данные	Выходные данные
1	solo	12

Рассмотрим таблицу размера MxN, в клетках которой стоят целые неотрицательные числа. Скажем, что таблица является симпатичной, если для всех i сумма чисел ее i-ой строки не превышает R_i, и для всех j сумма чисел ее j-го столбца не превышает Cj.

Вам задана таблица Z размера MxN, в некоторых клетках которой уже стоят целые неотрицательные числа. Найдите симпатичную таблицу с максимальной суммой элементов такую, что она совпадает с Z на тех клетках, в которых в Z стоят числа.

Входные данные
Первая строка входных данных содержит числа M и N (1 <= M, N <= 20). Следующая строка содержит M целых неотрицательных чисел - R₁, R₂, ..., R_M. Далее идет строка, содержащая N целых неотрицательных чисел C₁, C₂, ..., C_N. Все вводимые ограничения не превышают 106. Следующие M строк содержит по N целых чисел, которые задают Z. Если на некотором месте в таблице Z отсутствует число, то на этом месте во входных данных стоит  -1.

Выходные данные
Выведите найденную таблицу – M строк по N чисел. Если решения не существует, выведите единственное число -1.
 

Примеры

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

Имеется последовательность длины N: A1, A2, ..., AN. Изначально эта последовательность представляет собой перестановку 1, 2, ..., N. В этой последовательности Алиса может выполнить следующую операцию:
1) выбрать K последовательных элементов в последовательности;
2) затем заменить значение каждого выбранного элемента минимальным значением среди выбранных элементов.
Алиса хочет уравнять все элементы в этой последовательности, повторяя указанную выше операцию некоторое количество раз.
Найдите минимальное количество необходимых операций.
Можно доказать, что при ограничениях этой проблемы эта цель всегда достижима.

Входные данные
В первой строке задаются два целых числа N и K (2<=K<=N<=100000). Во второй строке задается последовательность целых чисел A1, A2, ..., AN - перестановка чисел от 1 до N (каждое число в последовательности различно, 1<=A_i<=N).

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

 

Примеры

№	Входные данные	Выходные данные
1	4 3 2 3 1 4	2
2	3 3 1 2 3	1
3	8 3 7 3 1 8 4 6 2 5	4

 

На стандартной шахматной доске (8х8) живут 2 шахматных коня: Красный и Зеленый. Обычно они беззаботно скачут по просторам доски, пощипывая шахматную травку, но сегодня особенный день: у Зеленого коня День Рождения. Зеленый конь решил отпраздновать это событие вместе с Красным. Но для осуществления этого прекрасного плана им нужно оказаться на одной клетке. Заметим, что Красный и Зеленый шахматные кони сильно отличаются от черного с белым: они ходят не по очереди, а одновременно, и если оказываются на одной клетке, никто никого не съедает. Сколько ходов им потребуется, чтобы насладиться праздником?

Входные данные
На вход программы поступают координаты коней, записанные по стандартным шахматным правилам (т.е. двумя символами - маленькая латинская буква (от a до h) и цифра (от 1 до 8), задающие столбец и строку соответственно).

Выходные данные
Требуется вывести наименьшее необходимое количество ходов, либо число -1, если кони не могут встретиться.

Примеры

№	Входные данные	Выходные данные
1	a1 a3	1

Дана таблица, состоящая из N строк и M столбцов. В каждой клетке таблицы записано одно из чисел: 0 или 1. Расстоянием между клетками (x1, y1) и (x2, y2) назовем сумму |x1-x2|+|y1-y2|. Вам необходимо построить таблицу, в клетке (i, j) которой будет записано минимальное расстояние между клеткой (i, j) начальной таблицы и клеткой, в которой записана 1. Гарантируется, что хотя бы одна 1 в таблице есть.

Формат входных данных
В первой строке вводятся два натуральных числа N и M, не превосходящих 500. Далее идут N строк по M чисел - элементы таблицы.

Формат выходных данных
Требуется вывести N строк по M чисел - элементы искомой таблицы.

Ушан с планеты Блук открыл пекарню. В его пекарне продается N видов тортов. Каждый вид торта имеет три параметра: «красота», «вкус» и «популярность». I-й вид торта имеет красоту xi, вкус yi и популярность zi. Эти значения могут быть нулевыми или отрицательными.
Громозека решил, что купит М кусочков торта. Он выбирает набор следующим образом:
- Нельзя использовать два и более куска одного и того же вида торта.
- При указанном выше условии выбирается набор тортов, который максимизирует (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности).
Найдите максимально возможное значение (абсолютное значение общей красоты) + (абсолютное значение общего вкуса) + (абсолютное значение общей популярности) для набора тортов, который выберет Громозека.

Входные данные
В первой строке через пробел записаны два целых числа N (1<=N<=1000) и M (0<=M<=N). В следующих N строках записано по  три целых числа xi, yi и zi (-10⁹<=xi, yi, zi <=10⁹, 1<=i<=N).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 3 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9	56	Подумайте о 2-м, 4-м и 5-м видах тортов. Общая красота, вкус и популярность будут следующими: Красота: 1 + 3 + 9 = 13 Вкус: 5 + 5 + 7 = 17 Популярность: 9 + 8 + 9 = 26 Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 13 + 17 + 26 = 56. Это максимальное значение.
2	5 3 1 -2 3 -4 5 -6 7 -8 -9 -10 11 -12 13 -14 15	54	Подумайте о том, чтобы иметь 1-й, 3-й и 5-й виды тортов. Общая красота, вкус и популярность будут следующими: Красота: 1 + 7 + 13 = 21 Вкус: (−2) + (- 8) + (- 14) = - 24 Популярность: 3 + (- 9) + 15 = 9 Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 21 + 24 + 9 = 54. Это максимальное значение.
3	10 5 10 -80 21 23 8 38 -94 28 11 -26 -2 18 -69 72 79 -26 -86 -54 -72 -50 59 21 65 -32 40 -94 87 -62 18 82	638	Если у нас есть 3-й, 4-й, 5-й, 7-й и 10-й виды тортов, общая красота, вкус и популярность будут -323, 66 и 249 соответственно. Значение (абсолютное значение общей красоты) + (абсолютное значение общей вкусовой привлекательности) + (абсолютное значение общей популярности) здесь равно 323 + 66 + 249 = 638. Это максимальное значение.
4	3 2 2000000000 -9000000000 4000000000 7000000000 -5000000000 3000000000 6000000000 -1000000000 8000000000	30000000000	Значения красоты, вкуса и популярности тортов, а также значение, которое будет напечатано, могут не соответствовать 32-битным целым числам.

 

Сегодня проходит памятный конкурс STCoder Contest 100. В этом случае Алиса хотела бы передать Громозеке целое число. Поскольку название конкурса - STCoder Contest 100, Громозека был бы счастлив, если бы ему дали положительное целое число, которое можно разделить на 100 ровно D раз. Найдите N-е наименьшее целое число, которое сделает Громозеку счастливым.

Входные данные
Во входной строке содержится два целых числа: D (равно 0, 1 или 2) и N (1<=N<=100).

Выходные данные
Выведите N-е наименьшее целое число, которое можно разделить на 100 ровно D раз.
 

 

Примеры

№	Входные данные	Выходные данные
1	0 5	5
2	1 11	1100
3	2 85	850000

 

Представьте данное число n в виде суммы двух кубов.

Входные данные
Программа получает на вход одно натуральное число n (n <= 1028).

Выходные данные
Программа должна вывести 2 целых неотрицательных числа (в порядке убывания), сумма кубов которых равна n. Если это невозможно, выведите строку impossible.
 

Примеры

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

Теорема Лагранжа утверждает, что любое натуральное число можно представить в виде суммы четырех точных квадратов. По данному числу n найдите такое представление: напечатайте от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число.

Входные данные
Программа получает на вход одно натуральное число n < 10000.

Выходные данные
Программа должна вывести от 1 до 4 натуральных чисел, квадраты которых дают в сумме данное число.

Примеры

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