e-olymp
Məsələlər

Сортировка "пузырьком"

Сортировка "пузырьком"

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Алгоритм считается учебным и практически не применяется вне учебной литературы, вместо него на практике применяется сортировка вставками. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

ВикипедиЯ

Пузырьковая сортировка является очень простым алгоритмом и его временная сложность составляет O(n2). Каждый раз, проходя по всему массиву, сначала мы сравниваем соседние элементы и если есть необходимость меняем их местами. Этот процесс повторяется, пока при очередном проходе сделана хотя бы одна замена. Предположим, что после T проходов массив уже отсортирован в порядке возрастания, тогда мы говорим, что T является количеством этапов соритовки для заданного массива. Ниже приведен пример. Возьмем за исходный начальный массив "5 14 2 8" а затем используя описанный алгоритм пузырьковой сортировки проведем его сортировку следующим образом:

Первый проход:

( 5 1 4 2 8 ) -> ( 1 5 4 2 8 ), сравнили первых два элемента и поменяли их местами.
( 1 5 4 2 8 ) -> ( 1 4 5 2 8 ), поменяли местами 5 > 4
( 1 4 5 2 8 ) -> ( 1 4 2 5 8 ), поменяли местами 5 > 2
( 1 4 2 5 8 ) -> ( 1 4 2 5 8 ), так как два последних элемента упорядочены (8 > 5), алгоритм не меняет их местами.

Второй проход:

( 1 4 2 5 8 ) -> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) -> ( 1 2 4 5 8 ), поменяли местами 4 > 2
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) -> ( 1 2 4 5 8 )

После T = 2 проходов массив уже отсортирован, поэтому мы говорим, что количество проходов алгорима сортировки пузырьком для заданного массива равно 2.

Петя изучил алгоритм сортировки пузырьком в классе и его учитель задает задания, связанные с ним, как домашнее задание. Учитель предоставил Пете уже осортированный массив A состоящий из N различных целых чисел и утверждает, что он получил его после K проходов алгоримом сортировки пузырьком. Задание: какое количество исходных первоначальных массивов A может существовать, чтобы в итоге получить заданный массив после K проходов алгоритма сортировки пузырьком? Результат может быть очень большим, поэтому его необходимо вывести по модулю 20100713.

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

Входные данные состоят из нескольких тестов.

В первой строке задано натуральное число T (T100000), указывающее количество тестовых случаев.

Следующие T строк содержат тестовые данные. В каждой строке находится два целых числа N и K (1N1000000, 0KN - 1) где N указывает на размер массива, а K - количество этапов сортировки алгоритмом пузырька.

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

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

Примечание

Предположим, что задан массив {a, b, c} (a < b < c). Существует 6 различных вариантов исходного массива:

{a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a},

а исходный мы можем получить по разному:

{a, b, c}: не сортируя, так как массив уже отсортирован.

{a, c, b}, {b, a, c}, {c, a, b}: за один проход алгоритма сортировки пузырьком.

{b, c, a}, {c, b, a}: за 2 прохода алгоритма сортировки пузырьком.

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
3
3 0
3 1
3 2
Çıxış verilənləri
1
3
2