Ima li koga da je rešio ovaj zadatak u paskalu?
z-which
Hm.. tesko xD , ja sam pokusao, ali bez uspeha, na zadnja 3 primera TLE.
Evo koda :
I neznam kako moze brze od ovoga :)
Evo koda :
const
mm = 3999971;
var
ind : array[0..mm] of longint;
b : array[0..205] of longint;
n, m, i, x, d, br : longint;
c : char;
begin
readln(n, m);
i := 0;
repeat
read(c); i := i + 1; d := 1; br := 0;
while (c <> ' ') and not eoln do begin
br := br + ord(c) * d; d := d + 1;
if br > mm then br := br mod mm;
read(c);
end;
if eoln then br := (br + ord(c) * d) mod mm;
ind[br] := i;
until i = n;
readln; i := 0;
repeat
read(c); i := i + 1; br := 0; d := 1;
while (c <> ' ') and not eoln do begin
br := br + ord(c) * d; d := d + 1;
if br > mm then br := br mod mm;
read(c);
end;
if eoln then br := (br + ord(c) * d) mod mm;
b[ ind[br] ] := b[ ind[br] ] + 1;
until i = m;
for i := 1 to n do writeln(b[i]);
end.
I neznam kako moze brze od ovoga :)
nisam ga rjesio u pascalu ali imas 2 opcije:
1. sortirati pocetne rijeci, pa za svaku rijec iz texta binarnim pretrazivanjem ju naci i povecati njen brojac. slozenost O( M*L* lg N + N*L*lg N )
2. hashirati rijeci i sortirati hasheve pa po istom postupku nastavit kao u prvom koraku, poslje sortiranja. slozenost O( M lg N + N lg N )
1. sortirati pocetne rijeci, pa za svaku rijec iz texta binarnim pretrazivanjem ju naci i povecati njen brojac. slozenost O( M*L* lg N + N*L*lg N )
2. hashirati rijeci i sortirati hasheve pa po istom postupku nastavit kao u prvom koraku, poslje sortiranja. slozenost O( M lg N + N lg N )
Uradio sa program koristeći 1. ideju. I na svom računaru na svim test primerima prolazi za manje od 0.1 sec. ( za primer od 200 reči po 500 karaktera i 2000 reči teksta). Nakon posta na zadnja tri testa je TLE, a na ostalim WA. Nisam siguran da uopšte dobro učitavam tekstualne podatke. Zato me interesuje ko je uradio ovaj zadatak u paskalu i, ako želi, pomogne.
@Dimke
Na prvi pogled, tvoj kod je OK, a i ovo što se tiče brzine. (tvoj kod je barem duplo brzi od mog koda sa sortiranjem, oko 0.11 sec.). Slični kodovi u C-u prolaze. Zar je input u paskalu toliko sporiji od C-ovog?
@Dimke
Na prvi pogled, tvoj kod je OK, a i ovo što se tiče brzine. (tvoj kod je barem duplo brzi od mog koda sa sortiranjem, oko 0.11 sec.). Slični kodovi u C-u prolaze. Zar je input u paskalu toliko sporiji od C-ovog?
Sve sto ja radim je : Ucitavam rec po rec iz text-a (prva grupa reci), Hash-ujem je i markiram ih (pamtim njihov Index u nizu Ind). E sad kad uchitavam drugu grupu reci, citam jednu po jednu i Hash-ujem ih i u O(1) povecam njeno ponavljanje za 1 i tako do kraja i na kraju samo ispisem kolko se koja rec puta ponavlja ... Nznm zasto nije dovoljno brzo :S
@halil
Izgleda da jeste...
@halil
Izgleda da jeste...
C dosta brze cita karaktere nego Pascal, dok je Pascal mnogo brzi kod realnih brojeva
program test;
var
n,m: longint;
c: char;
begin
readln(n,m);
while (not eoln) do read(c);
readln;
while (not eoln) and (not eof) do read(c);
end.Za ovaj program koji samo učitava podatke za z-wihich dobija se T.L.E, za zadnja tri testa. U čemu je fazon?
@Dimke:
I tvoj i moj program ubrzam za preko 50% na neki 'imbecilan' način, ali onda za zadnja četiri testa dobijam WA, dok na nekoliko mojih test-primera (maksimalnih) daju identične rezultate. Baš bi želeo da vidim test-primere sa sajta (da nisu unicode, mislim da nisu).
Probao sam i sa promenljivom tipa AnsiString. Tada za zadnja četiri primera dobijam 'Invalid memory reference (memory limit exceeded)' ili 'Exit code not zero'. Prvih 11 je OK.
P.S.
Kod mene je Comipler Version 2.2.2.
P.S.
Kod mene je Comipler Version 2.2.2.
@ Dimke, @ picsel (@paskalovci)
Prošao.
Iskoristio sam Dimčetov kod i neki nestandardan način učitivanje ( imbecilna ideja, gde mi detalji i dalje nisu jasni ). Ako se Dimke slaže da kod postujem ovde (ipak je, u suštini, to njegov kod). Dimke ?
Prošao.
Iskoristio sam Dimčetov kod i neki nestandardan način učitivanje ( imbecilna ideja, gde mi detalji i dalje nisu jasni ). Ako se Dimke slaže da kod postujem ovde (ipak je, u suštini, to njegov kod). Dimke ?
E, evo me :), postuj slobodno :D
@ halil
I ja sam pokusao nesto sa AnsiString-om, ali sve sto sam dobio je TLE na zadnja 3 i 12. primer prolazi brze za 0.02 sec xD
@ halil
I ja sam pokusao nesto sa AnsiString-om, ali sve sto sam dobio je TLE na zadnja 3 i 12. primer prolazi brze za 0.02 sec xD
program z_which;
const
mm = 999979;
MAXS = 5200000;
var
ind : array[0..mm] of longint;
b : array[0..215] of longint;
n, m, i, d, br: longint;
z: array [0..MAXS] of char;
p: pchar;
begin
readln(n, m);
// fillchar(b, sizeof(b), #0);
// fillchar(z[0], MAXS, #0);
readln(z);
p:= @z[0];
i := 0;
repeat
i := i + 1; d := 1; br := 0;
while (p^ <= ' ') and (p^ <> #0) do p:= p+1;
while (p^ > ' ') do begin
br := br + ord(p^) * d; d := d + 1;
while (br >= mm) do br := br - mm;
p:= p+1;
end;
if (p^ in [#$00, #$0D, #$0A, #$1A]) then p^:= #$1A else p:= p+1;
ind[br] := i;
until (p^ = #$1A);
// fillchar(z[0], MAXS, #0);
readln(z);
p:= @z[0];
i := 0;
repeat
i := i + 1; br := 0; d := 1;
while (p^ <= ' ') and (p^ <> #0) do p:= p+1;
while (p^ > ' ') do begin
br := br + ord(p^) * d; d := d + 1;
while (br >= mm) do br := br - mm;
p:= p + 1;
end;
if (p^ in [#$00, #$0D, #$0A, #$1A]) then p^:= #$1A else p:= p+1;
b[ ind[br] ]:= b[ ind[br] ] + 1;
until (p^ = #$1A);
for i := 1 to n do writeln(b[i]);
end.Kada sam postavi MAXS=1200000, onda na zadnja 4 testa dobija se 'Exit code not zero'. Zašto je MAXS=5200000? Nemam pojma. Na mom računaru radilo je i sa MAXS=1000003. Možda u test-primerima ima previše delimitera reči.
Ali samo učitavanje podataka je drastično brze!
Ali samo učitavanje podataka je drastično brze!
const
mm = 1999969;
var
ind : array[0..mm] of longint;
b : array[0..205] of longint;
n, m, i, j, d, br : longint;
z : array[1..5200000] of char;
begin
readln(n, m);
readln(z);
j := 0;
for i := 1 to n do begin
d := 1; br := 0; j := j + 1;;
while (z[j] <> ' ') and (z[j] <> #0) do begin
br := br + ord(z[j]) * d; d := d + 1; j := j + 1;
if br >= mm then br := br mod mm;
end;
ind[br] := i;
end;
readln(z);
j := 0;
for i := 1 to m do begin
d := 1; br := 0; j := j + 1;
while (z[j] <> ' ') and (z[j] <> #0) do begin
br := br + ord(z[j]) * d; d := d + 1; j := j + 1;
if br >= mm then br := br mod mm;
end;
b[ ind[br] ] := b[ ind[br] ] + 1;
end;
for i := 1 to n do writeln(b[i]);
end.
Evo moze i ovako ;), izgleda da dosta brze ucitava niz Char-ova, nego AnsiString ili Char po Char :)
Ovo mi se više sviđa. Ja se zaglupio sa pokazivačima.
Inače, ovako nešto ne bi prošlo na nekim implemetacija paskala. Ako se ne varam, nije po standardu, učitavanje niza iz tekstualnog fajla ( file of ... je već druga priča).
Mislim da bi za ovaj zadatak vreme trebalo povećati, barem da prođe onaj trivijalan kod sa učitavanjem. I dalje, to povećanje vremena, neće uticati na suštinu zadatka.
Nadam se admin ovo 'sluša'.
Inače, ovako nešto ne bi prošlo na nekim implemetacija paskala. Ako se ne varam, nije po standardu, učitavanje niza iz tekstualnog fajla ( file of ... je već druga priča).
Mislim da bi za ovaj zadatak vreme trebalo povećati, barem da prođe onaj trivijalan kod sa učitavanjem. I dalje, to povećanje vremena, neće uticati na suštinu zadatka.
Nadam se admin ovo 'sluša'.
Slazem se sto se tice povecavanja vremena :) , a admin 'ne slusa' vec jedno mesec dana xD
I ja se slazem da ovde treba povecati vreme zbog onih koji rade u pascalu, kao sto je npr. u zadatku 'golf' povecano vreme na 2s da bi u C-u proslo resenje sa racunanjem kvadrata, koje radi za vise od 1s...