Остатки

В калькулятор вводится натуральное число K и нажимается клавиша "+". Калькулятор всё ещё показывает K. Цель игры: получить на экране число, состоящее из одинаковых цифр. Для её достижения можно производить только одно действие - нажимать на клавишу "=" (возможно, 0 раз). После первого нажатия получается результат K + K, после очередного нажатия результат увеличивается на K. Требуется определить, удастся ли достичь цели, а если удастся, то какое число, состоящее из одинаковых цифр, будет получено первым. Количество отображаемых калькулятором цифр считать неограниченным, время работы батареек - тоже.

1 <= K <= 999.

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

Выходные данные
Если цели достичь невозможно, вывести "Impossible", если возможно, вывести два числа через пробел: цифру, из которой состоит искомое число, и количество цифр в числе.

Каждый член последовательности десятичных цифр d¹, d², d³..., начиная с четвёртого, равен последней цифре суммы трёх предыдущих. По заданным d¹, d², d³ найти N-й член последовательности.

Ограничения: 1 <= N <= 10¹⁵.

Входные данные
В первой строке находятся цифры d₁, d₂, d₃, разделённые пробелами, во второй - число N.

Выходные данные
Вывести одну цифру - d_N.

В последовательности чисел a₁, a₂, a₃, ... задан первый член, а остальные вычисляются по формуле a_i = (a_i - 1)2 mod 10 000. Найти N-й член последовательности.

Ограничения: 0 <= a₁ < 10 000, 1 <= N <= 2 000 000 000.

Входные данные
В первой строке находятся числа a₁ и N, разделённые пробелом.

Выходные данные
Вывести одно число - a_N.

Рассмотрим таблицу, состоящую из N строк и M столбцов. Если в каждой ячейке такой таблицы стоит целое число, назовем такую таблицу целочисленной матрицей. Скажем, что эта матрица кратна чиcлу p, если все числа в ее ячейках кратны p.

Рассмотрим теперь суммы элементов матрицы по строкам и столбцам соответственно. Обозначим сумму чисел i-й строки за Hi, а сумму чисел j-го столбца за Vj. Упорядоченный набор чисел (H₁, H₂, …, H_N, V₁, V₂, …, V_M) назовем профилем матрицы. Скажем, что матрица почти кратна p, если все числа, входящие в ее профиль, кратны p. Почти кратная 5 матрица и ее профиль изображены на рисунке 1.


Если две матрицы A и B имеют одинаковый размер, причем элемент, стоящий на пересечении i-й строки и j
-го столбца в матрице A отличается от соответствующего элемента матрицы B не более чем на p, скажем, что A отличается от B не более чем на p. Скажем, что матрица B похожа на матрицу A относительно числа p, если

1. отличается от не более чем на p
2. профили B и A совпадают.

На рисунке 2 изображены две похожие относительно числа 5 матрицы, первая из них почти кратна 5, а вторая кратна 5. Третья матрица на рисунке 2 тоже кратна 5, но непохожа на первую (хотя похожа на вторую).

Дано число p и почти кратная p матрица A. Ваша задача - найти такую матрицу B, чтобы она была кратна p и похожа на A относительно p.

Входные данные
В первой строке входных данных задаются целые числа p (1 <= p <= 10), N и M (1 <= N, M <= 30). Следующие N строк содержат по M целых неотрицательных чисел, не превышающих 1000, которые являются элементами исходной матрицы A.

Выходные данные
Выведите матрицу B по строкам - сначала M элементов первой строки, затем M элементов второй, и т. д. Разделяйте числа пробелами и/или переводами строк. Заботиться о красивом форматировании таблицы не надо. Если искомой матрицы не существует, выведите единственное число - "-1". Если решений несколько, выведите любое из них.

Фирма Macrohard разработала новый протокол обмена данными по сети. Каждый блок данных при этом обмене состоит из N
 чисел в диапазоне от 0 до M-1 включительно. Чтобы повысить надежность передачи, вместе с блоком данных пересылается контрольный блок такой же длины.

Предположим, что исходный блок состоит из чисел a₁, a₂,…,a_N. Тогда, контрольный блок состоит из чисел b1, b2,…,bN, из диапазона от 0 до M-1 включительно таких, что выполняются следующие равенства: b₁ = (a_N + b_N) mod M, b₂ = (a₁ + b₁) 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⁹). Следующая строка содержит блок данных, для которого следует построить контрольный блок, числа разделены пробелами.

Выходные данные
В первой строке выведите YES, если для данного блока данных можно построить контрольный блок, и NO, если нельзя. В случае, если контрольный блок построить можно, во второй строке выведите контрольный блок. Числа разделяйте пробелами. Если решений несколько, можно выдать любое из них.

Напишите рекурсивную функцию, возводящую число a в степень n. Гарантируется, что все числа "помещаются" в стандартные вещественные (a и ответ) и целые (n) типы.

Входные данные
Вводится 2 числа - a и n (число n может быть отрицательным).

Выходные данные
Необходимо вывести  значение aⁿ

Миша сидел на занятиях математики в Высшей школе экономики и решал следующую задачу: дано \(n\) целых чисел и нужно расставить между ними знаки \(+\) и \(\times\) так, чтобы результат полученного арифметического выражения был нечётным (например, между числами \(5\), \(7\), \(2\), можно расставить арифметические знаки следующим образом: \(5 \times 7 + 2 = 37\)). Так как примеры становились все больше и больше, а Миша срочно убегает в гости, от вас требуется написать программу решающую данную задачу.

Формат входных данных
В первой строке содержится единственное число \(n\) (\(2 \leq n \leq 10^5\)). Во второй строке содержится \(n\) целых чисел \(a_i\), разделённых пробелами (\(-10^9 \leq a_i \leq 10^9\)). Гарантируется, что решение существует.

Формат выходных данных
В одной строке выведите \(n - 1\) символ \(+\) или \(\times\), в результате применения которых получается нечётный результат. (Для вывода используйте соответственно знаки <<+>> (ASCII код—43) и <<x>> (ASCII код—120), без кавычек).

 

Дана последовательность из N чисел. Рассматриваются все её непрерывные подпоследовательности, которые содержат кратное K количество отрицательных чисел, заканчивающихся цифрой m. Найдите среди них подпоследовательность с максимальной суммой.  Программа должна вывести одно число – максимальную сумму элементов такой подпоследовательности. Гарантируется, что в исходной последовательности существует хотя бы K отрицательных чисел, заканчивающихся цифрой m.


Входные данные
В первой строке программа получается три числа: количество чисел в последовательности N (100 <= N <= 5000000), натуральное число K и натуральное число m (0 <= m <= 9). В каждой из следующих N строк записано одно целое число, не превышающее по модулю 10000. Гарантируется, что сумма любой подпоследовательности исходной последовательности не превышает по модулю 10⁹.

Выходные данные
Выведите на экран ответ на задачу.
 
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1

 

На вход программе подается последовательность целых чисел.  Рассматриваются все непрерывные подпоследовательности исходной последовательности, сумма элементов которых кратна K. Найдите количество таких подпоследовательностей. Гарантируется, что в последовательности такая подпоследовательность есть.

Входные данные
В первой строке записаны натуральные числа N (1 <= N <= 10⁸) и K (1 <= K <= 100 ). Каждая из следующих N строк содержит одно натуральное число, не превышающих 10000.

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

Примеры

№	Входные данные	Выходные данные
1	5 3 33 41 19 22 40	4

На детском празднике дети водили хороводы. Как только музыка закончила играть, дети всё ещё стояли в кругу. Тут Лена вспомнила, что родители дали ей коробку с k конфетками «Wilky May». Лена не жадина, поэтому она решила раздать все свои конфетки друзьям из хоровода. Лена знает, что некоторые её друзья сладкоежки, а некоторые нет. Сладкоежки берут из коробки две конфетки, если в коробке есть хотя бы две конфетки, а иначе берут одну. Остальные друзья Лены всегда берут ровно одну конфетку из коробки.

Чтобы начать раздавать конфетки, Лена вышла из хоровода, после чего в хороводе остались n ее друзей. Чтобы раздавать конфетки было проще, Лена присвоила каждому другу в хороводе номер в порядке по часовой стрелке, начиная с её лучшего друга Ромы, который получил номер 1.

Лена дала коробку другу, который получил номер l, после чего каждый друг Лены, начиная с друга с номером l, брал конфетки из коробки и передавал коробку следующему в порядке по часовой стрелке другу. После того, как друг с номером r взял конфетки, в коробке конфеток не осталось. Обратите внимание, что возможно, что некоторые друзья Лены брали конфетки из коробки несколько раз, то есть коробка могла пройти несколько полных кругов по хороводу.

Лена не знает, кто из ее друзей сладкоежки, но ее интересует, сколько максимум из её друзей могут быть сладкоежками. Если же такой ситуации не могло случиться, и Лена ошиблась в своих наблюдениях, сообщите ей об этом.

Входные данные
В единственной строке задаются четыре целых числа n, l, r, k (1 ≤ n, k ≤ 10¹¹ , 1 ≤ l, r ≤ n ) — количество детей в хороводе, номер друга, которому Лена отдала коробку конфет, номер друга, который взял последнюю конфетку, и количество конфет в коробке, соответственно.

Выходные данные
Выведите одно целое число — максимально возможное количество сладкоежек среди друзей Лены или « -1 » (без кавычек), если Лена ошиблась в своих наблюдениях.
 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	4 1 4 12	2	Любые два друга могут быть сладкоежками, тогда каждый два раза получит коробку конфет и последним, кто возьмёт конфету, будет четвёртый человек.
2	5 3 4 10	3	Сладкоежками могут быть любые три друга, кроме друга, стоящего на третьем месте.
3	10 5 5 1	10	Только один друг возьмёт одну конфетку, но он может быть сладкоежкой, просто он не может взять две конфеты. Все остальные в кругу тоже могут быть сладкоежками, но они не могут взять ни одной конфеты.
4	5 4 5 6	-1	Лена ошиблась и такой ситуации быть не могло.