#111629

Ровно К обменов - 2

Темы: [Сортировка "пузырьком"]

Даны два числа n и k . Вывести перестановку из n чисел ( n чисел от 1 до n без повторений) такую, чтобы сортировка пузырьком по возрастанию на соответствующем массиве сделала ровно k обменов. Если возможных ответов несколько –– выведите любой.

Входные данные

Даны натуральное число n ( n ≤ 10 ⁵ ) и целое неотрицательное k . Гарантируется, что для всех наборов тестовых данных решение существует.

Выходные данные

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

Примеры

Входные данные

5 3

Выходные данные

1 5 2 3 4

#111630

Середина

Темы: [Алгоритмы сортировки]

Какое число окажется в середине, если расставить элементы массива по возрастанию?

Входные данные

В первой строке дано одно натуральное нечетное число n ( 1 ≤ n < 1000 , n — нечетное) — количество элементов массива. Во второй строке через пробел перечислены элементы массива — натуральные числа, не превышающие 10 ⁹ .

Выходные данные

Выведите одно число — ответ на задачу

Примеры

Входные данные

5
6 2 7 4 2

Выходные данные

#111631

Сначала четные

Темы: [Алгоритмы сортировки]

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

Решите задачу, используя стандартную сортировку с компаратором (в Python - с помощью key).

Входные данные

В первой строке дано одно натуральное число n ( 1 ≤ n ≤ 100 ) — количество элементов массива. Во второй строке через пробел перечислены элементы массива — натуральные числа, не превышающие 10 ⁹ .

Выходные данные

В одной строке выведите массив, отсортированный заданным образом. Числа разделяйте пробелами.

Примеры

Входные данные

4
3 2 1 2

Выходные данные

2 2 1 3

#111632

План обменов

Темы: [Алгоритмы сортировки]

Дан массив. Ваша задача вывести план сортировки этого массива по неубыванию. Одно действие характеризуется двумя числами — индексами обмениваемых элементов. То есть, если выведено 1-3, это значит, что нужно поменять местами первый и третий элементы массива. Массив индексируется с единицы

Входные данные

В первой строке дано одно натуральное нечетное число n ( 1 ≤ n ≤ 10 ⁴ ) — количество элементов массива. Во второй строке через пробел перечислены элементы массива — натуральные числа, не превышающие 10 ⁹ .

Выходные данные

Выведите не более 10 ⁵ строк, в каждой из которых выведите по два различных числа, разделенных дефисом — индексы обмениваемых ячеек. Если возможных ответов несколько — выведите любой.

Примеры

Входные данные

4
3 5 1 4

Выходные данные

3-1
3-2
4-3

#111634

Робот

Темы: [Строки] ["Два указателя"]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2013, 1 день, Задача B ]

Студенты одного из вузов спроектировали робота для частичной автоматизации процесса сборки авиационного двигателя.

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

Предполагается использовать робота один раз для выполнения части подряд идущих операций из процесса сборки.

Память робота состоит из K ячеек, каждая из которых содержит одну операцию. Операции выполняются последовательно, начиная с первой, в том порядке, в котором они расположены в памяти. Выполнив последнюю из них, робот продолжает работу с первой. Робота можно остановить после любой операции. Использование робота экономически целесообразно, если он выполнит хотя бы K + 1 операцию.

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

Входные данные

В первой строке входного файла записано число K > 0 "— количество операций, которые можно записать в память робота.

Вторая строка состоит из N > K строчных латинских букв, обозначающих операции "— процесс сборки двигателя. Операции одного и того же типа обозначаются одной и той же буквой.

Выходные данные

Выходной файл должен содержать единственное целое число "— количество экономически целесообразных способов использования робота.

Примечание

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

Тесты из условия. Подзадача оценивается в 0 баллов.

N ≤ 100. Подзадача оценивается в 30 баллов.

N ≤ 2000. Подзадача оценивается в 30 баллов.

N ≤ 200 000. Подзадача оценивается в 40 баллов.

Примеры

Входные данные

2
zabacabab

Выходные данные

Входные данные

2
abc

Выходные данные