Нетривиальная задача

[Boyov]

Дана строка типа:

AAAAAAAAAABABABCCD

Нужно упаковать повторяющиеся подстроки так чтобы кол-во символов в результирующей строке было минимальным.

Т.е. если на входе : AAAAAAAAAABABABCCD
то на выходе должно быть : 9(A)3(AB)CCD

Обратите внимание на то, что если бы CCD превратилось в
2(C)D то результирующая строка стала бы длинее ( т.е. скобки и числа в результирующей строке тоже считаются символами ).

Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))


Что скажете ?
Boyov.

[nm]

Originally posted by Boyov
A chto sobstvenno effectivno ???



Vot original'naya zadacha
http://neerc.ifmo.ru/past/2002/problems/folding.htm

Tam ob ogranicheniyax vaabshe ne skazano, (eto otnositsya i ko vsem ostal'nim zadacham 2002 goda) ,navernoe nado polagat' chto ix net .

The input file contains a single line of characters from 'A' to 'Z' with at least 1 and at most 100 characters.

a eto - ne ogranichenie? )))))))
sobstwenno gorosja otsjuda i nado nachinat' ))
ty mozhesh sebe pozwolit' neodnokratno proskanirowat' fajl, kazhdyj raz szhimaja ocherednuju porciju dannyh



real'no - u tebja
k alfawitu A-Z dobawljajutsja simwoly а,б,в,ф,г,е... и т.д., kotorye fakticheski predstawljajut iz sebja -
а === 10(AY)
б === 2(EPRST)

i tak dalee i na kazhdom prohode tebe nuzhno szhimat' stroku sostojashuju iz
A-Zа-я

[Boyov]

Originally posted by nm
The input file contains a single line of characters from 'A' to 'Z' with at least 1 and at most 100 characters.

a eto - ne ogranichenie? )))))))
sobstwenno gorosja otsjuda i nado nachinat' ))
ty mozhesh sebe pozwolit' neodnokratno proskanirowat' fajl, kazhdyj raz szhimaja ocherednuju porciju dannyh



real'no - u tebja
k alfawitu A-Z dobawljajutsja simwoly а,б,в,ф,г,е... и т.д., kotorye fakticheski predstawljajut iz sebja -
а === 10(AY)
б === 2(EPRST)

i tak dalee i na kazhdom prohode tebe nuzhno szhimat' stroku sostojashuju iz
A-Zа-я

Thanks

[strax.]

PHP Code:

{ SOLUTION for "Folding" problem for NEERC'2002 }
{ (C) Roman Elizarov, 2002 }

{$A+,B-,D+,E+,F-,G-,I+,L+,N+,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M 65520,0,655360}
program FOLDING_SOLUTION;

const
  MAX_N = 100;

type
  TArray = array[1..MAX_N, 1..MAX_N] of integer;
  PArray = ^TArray;

var
  s: string;
  n, i, j, k, l, lr, x, p, q, ofs: integer;
  a, op: PArray;
  min, bestop, tmp: integer;
  c: char;
  ok: boolean;

procedure recwrite(i, j: integer);
var
  bestop, l, x: integer;
begin
  bestop := op^[i, j];
  if bestop = 0 then begin
    for l := i to j do
      write(s[l]);
  end else if bestop > 0 then begin
    recwrite(i, bestop);
    recwrite(bestop + 1, j);
  end else begin
    l := -bestop;
    x := (j - i + 1) div l;
    write(x, '(');
    recwrite(i, i + l - 1);
    write(')');
  end;
end;

begin
  { Allocate memory }
  new(a);
  new(op);
  { Open input/output }
  assign(input, 'folding.in'); reset(input);
  assign(output, 'folding.out'); rewrite(output);
  { Read }
  readln(s);
  n := length(s);
  { Solve }
  for i := 1 to n do begin
    a^[i, i] := 1;
    op^[i, i] := 0;
  end;
  for l := 2 to n do { lenght of subsequences to optimize }
    for i := 1 to n - l + 1 do begin { from s[i] }
      j := i + l - 1; { to s[j] }
      min := l;
      bestop := 0;
      { Try concatenation }
      for k := i to j - 1 do begin
        tmp := a^[i, k] + a^[k + 1, j];
        if tmp < min then begin
          min := tmp;
          bestop := k;
        end;
      end;
      { Try repeating }
      for lr := 1 to l div 2 do { length of repeating seq }
        if l mod lr = 0 then begin
          x := l div lr; { repeat count }
          ok := true;
          for p := 1 to lr do begin
            ofs := i + p - 1;
            c := s[ofs];
            for q := 2 to x do begin
              inc(ofs, lr);
              if s[ofs] <> c then begin
                ok := false;
                break;
              end;
            end;
            if not ok then
              break;
          end;
          if ok then begin
            tmp := 3 + a^[i, i + lr - 1];
            if x >= 10 then
              inc(tmp);
            if x >= 100 then
              inc(tmp);
            if tmp < min then begin
              min := tmp;
              bestop := -lr;
            end;
          end;
        end;
      { assign result }
      a^[i, j] := min;
      op^[i, j] := bestop;
    end;
  { Write }
  recwrite(1, n);
  writeln;
end. 


im mot pascal chka, teseq dzez mot ashxatum a?

[nm]

.........skipped


fu polnyj perebor
plz uvelichte limit do 1000 simwolow i posmotrim kak ono budet rabotat'

[strax.]

verjapes es im algoritmov areci!!!


http://www.gushar.com/folding.php?NE...NEERCYESYESYES

[nm]

Originally posted by strax.
verjapes es im algoritmov areci!!! :)


http://www.gushar.com/folding.php?NE...NEERCYESYESYES


;)

imho neprawil'no rabotaet :) na wot takoj stroke :)

wot tebe raz stroka
NEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCY LKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYL KACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKABBNE ERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLK ACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKA CYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKABB

i rezul'tat -
2(2(NEER8(CYLKA)NEER5(CYLKA))BB)

dobavim s konca k uzhe sushestwujushemu BB - ABBABBABBABBA i tak mnogo raz -wobshem wot zdes' rezul'tirujushaja stroka


NEERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCY LKACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYL KACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKABBNE ERCYLKACYLKACYLKACYLKACYLKACYLKACYLKACYLKANEERCYLK ACYLKACYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKA CYLKACYLKACYLKANEERCYLKACYLKACYLKACYLKACYLKABBABBA BBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABBABB ABBABBABBABBABBABBABBABBABBABBABBA

poluchaetsja wot chto :)
2(NEER8(CYLKA)NEER5(CYLKA))BB2(NEER8(CYLKA)NEER5(C YLKA))30(BBA)

chto garantirowanno neprawilono :)
dolzhno pouchitsja

2(2(NEER8(CYLKA)NEER5(CYLKA))BB)A29(BBA)


za praiwll'nost' chisla 29 -ne ruchajus'

wsjacheskih bug-ow :))))

[strax.]

nm
ha , &isht es asum, sxal ka mech@, bayc im grac principov chem karogh uxxel.

chnayac vor im graci aravelutyun@ nranum a vor input text-i chapi vra limit chka drac.

[nm]

Originally posted by strax.
nm
ha , &isht es asum, sxal ka mech@, bayc im grac principov chem karogh uxxel.

chnayac vor im graci aravelutyun@ nranum a vor input text-i chapi vra limit chka drac.

moje delo - skazat' :)