IOM 2018, Блиц, руски — Задача 42

ОЛИМПИАДА МЕГАПОЛИСОВ. Москва, 3 сентября 2018

Условие

Рассмотрим следующий массив: 5, 8, 4, 3, 8, 6, 2. Его предполагается сортировать пузырьком справа налево. Сколько обменов выполнит этот алгоритм? На $k$-м проходе сначала будут сравниваться $(n-1)$-й и $n$-й элементы, потом $(n-2)$-й и $(n-1)$-th, и т.д, последними будут сравниваться $k$-й и $(k+1)$-й элементы.

Решение

---

Оригинал в Архива: blitz-ru.pdf