Арифметические алгоритмы (Теория чисел)

Даны два целых неотрицательных числа: M и N. Найти их сумму.

Входные данные
В первой строке содержится M, во второй - N. 0 <= M, N < 10³⁰⁰⁰⁰.

Выходные данные
В первой строке вывести сумму без пробелов и ведущих нулей.

Для натуральных чисел a и n вычислить aⁿ.

Входные данные
В первой строке находятся разделённые пробелом a и n. 1 <= a <= 9, 1 <= n <= 7000.

Выходные данные
Выводится одно число - результат без стоящих впереди нулей, стоящих впереди и позади пробелов.

Крупная межгалактическая сеть мебельных магазинов Galactic-Мебель недавно вышла на рынок мебели для кухонь в звездной системе LoST-2007. В этой звездной системе во всех квартирах кухни имеют форму прямоугольника размером a на b метров. При этом вдоль одной из стен принято ставить стол, в смежной с ней стене находится окно. Таким образом, для размещения различных кухонных шкафчиков остается угол со сторонами a и b метров.

Для экономии места в этой звездной системе принято ставить шкафчики вплотную друг к другу и к углу кухни. Кроме этого, сами шкафчики встраиваются внутрь стены, то есть вдоль стены расположены только их дверцы.

В звездной системе LoST-2007 используется n типов кухонных шкафчиков. Каждый тип шкафчиков характеризуется своей шириной wi, при этом на кухне должен присутствовать ровно один экземпляр каждого типа шкафчиков.

Недавно директор маркетингового отдела Galactic-Мебель заметил, что он может предложить клиентам несколько вариантов расположения шкафчиков на кухне. Различными считаются варианты, которые отличаются расположением хотя бы одного шкафчика. При этом шкафчики различных типов могут иметь одинаковую ширину, однако отличаются внешней отделкой. Так что даже размещения, которые отличаются лишь позициями шкафчиков с равной шириной, считаются различными. Например, пусть a = 3, b = 4 и есть два типа шкафчиков, шириной 1 и 2, соответственно.


Тогда возможно шесть планировок кухни. Возможные планировки показаны на рисунке.

Требуется по заданным размерам кухни и шкафчиков найти число различных планировок.

Входные данные
Первая строка содержит три целых числа: a, b и n (1 ≤ a ≤ 300, 1 ≤ b ≤ 300, 1 ≤ n ≤ 100). Каждая из следующих n строк содержит целое число w_i (1 ≤ w_i ≤ 300) — ширину соответствующего шкафчика.

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

Строительная компания хочет построить дом, в котором будет n квадратных комнат. Каждая комната характеризуется своим размером — длиной стены. Обозначим размеры комнат в новом доме как a₁, a₂, …, a_n.

При этом для того, чтобы квартиры в доме активнее распродавались, компания объявила его «Домом оригинальности и гармонии». Оригинальность означает, что размер любой комнаты не должен делиться на размер никакой другой комнаты. Свойство гармонии требует, чтобы площадь любой комнаты делилась на размер каждой из комнат. Иначе говоря, для любых различных i и j должны выполняться условия: ai не делится на a_j, а a_i² делится на a_j.

Требуется по заданному числу n выбрать такие размеры комнат, чтобы выполнялись свойства оригинальности и гармонии. При этом с целью экономии строительных материалов размер каждой комнаты не должен превышать 2⁶³ – 1.

Входные данные
Строка содержит число n (1 ≤ n ≤ 1000).

Выходные данные
Выведите размеры комнат — n положительных целых чисел, не превосходящих 2⁶³ – 1. Разделяйте числа пробелами.

Рассмотрим таблицу, состоящую из 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, если нельзя. В случае, если контрольный блок построить можно, во второй строке выведите контрольный блок. Числа разделяйте пробелами. Если решений несколько, можно выдать любое из них.

Ваня и Петя играют в следующую игру. Ваня пишет на бумаге какую-либо перестановку чисел от 1 до N (то есть выписывает все числа от 1 до N в некотором порядке) и расставляет на столе в ряд N предметов. После этого Петя переставляет предметы в соответствии с Ваниной перестановкой. А именно, Петя выполняет следующие действия: если i-ое число в Ваниной перестановке равно a_i, то Петя ставит предмет, который стоит на i-ом месте, на место с номером a_i.

Обозначим предметы числами от 1 до N. Тогда начальное расположение предметов можно обозначить последовательностью чисел (1, 2, ..., N). К примеру, если N = 5, то начальное расположение предметов есть (1, 2, 3, 4, 5). Пусть Ваня написал перестановку <2, 5, 4, 3, 1>. Это значит, что после перемещения предметов они окажутся расставлены в следующем порядке: (5, 1, 4, 3, 2).

Однако, переставив предметы, Петя не останавливается на достигнутом и вновь переставляет их в соответствии с Ваниной перестановкой. Снова, если i-ое число в Ваниной перестановке равно a_i, то Петя ставит предмет, который стоит на i-ом месте на место с номером a_i. Так, если в приведенном выше примере повторно применить перестановку, предметы окажутся расположены в следующем порядке: (2, 5, 3, 4, 1).

Таким образом, Петя переставляет предметы в соответствии с Ваниной перестановкой, пока их расположение не окажется таким же, как исходное. В нашем примере Пете потребуется сделать еще 4 действия, порядок предметов после каждого из них будет следующим: (1, 2, 4, 3, 5), (5, 1, 3, 4, 2), (2, 5, 4, 3, 1), (1, 2, 3, 4, 5). Всего Пете потребовалось применить перестановку 6 раз.

Добрый Ваня хочет, чтобы Пете пришлось выполнить как можно больше действий. Помогите ему выбрать соответствующую перестановку.

Входные данные
Вводится единственное целое число N - количество предметов (1 <= N <= 100).

Выходные данные
Выведите перестановку чисел от 1 до N такую, что количество действий, которое придется сделать Пете, максимально. Если таких перестановок несколько, можно вывести любую.

Известно, что сложение и умножение являются ассоциативными операциями. Это значит, что значение выражений вида \(a_1+a_2+\ldots +a_n\) и \(a_1\cdot a_2 \cdot \ldots \cdot a_n\) не зависит от порядка выполнения в них действий и следовательно не меняется при произвольной расстановке в этих выражениях скобок.

В отличии от сложения и умножения, деление — операция не ассоциативная. Так, значение выражения вида \(a_1/a_2/\cdots /a_n\) может меняться при расстановке в нем скобок.

Рассмотрим выражение вида \[p_1 / p_2 / \cdots / p_n,\] где все \(p_i\) — простые числа (не обязательно различные). Найдите количество возможных значений, которые может принять указанное выражение после расстановки в нем скобок, а также количество целых чисел среди этих значений.

Например, выражение \(3/2/2\) после расстановки скобок может принять два значения: \(3/4 = (3 / 2) / 2\) и \(3 = 3 / (2 / 2)\).

Формат входных данных
Первая строка содержит число \(n\) (\(1 \le n \le 200\)). Следующая строка содержат \(n\) натуральных чисел — \(p_1, p_2, \dots, p_n\). Все числа \(p_i\) простые и не превосходят \(10^4\).

Формат выходных данных
На первой строке выведите количество возможных значений, которые может принять выражение \(p_1 / p_2 / \cdots / p_n\) при заданных \(p_i\) после расстановки в нем скобок. На второй строке выведите количество целых чисел среди этих значений.

Ребята во дворе решили поиграть в прятки. Чтобы выбрать ведущего, который будет искать, они решили воспользоваться считалкой. Считалка состоит из \(k\) слов, и используется следующим образом.

Все \(n\) ребят становятся в круг и один из них, начиная с себя, по очереди указывает на ребят в порядке, в котором они стоят по кругу, называя слова считалки. Тот, на кого указывает считающий, называя последнее слово считалки, выбывает из круга. После этого считалка повторяется сначала, а счет начинается со следующего за выбывшим. Так продолжается до тех пор, пока в круге не останется один человек. Он то и будет ведущим.

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

Ребята заметили это только тогда, когда после очередного повторения считалки считающий снова указал на последнем слове на участника, который уже должен был покинуть круг. Теперь их заинтересовал вопрос — а на скольких ребят в этот момент считающий все еще не указал, что они должны покинуть круг.

Помогите им ответить на этот вопрос.

Формат входных данных
Строка содержит два целых числа — \(n\) и \(k\) (\(1 \le n \le 1000\), \(1 \le k \le 10^9\)).

Формат выходных данных
Выведите одно число — количество ребят, на которых ведущий, еще не указал, что они должны покинуть круг, когда ведущий повторно укажет на кого-либо на последнем слове считалки.

Широкое распространение в стандартных библиотеках многих языков программирования получила реализация сбалансированных деревьев на основе так называемых красно-черных деревьев. В данной задаче вам предлагается посчитать количество красно-черных деревьев заданной формы.

Напомним, что двоичным деревом называется набор вершин, организованных в виде дерева. Каждая вершина имеет не более двух детей, один из которых называется левым, а другой — правым. Как левый, так и правый ребенок, а также оба могут отсутствовать.

Если вершина \(Y\) — ребенок вершины \(X\), то говорят, что вершина \(X\) является родителем вершины \(Y\). У каждой вершины дерева, кроме одной, есть ровно один родитель. Единственная вершина, не имеющая родителя, называется корнем дерева.

Соединим каждую вершину кроме корня с ее родителем. Заметим, что для каждой вершины существует ровно один путь, ведущий в нее от корня.

Двоичное дерево называется красно-черным, если каждая его вершина раскрашена в красный либо в черный цвет, причем выполняются следующие условия:

1. если вершина красная, то ее родитель — черный;

2. количество черных вершин на пути от корня до любой вершины, у которой отсутствует хотя бы один ребенок, одно и то же.

Примеры двоичного дерева, вершины которого раскрашены в два цвета, приведены на следующем рисунке.

Если считать закрашенные вершины черными, а незакрашенные — красными, то дерево на рисунке (а) является красно-черным деревом, а деревья на рисунках (б) и (в) — нет. Для дерева на рисунке (б) нарушается первое свойство — у красной вершины 5 родитель 2 также красный, а в дереве на рисунке (в) нарушается второе свойство — на пути от корня до вершины 1 одна черная вершина, а, например, на пути от корня до вершины 3 — две.

Для заданного двоичного дерева подсчитайте число способов раскрасить его вершины в черный и красный цвет так, чтобы оно стало красно-черным деревом.

Формат входных данных
Первая строка содержит число \(n\) — количество вершин в дереве (\(1 \le n \le 1000\)).

Пусть вершины дерева пронумерованы числами от \(1\) до \(n\). Следующие \(n\) строк содержат по два числа — для каждой вершины заданы номера ее левого и правого ребенка. Если один из детей отсутствует, то вместо его номера записан ноль. Гарантируется, что входные данные корректны, то есть набор чисел действительно задает двоичное дерево.

Формат выходных данных
Выведите одно число — количество способов раскрасить вершины заданного во входном файле двоичного дерева в красный и черный цвета так, чтобы оно стало красно-черным деревом.

Все допустимые способы раскрасить вершины дерева из первого примера приведены на следующем рисунке.

В ЛКШ Витя решил переселять комнаты каждый месяц. Известно какая комната в какую переезжает. Требуется определить целое число лет, которое пройдет прежде чем все окажутся снова в своих комнатах.

Входные данные
В первой строке записано N - количество комнат (1 < N < 101) и далее номера комнат, в которые переезжают 1,2,3,..,N-я комнаты. СЭС не потерпит беспорядка, поэтому все переезды корректны (в каждую комнату переедет ровно одна комната).

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

Переведите число {1} из 10-й СС в двоичную СС
 

Миша сидел на занятиях математики в Высшей школе экономики и решал следующую задачу: дано \(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), без кавычек).

 

Банк «Кисловодск» переходит на новый вид банковских карт. Для этого производятся одинаковые заготовки, на которых есть специальное место для идентификации клиента. Изначально на этом месте записывается кодовое число X. В банке с помощью специального прибора можно стирать некоторые цифры числа X. Оставшиеся цифры, будучи записанными подряд, должны образовывать номер счета клиента. Например, при X = 12013456789 номера счетов 5, 12, 17 или 12013456789 получить можно, а номера 22 или 71 получить нельзя.

Способ распределения номеров счетов в банке очень прост. Счетам присваиваются последовательно номера 1, 2, … Очевидно, что при таком способе в какой-то момент впервые найдется номер счета N, который нельзя будет получить из цифр X указанным выше способом. Руководство банка хочет знать значение N.

Напишите программу, которая находила бы N по заданному X.

Формат входных данных
Вводится натуральное число X без ведущих нулей (1 ≤ X ≤ 101000). 

Формат выходных данных
Выведите искомое N без ведущих нулей.

Найдите и выведите в возрастающем порядке все несократимые обыкновенные дроби \(f\) со знаменателем не превышающим \(n\), которые удовлетворяют неравенству \(1/p < f < 1/q\).

Формат входных данных
На ввод подается три числа: \(n\), \(p\) и \(q\) (\(1 \le n \le 100\), \(1 \le q < p \le 100\)).

Формат выходных данных
Выведите все искомые дроби, по одной на строке.

Переведите {1}  из десятичной системы счисления в двоичную систему счисления.

Дана последовательность из 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

Напишите программу, переводящую число из двоичной системы счисления в шестнадцатеричную

Входные данные
Программа получает на вход строку, состоящую из нулей и единиц, длина которой не превосходит 4000 символов. Первый символ строки всегда единица. Данная строка является двоичной записью некоторого числа.

Выходные данные
Необходимо записать в шестнадцатеричном виде и вывести данное число с использованием цифр 0, ..., 9 и букв A, ..., F без лидирующих нулей.

Примеры

№	Входные данные	Выходные данные
1	10100	14

На Марсе используют систему счисления с основанием k . В отличие от привычной нам десятичной системы счисления, в этой системе счисления k цифр со значениями от 0 до k - 1 , а вес цифры в i -м разряде равен k_i .

Например, пусть k = 8 . Запись 357₈ означает число 3·8 2 + 5·8 + 7 , в более привычной землянам десятичной системе счисления это число записывается как 239₁₀ . А число 192₁₀ , в системе счисления с основанием 8 записывается как 300₈ .

Ильдар — юный марсианин, и он очень любит круглые числа. Ильдар называет число достаточно круглым , если его запись в системе счисления с основанием k заканчивается хотя бы на n нулей. Сегодня Ильдар хочет найти i -е по порядку достаточно круглое число.

Помогите Ильдару, найдите i -е достаточно круглое в системе счисления с основанием k натуральное число и выведите его в десятичной системе счисления. Ильдар очень дружелюбен и гарантирует, что ответ в десятичной системе счисления не превосходит 10¹⁸ .

Входные данные
Все ограничения на числа в этой задаче заданы в десятичной системе счисления. Все числа во вводе также записаны в десятичной системе счисления.

Первая строка входных данных содержит число k — основание системы счисления, которую использует Ильдар ( 2 ≤ k ≤ 10⁹ ).

Вторая строка входных данных содержит число n — минимальное количество нулей на конце достаточно круглого числа ( 0 ≤ n ≤ 100 ).

Третья строка входных данных содержит число i — порядковый номер достаточно круглого числа, которое интересует Ильдара ( 1 ≤ i ≤ 10⁹ ).

Выходные данные
Выведите одно число — запись в десятичной счистеме счисления i -го по порядку достаточно круглого в системе счисления с основанием k натурального числа. Гарантируется, что ответ не превышает 10¹⁸ .

Обратите внимание, что ответ может не поместиться в стандартный 32-битный тип данных. Надо использовать 64-битный тип, в паскале он называется « int64 », в C++ « long long », в Java « long ». Если вы пишете на языке Python, то волноваться не надо, в Python встроенный целочисленный тип не имеет ограничений на величину числа.
 

№	Входные данные	Выходные данные
1	8 2 2	192