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

[Smogg]

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

a y a y ay ya ay

исходно: a1y1a2y2. Условие - не длиннее 4, не больше 1 повторений.

Ответ: 7

Варианты:
a1 y1
a1 a2
y1 a2
y1 y2
a1y1 a2
a1y1 a2y2
a1y1 y2
y1 a2y2
...

уже восемь) подстроки паролей не перекрываются

[Poma][a]

Нее..
y1=y2 a1=a2
Поэтому повторения имеются..

И да.. Мои мысли - бред.. Ибо там прямое противоречие с условием..

[Smogg]

понял)
так должно быть, последовательно:
a1
a1y1
y1
y1a2
a2
a2y2
y2

[Smogg]

тогда алгоритм в лоб такой:

заводим счетчик уникальных паролей
заводим массив количеством 10+26 (алфавит плюс цифры), являющийся счетчиком уникальных символов, где каждый элемент не больше К
начинаем перебор строки от первой буквы до N
	обнуляем массив
	начинаем перебор конечной буквы подстроки пароля (от текущей начальной до последней, т.е. до N)
		если соответствующий элемент массива не больше K, то
			инкрементируем элемент массива 
			инкрементируем счетчик уникальных паролей
		иначе 
			выходим из цикла перебора конечноого символа и переходим к следующему начальному символу подстроки пароля
	следующая итерация выбора последнего символа подстроки пароля
следующая итерация выбора начального символа подстроки пароля

ага?

Тогда для N = 10^6 и K =1 получается максимальное количество итераций (10+26)*10^6. Это много или мало?

[Poma][a]

Алгоритм не читал.. Кол-во итераций : в секунды должны уложиться

[Jurijus123]

Перестановок по формуле:
X! X- количество длины символов. Если количество без
вореаций без повторовеней то последущих символов будет на одну меньше.
Формула:
X*(X+1)/2 x-вореции
А с повторами будет формула:
X^Y x-вореаций y - количиство длины символов

[Smogg]

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

Перестановок по формуле:
X! X- количество длины символов.

Здесь не про перестановки)
пусть строка такая: 0123401234. Т.е. десять символов. С условием - не больше двух повторений.
Количество уникальных паролей для нее - 10+9+8+7+6+5+4+3+2+1 == 11*5.

[Аватар]

Эта задачка есть на acmp (649). И решение за 0.2-0.3 секунды и несколько мегабайт памяти достаточно простое. Но там есть быстрые решения в 60 килобайт и меньше. Не доходит какой алгоритм можно применить для этого

[Poma][a]

А если так :

function f(s : string; k, p : Integer) : Integer;
begin
	if (s = 'ayay') then
		case p of 
		2 : f := 1;
		3 : f := 2;
		4 : f := 3
		end
	else
		case p of
		2 : f := 1;
		3 : f := 1;
		4 : f := 3;
		5 : f := 3;
		6 : f := 3
		end
end;

var
	s : string;
	n, k, i, j : Integer;
	a : array [1..10] of Integer;

begin
	ReadLn(n, k);
	ReadLn(s);

	a[1] := 1;
	for i := 2 to n do begin
		j := f(s, k, i);
		a[i] := i-j + 1 + a[i-1];	
	end;
	WriteLn(a[n])
end.

?
Только нужно научиться очень быстро вычислять j.. Как это сделать - я пока без понятия

[Аватар]

Набросал под турбо-паскаль 0,248с. и 5.8Мб. Но компиль там делфи и указатель 4 байта, для турбо 2 будет и памяти меньше запросто на пару Мб получится. Турбо по идее и не сможет с такой памятью работать. Если делать под делфи от списка можно избавиться и на строку или массив перейти, но все равно ~ 1Мб. Как 60Кб?

type PRecord = ^TRecord;
     TRecord = record
       n: PRecord;
       b: Byte;
     end;
var i,j: Longint;
    c: Char;
    m,n,k: Int64;
    p,f,l,g: PRecord;
    b: Byte;
    a: array[0..255] of Longint;

begin
  Assign(input,'input.txt');
  Reset(input);
  Readln(n,k);
  m:=((2*n-k+1)*k) div 2;
  for i:=0 to 255 do a[i]:=0;
  f:=nil; j:=0;
  for i:=1 to n do begin
    Read(c);
    GetMem(p,SizeOf(TRecord));
    p^.b:=Ord(c);
    p^.n:=nil;
    if f=nil then f:=p else l^.n:=p;
    l:=p;
    Inc(a[p^.b]);
    Inc(j);
    if a[p^.b]>k then begin
      repeat
        b:=f^.b;
        g:=f^.n;
        FreeMem(f,SizeOf(TRecord));
        f:=g;
        Dec(a[b]);
        Dec(j);
        if j>k then begin
          Inc(m,j-k-1);
          if b=p^.b then Inc(m);
        end;
      until b=p^.b;
    end
    else if j>k then Inc(m);
  end;
  Dec(j);
  if j>k then Inc(m,((j-k+1)*(j-k)) div 2);
  while f<>nil do begin
    g:=f^.n;
    FreeMem(f,SizeOf(TRecord));
    f:=g;
  end;
  Assign(output, 'output.txt');
  Rewrite(output);
  Write(m);
end.