Портал обучения информатике. Подготовка к ЕГЭ, ОГЭ, олимпиадам

Беси начал изучать алгоритмы с различных WEB-ресурсов.

Её любимый алгоритм - пузырьковая сортировка. Ниже приведена его реализация в коровьем коде, которая сортирует массив \(A\) длины \(N\).

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Команда "moo" выводит слово "moo".

По данному массиву предскажите, сколько раз будет напечатано слово "moo" этим кодом Беси.

ФОРМАТ ВВОДА (файл sort.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100,000\)). Следующие \(N\) строк описывают \(A[0] \ldots A[N-1]\), каждая - целое число в интервале \(0 \ldots 10^9\). Не гарантируется, что все элементы различны.

ФОРМАТ ВЫВОДА (файл sort.out):

Выведите, сколько раз будет напечатано слово "moo"

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

—Войти и решать

Out of Sorts#90028

Беси изучает алгоритмы на web-ресурсах.

Её любимый алгоритм называется "пузырьковая сортировка". Ниже приведена начальная его версия в коровьем коде для сортировки массива \(A\) из \(N\) элементов.

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
         sorted = false

Команда "moo" выводит слово "moo".

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

sorted = false
while (not sorted):
   sorted = true
   moo
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = N-2 downto 0:
      if A[i+1] < A[i]:
         swap A[i], A[i+1]
   for i = 0 to N-2:
      if A[i+1] < A[i]:
         sorted = false

По заданному входному массиву предскажите, сколько раз слово "moo" будет напечатано этим модифицированным кодом.

ФОРМАТ ВВОДА (файл sort.in):

Первая строка ввода содержит \(N\) (\(1 \leq N \leq 100,000\)). Следующие \(N\) строк описывают \(A[0] \ldots A[N-1]\). Каждый элемент - целое число в интервале \(0 \ldots 10^9\). Не гарантируется, что все элементы различны.

ФОРМАТ ВЫВОДА (файл sort.out):

Выведите сколько раз meltn напечатано слово "moo".

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

—Войти и решать

Военная сортировка#54665

Фирма Macrohard получила заказ от армии одной страны на реализацию комплекса программного обеспечения для нового суперсекретного радара. Одной из наиболее важных подпрограмм в разрабатываемом комплексе является процедура сортировки.

Однако в отличие от обычной сортировки, эта процедура должна сортировать не произвольный массив чисел, который передается ей на вход, а специальный заранее заданный массив из N чисел, в котором записана некоторая фиксированная перестановка чисел от 1 до N, и кроме того, ни одно число в нем изначально не находится на своем месте (то есть на позиции с номером i изначально не находится число i).

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

Например, если массив из 6 элементов в некоторый момент имеет вид <2, 1, 3, 6, 4, 5>, то можно поменять местами 1 и 2, 6 и 4 или 4 и 5, а менять местами 1 и 3 или 3 и 6 нельзя, поскольку число 3 находится на своем месте (на позиции с номером 3).

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

Подсказка

Найти такую последовательность обменов всегда возможно.

Входные данные
В первой строке вводится целое число N - размер входного массива (1 <= N <= 100). Вторая строка содержит N целых чисел - исходную перестановку чисел от 1 до N в массиве. Изначально ни одно число не стоит на своем месте.

Выходные данные
Выведите K строк, где K - количество обменов в Вашей сортировке. На каждой строке выведите по два числа x_i и y_i, разделенных пробелом - позиции в массиве, числа на которых следует поменять местами на i-ом обмене. Помните, что должно выполняться условие |x_i - y_i| = 1 и что нельзя перемещать число, которое уже стоит на своем месте.

Пояснение к примеру
В приведенном примере массив последовательно имеет следующий вид:
исходный вид массива
2 3 1 6 4 5
поменяли местами числа на 2 и 3 позициях
2 1 3 6 4 5
поменяли местами числа на 1 и 2 позициях
1 2 3 6 4 5
поменяли местами числа на 4 и 5 позициях
1 2 3 4 6 5
поменяли местами числа на 5 и 6 позициях
1 2 3 4 5 6

Сортировка "пузырьком"Сортировка выбором (максимума)

✓ 1✗ 2—Войти и решать

Урок физкультуры#50574

На уроке физкультуры тренер Андрей Сергеевич выстраивает учеников в одну шеренгу. В шеренге сначала идут мальчики, а потом девочки. При этом мальчики в шеренге стоят по убыванию роста, аналогично девочки тоже стоят по убыванию роста. Таким образом, следом за самым низким мальчиком стоит самая высокая девочка.

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

Формат входных данных
Первая строка содержит целое число \(n\) — число учеников в классе (\(2 \le n \le 50\)). Следующие \(n\) строк содержат по два целых числа каждая: \(a_i\) и \(h_i\) — пол и рост в сантиметрах \(i\)-го ученика (\(a_i\) равно 0 или 1, \(100 \le h_i \le 200\)). Значение \(a_i = 0\) означает, что \(i\)-й ученик — мальчик, а значение \(a_i = 1\) означает, что \(i\)-й ученик — девочка.

Формат выходных данных
Выведите одно число — максимальное различие в росте стоящих рядом учеников после того, как они выстроятся в шеренгу на уроке физкультуры.

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

✓ 11✗ 45700средняяВойти и решать

"Сортировка" с конфеткой#38576

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

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

Требуется провести сортировку «с конфеткой» данного массива и выдать результат сортировки.

Входные данные
Сначала вводится число N — количество чисел в массиве, затем N чисел — элементы массива. Далее задается число M — количество пар чисел, за которые дают конфетку, а затем M пар чисел. Если в списке есть пара (i,j), то и за пару (j,i) также дают конфетку.

1 ≤ N ≤ 5000, 0 ≤ M ≤ 10000.

Выходные данные
Требуется вывести массив после сортировки.

Примеры

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

Задачи на моделирование Сортировка "пузырьком"

✓ 36✗ 5051 100средняяВойти и решать

Ожерелье#34881

В витрине ювелирного магазина стоит манекен, на шею которого надето ожерелье. Оно состоит из N колечек, нанизанных на замкнутую нить. Все колечки имеют разные размеры. В зависимости от размера колечки пронумерованы числами от 1 до N, начиная с самого маленького и до самого большого. Колечки можно передвигать вдоль нити и протаскивать одно через другое, но только в том случае, если номера этих колечек отличаются более чем на единицу.

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

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

Входные данные
Первая строка входных данных содержит число N (2 ≤ N ≤ 50).

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

Выходные данные
Ваша программа должна вывести описание процесса упорядочения.

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

Количество выводимых строк не должно превышать 50000.

Если требуемого упорядочения колечек достичь не удается, программа должна вывести одно число –1

Ввод	Вывод
4 3 1 2 4	4 2 4 1 0

Задачи на моделирование Сортировка "пузырьком"

✓ 28✗ 90800средняяВойти и решать

Пузырьковая сортировка: количество обменов#29475

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

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

На первой строке дано число N (\(1 <= N <= 1000\)) – количество элементов в массиве. На второй строке – сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю 10⁹.

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

Выведите одно число – количество обменов пузырьковой сортировки.

Примеры

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

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

✓ 2 539✗ 2 085200лёгкаяВойти и решать