Алгоритмы

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

В первой строке записаны два числа N и M - размеры таблицы (1<=N<=100, 1<=M<=100). Далее записаны N строк по M чисел в каждой - размеры штрафов в у.е. за прохождение через соответствующие клетки (каждое число от 0 до 100).

Первая строка выходных данных содержит максимальную возможную сумму, вторая – маршрут, на котором достигается эта сумма. Маршрут выводится в виде последовательности, которая должна содержать N-1 букву D, означающую передвижение вниз и M-1 букву R, означающую передвижение направо. Если таких последовательностей несколько, необходимо вывести ровно одну (любую) из них.

Примеры

5 5
9 9 9 9 9
3 0 0 0 0
9 9 9 9 9
6 6 6 6 8
9 9 9 9 9

74
D D R R R R D D 

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

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

Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел ai - количество магической энергии в i-м доме.

Ограничения на входные данные 

• 1 <= n <= 100
• 0 <= a[i] <= 1000
• 1 <= i <= n

Выходные данные
Выведите максимальное количество магической энергии, которую вы сможете собрать. 
 

Примеры

Вы - маг, странствующий по волшебному лесу, в поисках своей утраченной магической силы. Эта магическая сила находится в волшебных кристаллах, которые растут на деревьях в этом волшебном лесу. На каждом дереве растет только один волшебный кристалл. Так как вы маг, то вы знаете какой силой обладает тот или иной кристалл, растущий на определенном дереве в этом лесу. Вы хотите получить в этом лесу как можно больше магической силы. Для этого вам следует выполнить следующее действие любое количество раз:

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

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

Входные данные
Первая строка входных данных содержит число n - количество деревьев в волшебном лесу. Вторая строка содержит n чисел ai - волшебная сила кристалла на i-м дереве.

Ограничения на входные данные

• 1 <= n <= 2 * 104
• 1 <= a[i] <= 104
• 1 <= i <= n

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

Примеры

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

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

Входные данные
В первой строке записано число n - количество домой вдоль улицы. Во второй строке - n целых чисел ai - количество магической энергии в i-м доме.

Ограничения на входные данные 

• 1 <= n <= 100
• 0 <= a[i] <= 400
• 1 <= i <= n

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

Примеры

Примеры

tree

eert

cccaaa

aaaccc

Aabb

bbAa

Примеры

silvertests

sstt

Примеры

Примеры

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

В первой строке записаны через пробел размеры двумерного массива: количество строк N и количество столбцов M ( 1 <= N , M <= 100 ). В следующих N строках записаны строки двумерного массива, в каждой – по M натуральных чисел, разделённых пробелами. 
 

Программа должна вывести отсортированный двумерный массив.
 

Примеры

5 7
13 5 1 8 4 14 5 
5 13 10 9 3 7 7 
3 3 9 6 3 7 5 
10 8 11 2 1 1 13 
1 12 13 15 9 11 4 

1 1 1 1 2 3 3 
3 3 4 4 5 5 5 
5 6 7 7 7 8 8 
9 9 9 10 10 11 11 
12 13 13 13 13 14 15 

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

В первой строке записано одно число N размер квадратной матрицы ( 1 <= N <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по N натуральных чисел, разделённых пробелами. 
 

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

Примеры

5
12 4 8 13 13 
1 12 1 4 15 
2 3 5 2 3 
6 5 13 12 14 
14 9 15 4 12 

12 4 8 13 14 
1 12 1 13 15 
2 3 5 2 3 
6 5 13 12 14 
4 9 15 4 12

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

В первой строке записано одно число N размер квадратной матрицы ( 1 <= N <= 100 ). В следующих N строках записаны строки матрицы, в каждой – по N натуральных чисел, разделённых пробелами. 
 

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

Примеры

5
1 11 11 5 10 
2 9 2 10 2 
12 9 10 9 15 
6 15 14 1 11 
11 12 4 9 3 

1 11 11 5 10 
2 1 2 10 2 
12 9 3 9 15 
6 15 14 9 11 
11 12 4 9 10

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i², у профессора Селезнева i-й член последовательности равен i³. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз. 

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности. 

В единственной строке входного файла дано натуральное число i (1 <= i <= 10⁷).

Выведите i-е число новой последовательности. 

Примеры

Примеры

Алиса со своим отцом профессором Селезневым записывают на листочке числа определенной последовательности. У Алисы каждый i-й член последовательности равен i², у профессора Селезнева i-й член последовательности равен i³. Они решили создать новую возрастающую последовательность путем объединения двух своих последовательностей. При этом, если в обоих последовательностях есть одинаковое число, то в новой последовательности оно присутствует только один раз. 

Алиса и профессор просят вас угадать i-е число в новой объединенной последовательности. 

В единственной строке входного файла дано натуральное число i (1 <= i <= 10⁷).

Выведите i-е число новой последовательности. 

Примеры

Отсортируйте данный массив, используя сортировку слиянием.

Примеры

Даны два массива arr1 и arr2. Элементы массива arr2 различны, и при этом все элементы arr2 содержатся в arr1.

Отсортируйте элементы массива arr1 таким образом, чтобы относительный порядок элементов в массиве arr1 был таким же, как в массиве arr2. Элементы, которых нет в массиве arr2 должны располагаться в конце массива arr1 в порядке возрастания.

• 1 <= n, m <= 106
• 0 <= arr1[i], arr2[i] <= 1000
• Все элементы массива arr2 различны.
• Каждый элемент массива arr2[i] содержится в массиве arr1.

Примеры

Дано целое число  N<=10³ и N целых чисел. необходимо найти три числа, произведение которых максимально.

Если таких троек чисел несколько, выведите любую из них. 

Входные данные
В первой строке задано целое число 3 <= N <= 10³ - количество элементов в списке.
Во второй строке заданы N целых  элементов списка, не превосходящих по модулю 30000.

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

Примеры

Примеры

Примеры

Чебурашка обожает мандарины. Сейчас он оказался на новогодней ярмарке среди большого количества ящиков с мандаринами. В i-м ящике bi мандаринов. Ярмарка начинает свою работу через h часов.

Чебурашка очень умный и может выбрать скорость поедания мандаринов -  k мандаринов в час. Затем он каждый час выбирает ящик мандаринов и уплетает k штук из этого ящика. Если в ящике меньше k мандаринов, то Чебурашка съест их все и больше не притронется ни к одному мандарину в течение этого часа.

Чебурашка любит есть медленно, но желает съесть все мандарины до открытия ярмарки.

Помогите найти Чебурашке минимальную скорость поедания мандаринов, но такую, чтобы он все-таки смог съесть все мандарины.
 

Примеры