Дистанционная подготовка: Прошу помочь с программой.
Прошу помочь с программой.
от Никита Пушкин - Суббота 27 Сентябрь 2014, 16:09
1418. Разные
  Написал программу, которая вроде бы должна работать. Алгоритм таков: считываем по очереди числа и вставляем их на ту позицию, где они должны стоять на момент их считывания, то есть сортируем массив методом вставки. А затем просто пробегаем массив по порядку и смотрим, сколько различных чисел мы можем найти.

Но есть две проблемы: во-первых, программа почему-то прошла не все тесты, а во-вторых, она некоторые тесты просто-напросто заваливает по времени. Может кто-нибудь сказать, что у меня не так?

Вот текст программы:
i,j,l-счетчики; k-число, которое мы считали и собираемся вставить в массив; back,back2-переменные, используемые для сдвига массива вправо при вставке числа; num-количество различных чисел.

program a1418;
var n,i,j,k,l,back,back2,num:longint;
a:array[1..100000] of longint;
bo:boolean;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
readln(n);
read(a[1]);
for i:=2 to n do
begin
  read(k);
  j:=1;
  bo:=false;
  while (j<i) and (bo=false) do //определяем куда вставить число
  begin               
    if k<=a[j] then
    begin
      bo:=true;
      back:=a[j];
      for l:=j+1 to i do //смещение чисел вправо
      begin           
        back2:=a[l];
        a[l]:=back;
        back:=back2;
      end;
      a[j]:=k;
    end;
    inc(j);
    if j=i then a[j]:=k; //если число самое большое, то вставляем его в конец
  end;           
num:=1;
back:=a[1];  //взял back, т.к он больше не нужен, а новую переменную вводить лень
for i:=2 to n do 
if a[i]<>back then
  begin           
  inc(num);
  back:=a[i];
  end;
write(num);
end.
Re: Прошу помочь с программой.
от Peter Cherepanov - Суббота 27 Сентябрь 2014, 20:15
  Квадратичная сортировка при таких ограничениях не подходит. Дальше не смотрел.
Re: Прошу помочь с программой.
от Никита Пушкин - Воскресенье 28 Сентябрь 2014, 00:10
  Мда, почему-то мне этот метод сортировки очень понравился, но я забыл, что это квадратичная сортировка.
Re: Прошу помочь с программой.
от Владислав Давыдов - Понедельник 14 Сентябрь 2015, 18:11
  Кто знает что в 3-ем тесте?
Программу строил на быстрой сортировке