Обсуждение @ 1253. Некрологи @ Timus Online Judge

uuuuuuu How to check wheter the necrologue's length is less than 1,000,000 without recursion or just not to get MLE ??? [7] // Задача 1253. Некрологи 31 мар 2003 00:36

Evil Hacker Look inside (+) [6] // Задача 1253. Некрологи 31 мар 2003 01:13

DFS modification works very good!:

b[i] = 0 when this necrologue was not visited.
     = 1 when necrologue is beeing processed
     = 2 when necrologue was processed.

TextLen[i] = Length of i-th necrologue.
Text[i][j] - j-th letter of i-th necrologue.

1. b[i] = 0, TextLen[i] = 0; for all necrologues i.
2. We call DFS_Visit(1);

1. DFS_Visit(v)   v - necrologue
2. b[v] = 1        We are processing this necro
3. TextLen[v] = 0 Just in case
4. Sequently for all character s = 1, 2, 3, ...
5. If this is character of necro. increase TextLen[v] by 1
6. If this is link to other necro (say u) then do next
7. If b[u] = 1   then we gone to a loop write answer and exit
8. If b[u] = 2   then we already processed necro u and we know
TextLen[u], so we can increase TextLen[v] by TextLen[u].
9. If b[u] = 0   then we call DFS_Visit(u) and if it returned
increase TextLen[v] by TextLen[u].
10. b[v] = 0;

With each increase of TextLen we must check wether it becomes greater
than 1 000 000 if so Stop execution.

uuuuuuu Thank you ! // Задача 1253. Некрологи 31 мар 2003 19:59

uuuuuuu now TLE :(( -> how to do with the 1 sec time limit ? [4] // Задача 1253. Некрологи 31 мар 2003 20:31

i just do the dfs and then i write the answer with the recursion...
but always TLE

Evil Hacker Could you show your code ?? [3] // Задача 1253. Некрологи 31 мар 2003 20:41

uuuuuuu Here it is ... [2] // Задача 1253. Некрологи 1 апр 2003 19:24

var
n:array[1..9,0..1001]of char;
b:array[1..9]of byte;
textlen:array[1..9]of longint;
wypisane,ile:longint;

procedure wczytaj;
var
   i,k:longint;
   zn:char;
   zb:text;
begin
{assign(zb,'1253.in');
reset(zb);}
readln({zb,}ile);
for i:=1 to ile do
begin
k:=0;
read({zb,}zn);
   while zn<>'#'do
    begin
    inc(k);
    n[i,k]:=zn;
    read({zb,}zn)
    end;
inc(k);
n[i,k]:='#';
readln{(zb)}
end;
{close(zb)}
end;

procedure dzialaj(x:longint);
var
i,kt:longint;
zn:char;
begin
i:=1;
zn:=n[x,i];
while zn<>'#'do
   begin
    if zn='*' then
      begin
       kt:=ord(n[x,i+1])-48;
       i:=i+2;
       dzialaj(kt)
      end
    else
     begin
     write(zn);
     inc(i)
     end;
   zn:=n[x,i];
   end;
end;

procedure koniec;
begin
writeln('#');
halt
end;

procedure dfsvisit(v:byte);
var zn:char;
     i:integer;
begin
b[v]:=1;
i:=1;
textlen[v]:=0;
zn:=n[v,i];
while zn<>'#'do
begin
   if ((ord(zn)-48)>0)and((ord(zn)-48)<10)and(n[v,i-1]='*')then
    begin
     if b[ord(zn)-48]=1 then
      begin
       writeln('#');
       halt
      end
     else if b[ord(zn)-48]=2 then
       begin
       textlen[v]:=textlen[v]+textlen[ord(zn)-48];
       if textlen[v]>1000000 then koniec
       end
     else if b[ord(zn)-48]=0 then
      begin
      dfsvisit(ord(zn)-48);
      textlen[v]:=textlen[v]+textlen[ord(zn)-48];
      if textlen[v]>1000000 then koniec
      end;
     inc(i)
    end
   else if zn='*'then inc(i)
   else
     begin
     inc(textlen[v]);
     if textlen[v]>1000000 then koniec;
     inc(i)
     end;
   zn:=n[v,i]
end;
b[v]:=2;
end;

procedure dfs;
begin
fillchar(b,sizeof(b),0);
fillchar(textlen,sizeof(textlen),0);
dfsvisit(1)
end;

begin
wczytaj;
dfs;
dzialaj(1);
end.

I'm ALIVE. I know what's wrong know:(+) [1] // Задача 1253. Некрологи 5 апр 2003 20:35

It's the "return symbol".
In C/C++ "return symbol" is '\n', it is just 1 byte.
But in Pascal "return symbol" is #13#10, it is 2 byte.

My program made the same mistake as your :-)
Good Luck!

I'm ALIVE. Sorry, the post is wrong. I shall not post it here. // Задача 1253. Некрологи 5 апр 2003 20:37

> It's the "return symbol".
> In C/C++ "return symbol" is '\n', it is just 1 byte.
> But in Pascal "return symbol" is #13#10, it is 2 byte.
>
> My program made the same mistake as your :-)
> Good Luck!

Обсуждение задачи 1253. Некрологи