У Пети в саду растет яблоня. Воодушевленный историей об Исааке Ньютоне, который, как известно, открыл закон всемирного тяготения после того, как ему на голову упало яблоко, Петя с целью повысить свою успеваемость по физике часто сидит под яблоней.
Однако, поскольку по физике у Пети твердая тройка, яблоки с его яблони падают следующим образом. В какой-то момент одно из яблок отрывается от ветки, на которой оно висит, и начинает падать строго вниз. Если в некоторый момент оно задевает другое яблоко, то то тоже отрывается от своей ветки и начинает падать вниз, при этом первое яблоко не меняет направление своего падения. Вообще, если любое падающее яблоко заденет другое яблоко на своем пути, то оно также начнет падать.
Таким образом, в любой момент каждое яблоко либо висит на ветке, либо падает строго вниз, причем все яблоки кроме первого, чтобы начать падать, должны сначала соприкоснуться с каким-либо другим падающим яблоком.
Выясните, какие яблоки упадут с Петиной яблони.
В первой строке вводится число \(N\) - количество яблок на Петиной яблоне (1 <= \(N\) <= 200). Следующие \(N\) строк содержат описания яблок. Будем считать все яблоки шарами. Каждое яблоко задается координатами своей самой верхней точки (той, где оно исходно прикреплено к дереву, длиной черенка пренебрежем) \(x_i\), \(y_i\) и \(z_i\) и радиусом \(r_i\) ( -10000 <= \(x_i\), \(y_i\), \(z_i\) <= 10000, 1 <= \(r_i\) <= 10000, все числа целые). Гарантируется, что изначально никакие яблоки не пересекаются (даже не соприкасаются). Ось OZ направлена вверх.
В первой строке выведите количество яблок, которые упадут с яблони, если начнет падать первое яблоко. В следующей строке выводите номера упавших яблок. Яблоки нумеруются, начиная с 1, в том порядке, в котором они заданы во входных данных.
4 0 0 10 4 5 0 3 1 -7 4 7 1 0 1 2 6
3 1 2 4
Фирма Macrohard разработала новый протокол обмена данными по сети. Каждый блок данных при этом обмене состоит из \(N\) чисел в диапазоне от 0 до \(M\)-1 включительно. Чтобы повысить надежность передачи, вместе с блоком данных пересылается контрольный блок такой же длины.
Предположим, что исходный блок состоит из чисел \(a_1\), \(a_2\),…,\(a_N\). Тогда, контрольный блок состоит из чисел \(b_1\), \(b_2\),…,\(b_N\), из диапазона от 0 до \(M\)-1 включительно таких, что выполняются следующие равенства: \(b_1\) = (\(a_N\) + \(b_N\)) mod \(M\), \(b_2\) = (\(a_1\) + \(b_1\)) mod \(M\), ... , \(b_N\) = (\(a_N\)-1 + \(b_N\)-1) mod \(M\) (обозначение \(X\) mod \(M\) обозначает остаток от деления \(X\) на \(M\), например, 7 mod 4 = 3, 6 mod 2 = 0).
Блоки данных, для которых нельзя построить контрольный блок, удовлетворяющий указанному свойству, считаются подозрительными и их передача по сети не разрешается.
Ваня хочет поступить на работу программистом в фирму Macrohard, и в качестве вступительного задания ему поручили написать процедуру построения контрольного блока для заданного блока данных. Помогите ему!
В первой строке вводятся числа \(N\) и \(M\) (1 <= \(N\) <= 1000, 2 <= \(M\) <= \(10^9\)). Следующая строка содержит блок данных, для которого следует построить контрольный блок, числа разделены пробелами.
В первой строке выведите YES, если для данного блока данных можно построить контрольный блок, и NO, если нельзя. В случае, если контрольный блок построить можно, во второй строке выведите контрольный блок. Числа разделяйте пробелами. Если решений несколько, можно выдать любое из них.
4 2 0 0 0 0
YES 0 0 0 0
4 2 0 1 0 0
NO
Петя склеил из \(N^3\) единичных кубиков большой куб размером \(N\) × \(N\) × \(N\). Устав от этой сложной работы, он отправился спать, а утром, проснувшись, с ужасом обнаружил, что его младший брат Ваня \(K\) раз проткнул куб спицей.
При этом Ваня действовал очень аккуратно, каждый раз установив конец спицы точно в центр грани какого-нибудь граничного единичного кубика, он протыкал куб параллельно соответствующей оси координат, при этом целый ряд из \(N\) кубиков оказывался испорчен.
Немного успокоившись после этого тяжелого потрясения, Петя заинтересовался, сколько кубиков в его творении осталось неповрежденными. Помогите ему ответить на этот сложный вопрос.
В первой строке вводятся числа \(N\) и \(K\) (1 <= \(N\) <= 1000, 0 <= \(K\) <= 150). Следующие K строк описывают Ванины преступные действия. Каждая строка содержит три числа - два из них представляют собой соответствующие координаты всех кубиков, проткнутых спицей, а третье, соответствующее координате, в направлении которой был проткнут куб, равно 0. Например, если \(N\) = 3, тройка (1, 0, 3) означает, что спицей были проткнуты кубики (1, 1, 3), (1, 2, 3) и (1, 3, 3). Все координаты лежат в пределах от 1 до \(N\). Известно, что Ваня никакое действие не выполнял два раза (т.е. никакая тройка не встретится во входных данных дважды).
Выведите единственное число - количество неповрежденных кубиков.
5 3 1 2 0 2 3 0 3 3 0
110