Беси изучает алгоритмы на 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".
Ваш ответ: