IOM 2018, Блиц, английски — Задача 42

OLYMPIAD OF METROPOLISES. Moscow, September 3 · 3 септември 2018 г.

Условие

Consider the following sequence: 5, 8, 4, 3, 8, 6, 2. The sequence is going to be sorted in ascending order, and bubble sort algorithm that compares two adjacent numbers from right to left is going to be used. How many swaps are performed during the algorithm? During the $k$-th round of data procession, assuming there are $n$ elements, first we compare the $(n-1)$-th and $n$-th element and swap them if necessary, then $(n-2)$-th and $(n-1)$-th, etc., and at the end of the $k$-th round we compare and swap the $k$-th and the $(k+1)$-th element.

Отговори

Решение

---

Оригинал в Архива: blitz.pdf · официални решения: blitz-answers.pdf