images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
23/11/2024 15:18:18

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

1236. Сортировка

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Начинающий программист Дон Тунк хочет определить количество операций обмена и количество проходов в известном алгоритме при сортировке некоторой последовательности целых чисел.
Для этого он написал следующую программу на языке Паскаль:
program BubbleSort;
var
  Arr:Array[1..100000] of Integer;
  n, i, Temp, Count, NLoop : Integer; 
  Flag : Boolean; 
begin
  read(n);
  for i:=1 to n do
    read(Arr[i]);
  Count := 0;
  NLoop := 0;
  repeat
    Flag := False;
    for i := 1 to n - 1 do
      if Arr [i] > Arr [i + 1] then
      begin 
        Temp := Arr [i]; 
        Arr [i] := Arr [i + 1];
        Arr [i + 1] := Temp; 
        Flag := True;
        inc(Count);
      end;
    inc(NLoop);
  until not Flag;
  writeln(Count,' ',NLoop);
end;
Есть перевод этой программы на язык Си:
#include <stdio.h>
int Arr[100000];
int n, i, Temp, Count=0, NLoop=0, Flag;
int main()
{ scanf("%d",&n);
  for(i=0; i<n; ++i)
    scanf("%d",&Arr[i]);
  do
  { Flag=0;
    for(i=0; i<n-1; ++i)
      if(Arr[i]>Arr[i+1])
      { Temp=Arr[i];
        Arr[i]=Arr[i+1];
        Arr[i+1]=Temp;
        Flag=1;
        ++Count;
      }
    ++NLoop;
  } while(Flag);
  printf("%d %dn",Count,NLoop);
  return 0;
}
К сожалению, время работы этой программы оказалось очень большим, поэтому Дон обратился за помощью к вам, чтобы вовремя завершить свое исследование.
Напишите программу, определяющую для заданной последовательности количество обменов и количество проходов, необходимых для её сортировки вышеуказанным алгоритмом.
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^5`) – количество элементов в последовательности. Вторая строка ввода содержит `N` целых чисел в диапазоне от `1` до `10^5` – сортируемую последовательность.
Вывести два целых числа – количество обменов и количество проходов, выполненных при сортировке заданной последовательности указанным алгоритмом.

Пример ввода

4
10 1 2 1

Пример вывода

4 3
loading