1.Инверсии

Инверсией в последовательности чисел a1, a2, ..., aN называется ситуация, когда большее число стоит левее меньшего. Например, в последовательности 3, 4, 1, 2 имеется четыре инверсии: 3 и 1, 3 и 2, 4 и 1, 4 и 2.

Требуется создать такую перестановку натуральных чисел от 1 до N, чтобы в ней было ровно K инверсий.


Входные данные
В первой строке входных данных через пробел записаны целые числа N и K.

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

Гарантируется, что для заданных N и K искомая перестановка существует. Если правильных ответов несколько, выведите любой.

Система оценки

• Подзадача 1 (50 баллов): 1 ≤ N ≤ 10
• Подзадача 2 (25 баллов): 1 ≤ N ≤ 1000
• Подзадача 3 (25 баллов): 1 ≤ N ≤ 2 × 105

2.Быстрая сортировка
Для сортировки последовательности чисел широко используется быстрая сортировка - QSort. Ниже приведена программа на языке Pascal, которая сортирует массив a, используя данный алгоритм:

Хотя QSort является самой быстрой сортировкой в среднем, существуют тесты, на которых она работает очень долго. Будем оценивать время работы алгоритма количеством сравнений, сделанных с элементами массива (т.е. суммарным количеством сравнений в первой и втором while). Требуется написать программу, генерирующую тест, на котором быстрая сортировка сделает наибольшее число таких сравнений.


Входные данные
Цело число N (1 ≤ N ≤ 70000)

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


3.Количество инверсий

Дана последовательность неповторяющихся целых чисел. Инверсией назовём такую ситуацию, когда большее число стоит впереди меньшего. Например, в последовательности 4 3 2 5 1 всего 7 инверсий: 4 и 3, 4 и 2, 4 и 1, 3 и 2, 3 и 1, 2 и 1, 5 и 1. Ваша задача – определить количество инверсий в заданной последовательности.


Входные данные
В первой строке записано целое N – длина последовательности (1 ≤ N ≤ 50000). В следующей строке через пробел записаны N неповторяющихся целых чисел – члены последовательности. Каждое число лежит в диапазоне от 1 до 1000000.

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


4.Минимальный путь в таблице

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

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


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

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

После этого выведите строку, описывающую путь игрока. Строка должна содержать только символы R и D. Символ R говорит о том, что на очередном шаге надо пойти вправо, а символ D – вниз. В случае нескольких верных ответов выведите любой.

Ссылки на задачи:
https://codeforces.com/group/hOmOGUBB7I/contest/24...
https://codeforces.com/group/hOmOGUBB7I/contest/24...
https://codeforces.com/group/hOmOGUBB7I/contest/24...
https://codeforces.com/group/hOmOGUBB7I/contest/31...