Защищенный пароль

[VladKB1]

Ребята большое спасибо за помощь! Я всё собрал в кучу и написал код, но в нём есть ошибки исправьте мне код пожалуйста!

var
 s: string;
 a: array [char] of longint;
 n,k,i,j,l,r,x,rec: longint;
begin
 assign(input,'input.txt');
 reset(input);
 assign(output,'output.txt');
 rewrite(output);

 readln(n,k);
 read(s);

 l:=1;
 for i:=1 to n do
 begin
  while a[s[r]] > k do
  begin
   dec(a[s[l]]);
   inc(l);
  end;

  if s[i] <> s[i+1] then
  begin
   r:=i;
   inc(a[s[i]]);
   inc(rec,r-l+1);
  end;
 end;
 writeln(rec);
end.

Тестировать можно здесь : http://dl.gsu.by/desk.asp\Гомельская обл. \2009\День 2\2 - "Защищенный пароль" 79474

[Аватар]

Сообщение от VladKB1

Задачу решаю на турбо паскале

А чего тестировать, если на турбо паскале это не пойдет? Одна строка s длиной 1000000 чего стоит

[Poma][a]

А почему речь о турбе?
Кстати.. Придумал вариант с памятью 36*10^6 и сложностью n log n
Храним инфу для каждого символа строки: сколько каких символ встретили до него включительно.. А потом бинарным поиском ищем.. Все

[VladKB1]

Сообщение от Аватар

А чего тестировать, если на турбо паскале это не пойдет? Одна строка s длиной 1000000 чего стоит

А отправляю на тест с помощью FreePascal

[Аватар]

мой код как раз для фри паскаля

[VladKB1]

Сообщение от Аватар

мой код как раз для фри паскаля

Помните я один раз вам (в другой теме) отвечал, что мне нельзя использовать то и то... Дак вот, у вас получиться исправить мой код не смотря на 1 000 000 символов?

[VladKB1]

Всем большое спасибо за помощь! Я решил задачу. Вот код:

var
 s: ansistring;
 a: array [char] of longint;
 n,k,i,j,l,r,x: longint;
 res:int64;
begin
 assign(input,'input.txt');
 reset(input);
 assign(output,'output.txt');
 rewrite(output);

 readln(n,k);
 read(s);

 l:=1;
 for i:=1 to n do
 begin
  r:=i;
  inc(a[s[i]]);
  while a[s[r]] > k do
  begin
   dec(a[s[l]]);
   inc(l);
  end;
  res:=res+(r-l+1);
  end;
 writeln(res);
end.

[Poma][a]

Супер! Спасибо!
Вся фишка в том, что сохраняя предыдущее значение l, мы можем в худшем случае еще раз пройтись по строке.. И будет 2N, а не N^2

Кстати, можно бахнуть {$H+} вместо ansistring

Только что с памятью? Строка всё равно нужна.. А это 10^6.. Правда ее можно молясь сократить, мол до l она нам нафиг не сдалась, но тогда другой момент : k громадно и символы различны(последнее для наглядности).. Тогда нужно удалять все ненужные, попутно смещая l..
Может позволит что-то убрать.. Но в лучшем(в идеальном, если я нигде не ошибся), мы уберем только половину.. А это 10^6 байт / 2 = 4мб