PDA

View Full Version : Нетривиальная задача

Boyov
Nov 6, 2003, 18:16
Дана строка типа:

AAAAAAAAAABABABCCD

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

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

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

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


Что скажете ;)?
Boyov.
W_z_rd
Nov 6, 2003, 18:51
A zazipovat` slabo ? ;) LZW compressiey :)
Zadacha na samom dele trivialnaya, esli znat` teoriyu po compressii.
DaNYer
Nov 6, 2003, 19:42
u vas kursovaya da?

p.s. Vas ne Armen sluchaino zvat'?
[ Xelgen ]
Nov 6, 2003, 20:01
Originally posted by DaNYer
u vas kursovaya da?

p.s. Vas ne Armen sluchaino zvat'?

Не, Карен, у нас олимпиада ;)
И зовут его Артемом :)
nm
Nov 6, 2003, 23:01
Originally posted by W_z_rd
A zazipovat` slabo ? ;) LZW compressiey :)
Zadacha na samom dele trivialnaya, esli znat` teoriyu po compressii.


lzw ne katit :) t.k. zdes' buffery mogut byt' wlozhennymi - wot eto primer .....
Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))


nu wo wsjakom sluchae ne katit w original'nom wariante, a tak -mozhno peredelat'
Boyov
Nov 6, 2003, 23:16
Originally posted by W_z_rd
A zazipovat` slabo ? ;) LZW compressiey :).

А смысл ??? :confused:

LZW это конечно хорошо (http://dogma.net/markn/articles/lzw/lzw.htm), а ещё существует туева хуча всяких других способов "compression"-а (md5 например http://www.faqs.org/rfcs/rfc1321.html) ,но я не думаю что эта задача вот так просто решится с помощю какого-то конкретного (известого) алгоритма. Correct me in case I'm wrong. Буду very very happy если я неправ :)


All the best
Boyov.
W_z_rd
Nov 7, 2003, 02:13
Originally posted by nm
lzw ne katit :) t.k. zdes' buffery mogut byt' wlozhennymi - wot eto primer .....
Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))


nu wo wsjakom sluchae ne katit w original'nom wariante, a tak -mozhno peredelat'
So vlozhennymi ciklami interesnee. Konechno, ya ne imel vvidu LZW v original`nom variante. Eto bila shutka s izryadnoy doley pravdi: mozhno ispolzovat` idei lezhashie v osnove LZW i podobnix kompressiy.



To Boyov:

MD5 eto hash-funkciya (message digest), a ne compressiya. No eto nevazhno. Ne, ti prav, gotovix sposobov netu, no sm. vishe.
greka
Nov 7, 2003, 08:07
Originally posted by Boyov
А смысл ??? :confused:

LZW это конечно хорошо (http://dogma.net/markn/articles/lzw/lzw.htm), а ещё существует туева хуча всяких других способов "compression"-а (md5 например http://www.faqs.org/rfcs/rfc1321.html)...

s kakix por MD5 stal "compression" -om ? :)
greka
Nov 7, 2003, 08:19
eta zadacha - PCX-compression.
t.e. graficheskij format PCX.

a smysl topika ya ne ponyal - algoritm napisat'?
[ Xelgen ]
Nov 7, 2003, 12:32
Originally posted by Greco El
a smysl topika ya ne ponyal - algoritm napisat'?

если не написать, то хотя бы описать ;)
Boyov
Nov 7, 2003, 13:21
Originally posted by Greco El
s kakix por MD5 stal "compression" -om ? :)

Народ ,пардон, но вы меня не так поняли :). It was a Joke ;). Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.

O смысле данного топика: мне нужен был ,скажем так, guidance, и я кстати его получил. Всем Спасибо.


Boyov
W_z_rd
Nov 7, 2003, 13:51
Originally posted by Boyov
Народ ,пардон, но вы меня не так поняли :). It was a Joke ;). Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.

O смысле данного топика: мне нужен был ,скажем так, guidance, и я кстати его получил. Всем Спасибо.


Boyov


Shyutnik ! ;)
Udachi !
Tumanyan
Nov 7, 2003, 15:18
Originally posted by Boyov
Дана строка типа:

AAAAAAAAAABABABCCD

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

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

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

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


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

A esli primenit' vesovuyu funkciyu? Tipa
F(X) = number of elements in compressed x. Sootvetstvenno, iskat' min x.

Naprimer F(CCD) = 4, sledovatel'no, CCD ne kompressiruem. F(AAAAAAAAAA) = 4 - kompressiruem.
nm
Nov 8, 2003, 18:02
Originally posted by Boyov
Народ ,пардон, но вы меня не так поняли :). It was a Joke ;). Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.

O смысле данного топика: мне нужен был ,скажем так, guidance, и я кстати его получил. Всем Спасибо.


Boyov

kstati naschet LZ - esli ja prawil'no ponimaju, tebe nuzhno na Ziv-e gonjat' LZ algoritm, rekursiwno ....
chtob i w Ziv-e najti powtorjajushiesja stroki ...
a washe eto wse ne effektiwno :)))

kstati kakie ogranichenija es't ? na ozu, wremja wypolnenija ?
Boyov
Nov 8, 2003, 19:00
Originally posted by nm
a washe eto wse ne effektiwno :)))
?

A chto sobstvenno effectivno ???

Originally posted by nm
kstati kakie ogranichenija es't ? na ozu, wremja wypolnenija ? [/B]

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 ;).
nm
Nov 8, 2003, 19:15
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
Nov 9, 2003, 11:55
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.
Nov 10, 2003, 17:42
{ 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
Nov 10, 2003, 17:44
.........skipped :)


fu :) polnyj perebor ;)
plz uvelichte limit do 1000 simwolow ;) i posmotrim kak ono budet rabotat' :)
strax.
Nov 10, 2003, 18:24
verjapes es im algoritmov areci!!! :)


http://www.gushar.com/folding.php?NEERCYESYESYESNEERCYESYESYES


;)
nm
Nov 10, 2003, 18:55
Originally posted by strax.
verjapes es im algoritmov areci!!! :)


http://www.gushar.com/folding.php?NEERCYESYESYESNEERCYESYESYES


;)

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.
Nov 12, 2003, 10:54
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
Nov 12, 2003, 18:40
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' :)