#551

Контрольный блок

Темы: [Остатки]

Источники: [ Командные олимпиады, ВКОШП, 2001, Задача G ]

Дана последовательность чисел A1, ..., An. Требуется построить последовательность B, где B1 = (An+Bn) mod M, B2 = (A1+B1), ..., Bn = (An-1 + Bn-1).

Фирма 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

#552

Куб

Темы: [Одномерные массивы] [Условный оператор (if)]

Источники: [ Командные олимпиады, ВКОШП, 2001, Задача H ]

Есть куб состоящий из единичных кубиков. Заданы наборы кубиков, проткнутые спицей вдоль одной из осей. Требуется подсчитать количество оставшихся кубиков.

Петя склеил из \(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\). Известно, что Ваня никакое действие не выполнял два раза (т.е. никакая тройка не встретится во входных данных дважды).

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

Выведите единственное число - количество неповрежденных кубиков.

Примеры

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

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

#559

Номер месяца

Темы: [Условный оператор (if)]

Источники: [ Командные олимпиады, Школьная командная олимпиада ФМШ № 2007 г.Москвы, 10-11 классы, 2007-2008, Задача A ]

По заданному числу определить название месяца.

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

Вводится одно натуральное число \(N\), 1 ≤ \(N\) ≤ 12

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

Программа выводит КОД месяца согласно таблице:

Примеры

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

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

YAN

#560

Змей Горыныч

Темы: [Условный оператор (if)]

Источники: [ Командные олимпиады, Школьная командная олимпиада ФМШ № 2007 г.Москвы, 10-11 классы, 2007-2008, Задача B ]

Илья Муромец идет на битву со Змеем Горынычем. У Змея Горыныча \(М\) голов, Илья Муромец за один удар отрубает \(N\) голов, после удара Змей Горыныч регенерирует \(K\) голов. Далее процесс повторяется, пока головы не кончатся.

Напишите программу, которая определяет, сможет ли Илья Муромец одолеть Змея Горыныча и, если да, то сколько ударов для этого потребуется.

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

Программа получает три числа, записанных через пробел — \(N\), \(M\) и \(K\) (1 ≤ \(N\) , \(M\), \(K\) ≤ \(10^9\)), где \(N\) – число голов, которые Илья Муромец срубает одним ударом, \(M\) – число голов Змея Горыныча, \(K\) – число голов, которые Змей Горыныч регенерирует за раз.

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

Вывести число ударов, которые должен нанести Илья Муромец, чтобы убить Змея Горыныча. Если одолеть Змея Горыныча при заданных исходных данных невозможно, то следует вывести «NO» (без кавычек заглавными буквами).

Примеры

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

3 6 2

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

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

5 10 6

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

NO

#561

Двоичные числа

Темы: [Перебор]

Источники: [ Командные олимпиады, Школьная командная олимпиада ФМШ № 2007 г.Москвы, 10-11 классы, 2007-2008, Задача C ]

Найдите количество чисел \(Z\), удовлетворяющих неравенству \(A\) ≤ \(Z\) ≤ \(B\), таких, что в записи \(Z\) в двоичной системе счисления используется ровно 2 единицы. Например, если \(A\)=10; \(B\)=20; то таких чисел 5 (это числа \(10=1010_2\); \(12=1100_2\); \(17=10001_2\); \(18=10010_2\); \(20=10100_2\)).

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

На вход программы поступают два числа, записанных через пробел — \(A\), \(B\) ( 0 ≤ \(A\), \(B\) ≤ \(10^9\))

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

Выведите одно число – количество чисел \(Z\).

Примеры

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

10 20

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