Алгоритмы

Найдите перестановку по её номеру в лексикографическом порядке.

Входные данные
В первой строке входных данных содержится число 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

На стандартной шахматной доске (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 в виде суммы двух кубов.

Входные данные
Программа получает на вход одно натуральное число 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

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

Входные данные
Задано единственное число N. (N ≤ 40)

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

Примеры

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

Со времен написания условия предыдущей задачи многое изменилось. Симпатичные узоры (о том, что это такое – см. задачу "Симпатичные узоры") стали очень популярны по всему миру, поэтому люди готовы содержать очень большой участок земли, лишь бы иметь на ней узор, не встречающийся больше нигде.

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

Так как масштабы буквально мировые, N <= 10¹⁰⁰. Однако Вася не любит большие числа, поэтому просит выдать ответ по модулю P.

Входные данные
В первой строке входных данных  содержатся три положительных целых числа, разделенные пробелом – N, M и P (1 <= N <= 10¹⁰⁰, 1 <= M <= 5, 1 <= P <= 10 000).

Выходные данные
Выведите  количество различных симпатичных узоров N x M по модулю P .

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

Для простоты будем считать, что все карты различны по номиналу, а также, что самая младшая карта побеждает самую старшую карту ("шестерка берет туза").

Игрок, который забирает себе карты, сначала кладет под низ своей колоды карту первого игрока, затем карту второго игрока (то есть карта второго игрока оказывается внизу колоды).

Напишите программу, которая моделирует игру в пьяницу и определяет, кто выигрывает. В игре участвует 10 карт, имеющих значения от 0 до 9, большая карта побеждает меньшую, карта со значением 0 побеждает карту 9.

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

Выходные данные
Программа должна определить, кто выигрывает при данной раздаче, и вывести слово first или second, после чего вывести количество ходов, сделанных до выигрыша. Если на протяжении 10⁶ ходов игра не заканчивается, программа должна вывести слово botva.

Примеры

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

Имеется сетка из N строк и N столбцов квадратов. Пусть (i, j) индексы клетки, которая расположена в i-й строке сверху и j-м столбце слева. Эти клетки должны быть окрашены в один из цветов C от цвета 1 до цвета C. Первоначально (i, j) окрашен в цвет ci,j. Назовем сетку хорошей, когда выполняются следующие условия для всех i, j, x, y, удовлетворяющих \(1<=i,j,x,y<=N\):
- если \((i+j)\%3=(x+y)\%3\), цвет (i, j) и цвет (x, y) совпадают;
- если \((i+j)\%3\neq(x+y)\%3\), цвет (i, j) и цвет (x, y) различны.
Здесь \(X \% Y \) представляет X по модулю Y.
Мы перекрасим ноль или более клеток, чтобы сетка была хорошей сеткой.
Неправильной клеткой назовем клетку, которая имела цвет X до перерисовки и Y после перекраски (DX,Y).
Найдите минимально возможную сумму всех неправильных клеток.

Входные данные
В первой строке задаются два целых числа N и C. В следующих C строках задаются по C значений Di,j. В последних N строках записаны N чисел в каждой строке - ci,j.

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	2 3 0 1 1 1 0 1 1 4 0 1 2 3 3	3	Перекрасить (1,1) в цвет 2. Неправильный (1,1) становится D 1,2 = 1. Перекрасить (1,2) в цвет 3. Неправильность (1,2) становится D 2,3 = 1. Перекрасить (2,2) в цвет 1. Неправильность (2,2) становится D. 3,1 = 1. В этом случае сумма неправильности всех квадратов равна 3. Отметим, что возможно \(Di, j  \neq D j, i \).
2	4 3 0 12 71 81 0 53 14 92 0 1 1 2 1 2 1 1 2 2 2 1 3 1 1 2 2	428

 

Чтобы затруднить снятие денег, банк на планете Крокрыс разрешает своим клиентам снимать только одну из следующих сумм за одну операцию:
- 1 крокрыскоин (действующая монета на планете Крокрыс);
- 6 крокрыскоинов, 36 (=6²) крокрыскоинов, 216(=6³) крокрыскоинов , ...;
- 9 крокрыскоинов, 81 (=9²) крокрыскоинов, 729(=9³) крокрыскоинов , ...
Сколько минимум операций требуется, чтобы вывести ровно N крокрыскоинов?
Невозможно повторно внести снятые вами деньги.

Входные данные
На вход подается целое число N (\(1<=N<=100000\)).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	127	4	При снятии 1 + 9 + 36 + 81 получится снять 127 крокрыскоина за 4 операции.
2	3	3	1+1+1 = 3, всего 3 операции
3	44852	16

 

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

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

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

Примеры

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

У нас есть сетка с H строками и W столбцами. Квадрат в i-й строке и j-м столбце будет называться Square(i, j). Целые числа от 1 до H·W записаны по всей сетке, а целое число, записанное в Square(i, j), равно Ai,j.
Вы - волшебник (волшебница), и можете телепортировать фигуру, помещенную на Square(i, j) в Square(x, y), потратив \(|x-i|+|y-j|\) маджиков (магических монет).
Теперь вам нужно пройти Q практических тестов на свои способности как волшебника (волшебницы). I-е испытание будет проводиться следующим образом:
- первоначально фигура располагается в квадрате, где записано целое число Li;
- пусть x будет целым числом, записанным в квадрате, занятом фигурой. Неоднократно переместите фигуру в квадрат, где написано целое число x+D, пока x не станет равен Ri. Тест заканчивается, когда x = Ri .
Гарантируется, что Ri- Li делится на D.
Для каждого теста найдите сумму маджиков, израсходованных во время этого теста.

Входные данные
В первой строке заданы три целых числа: H, W и D (\(1\leq H,W \leq 300\), \(1 \leq D \leq H \cdot W\)).
В следующих H строках записано по W чисел Ai,j (\(1 \leq A_{i,j} \leq H \cdot W\), \(A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))\).
В следующей строке записано целое число Q (\(1 \leq Q \leq 10^5\)).
В последних Q строках записано по 2 целых числа: Li и Ri (\(1 \leq L_i \leq R_i \leq H \cdot W\)), \((R_i-L_i)\) кратно D.

Выходные данные
Для каждого теста выведите сумму маджиков, израсходованных во время этого теста. Вывод должен быть в порядке проведения тестов.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснения
1	3 3 2 1 4 3 2 5 7 8 9 6 1 4 8	5	- 4 записано Square (1,2). - 6 записано в Square (3,3). - 8 записано in Square (3,1). Таким образом, сумма магических очков, израсходованных во время одного теста, составляет:  \((|3-1|+|3-2|)+(|3-3|+|1-3|)=5\).
2	4 2 3 3 7 1 4 5 2 6 8 2 2 2 2 2	0 0	Обратите внимание, что может быть тест, в котором фигура вообще не перемещается, и может быть несколько идентичных тестов.
3	5 5 4 13 25 7 15 17 16 22 20 2 9 14 11 12 1 19 10 6 23 8 18 3 21 5 24 4 3 13 13 2 10 13 13	0 5 0

 

Есть N человек. Имя i-го человека - Si . Мы хотим выбрать трех человек, чтобы выполнялись следующие условия:
- имя каждого выбранного человека начинается с M, А, R, С или Н; 
- среди выбранных людей нет людей, имена которых начинаются с одной буквы.
Сколько существует таких способов выбрать трех человек, не обращая внимания на порядок?

Входные данные
В первой строке записано целое число N (\(1<=N<=10^5\)) В следующих N строках записаны имена Si - строка, состоящая только из английских заглавных букв, длина строки не более 10 символов. Все имена различные.

Выходные данные
Выведите ответ на задачу. Обратите внимание, что ответ может не соответствовать 32-битному целочисленному типу.
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	5 MASHIKE RUMOI OBIRA HABORO HOROKANAI	2	Трех людей можно выбрать такими способами: - MASHIKE, RUMOI, HABORO - MASHIKE, RUMOI, HOROKANAI Ответ: 2
2	4 ZZ ZZZ Z ZZZZZZZZZZ	0
3	5 CHOKUDAI RNG MAKOTO AOKI RINGO	7

Весельчак У любит дарить алмазных черепашек. У него в сумке лежат черепашки либо трех цветов: розовый, белый и зеленый, либо четырех цветов: розовый, белый, зеленый и желтый. Он по очереди дарил черепашек из сумки, цвет i-й черепашки был Si. Цвета представлены следующим образом: P - розовый, W - белый, G - зеленый, Y - желтый. Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

Входные данные
В первой строке записано число N (\(1<=N<=100\)) - количество Черепашек, которое вынимал Весельчак У. Во второй строке содержатся N символов Si - цвета, вынимаемых черепашек. Каждый символ Si равен P, W, G или Y. Всегда существуют такие i, j и k, что Si = 'P', Sj = 'W' и Sk = 'G'.

Выходные данные
Если количество цветов черепашек в сумке было три, выведите Three; если цветов было четыре, выведите Four. 

 

Примеры

№	Входные данные	Выходные данные
1	6 G W Y P Y W	Four
2	9 G W W G P W P G G	Three
3	8 P Y W G Y W Y Y	Four

У Громозеки есть N часов. Стрелка i-х часов (\(1<=i<=N\)) поворачивается на 360 ° ровно за Ti секунд. Изначально стрелка всех часов стоит на месте и направлена прямо вверх. Громозека запускает все часы одновременно. Через сколько секунд стрелка всех часов снова укажет прямо вверх?

Входные данные
В первой строке записано целое число N (\(1<=N<=100\)). В следующих N строках записаны целые числа Ti (\(1<=T_i<=10^{18}\)), по одному числу в строке. 

Выходные данные
Выведите на экран ответ. Гарантируется, что ответ не превышает \(10^{18}\).
 

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	2 2 3	6	У нас есть двое часов. Время, когда стрелка каждых часов указывает вверх, выглядит следующим образом: Часы 1: 2, 4, 6, ... секунд после начала. Часы 2: 3, 6, 9, ... секунд после начала. Таким образом, требуется 6 секунд, пока стрелки обоих часов снова не укажут прямо вверх.
2	5 2 5 10 1000000000000000000 1000000000000000000	1000000000000000000

 

Дано целое число N (\(1<=N<=10^{10}\)).
Для двух положительных целых чисел A и B определим \(F (A, B)\) как большее из двух: 
- количество цифр в десятичной записи числа A;
- количество цифр в десятичной записи числа B.
Например, \(F (3,11) = 2\), поскольку 3 состоит из одной цифры, а 11 - из двух.
Найдите минимальное значение \(F (A, B)\) среди всех пар положительных целых чисел A и B, таких что \(N = A \cdot B\).

Входные данные
На вход подается целое число N (\(1<=N<=10^{10}\)).

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

 

Примеры

№	Входные данные	Выходные данные	Пояснение
1	10000	3	\(F(A,B) \) имеет минимальное значение при \((A,B)=(100,100)\).
2	1000003	7	Есть две пары A и B, таких чтобы выполнялость условие задачи: \((1,1000003)\) и \((1000003,1)\). Для этих пар, \(F(1,1000003)=F(1000003,1)=7\).
3	9876543210	6

 

Пусть a₁ = 2, a₂ = 3, a_n = a_1·a₂·...·a_n-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.<

Входные данные
Вводится одно натуральное число X, 1 < X ≤ 10⁹.

Выходные данные
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.
 

Примеры

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

Рассмотрим фигуру, аналогичную показанной на рисунке (большой равносторонний треугольник, составленный из маленьких равносторонних треугольников). На рисунке приведена фигура, состоящая из 4-х уровней треугольников.



Напишите программу, которая будет определять, сколько всего в ней треугольников (необходимо учитывать не только "маленькие" треугольники, а вообще все треугольники — в частности, треугольник, выделенный жирным, а также вся фигура, являются интересующими нас треугольниками).

Входные данные
Вводится одно число N — количество уровней в фигуре (1 ≤ N ≤ 100000).

Выходные данные
Выведите  количество треугольников в такой фигуре.

Примеры

№	Входные данные	Выходные данные
1	1	1
2	2	5
3	4	27