ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1220. Stacks

ML on test #10!!! But program should not use more 450K. HELP! See code inside.
Posted by SPbETU#1 2 Aug 2004 12:41
Should correct algo use not more than 400K?
Help need.

const
  maxnumel = 10;
  maxm = 1000;
  maxel = (100000 div maxnumel) + 1;
  good : set of char = ['A'..'Z'];

var
  stack : array[1..maxm] of integer;
  next : array[1..maxel] of integer;
  data : array[1..maxel, 1..maxnumel] of integer;
  size : array[1..maxm] of byte;
  ch : char;
  n, i, num, stacknum : integer;
  free : integer;
  st : string;

procedure readword(var st : string);
begin
  read(ch);
  st := '';
  while not(ch in good) do read(ch);
  while ch in good do begin
    st := st + ch;
    read(ch);
  end;
end;

begin
  fillchar(stack, sizeof(stack), 0);
  fillchar(size, sizeof(size), 0);
  read(n);
  free := 0;
  for i := 1 to n do begin
    readword(st);
    if st = 'PUSH' then begin
      readln(stacknum, num);

      if (size[stacknum] > 0)and(size[stacknum] < maxnumel) then begin
        inc(size[stacknum]);
        data[stack[stacknum]][size[stacknum]] := num;
      end else begin
        inc(free);
        next[free] := stack[stacknum];
        stack[stacknum] := free;
        size[stacknum] := 1;
        data[free, 1] := num;
      end;

    end else begin
      read(stacknum);
      if size[stacknum] < 1 then begin
        stack[stacknum] := next[stack[stacknum]];
        size[stacknum] := maxnumel;
      end;
      writeln(data[stack[stacknum], size[stacknum]]);
      dec(size[stacknum]);
    end;
  end;
end.

Thanks for attention!

Edited by author 02.08.2004 12:43
This problem can not be accepted on Pascal. :( Use C or C++...
Posted by SPbETU#1 4 Oct 2004 18:10
SizeOf(Integer) = 4. Use SmallInt.
After adding type integer = smallint it gets WA:
711430 19:20:44
4 окт 2004 TECTOBOP 1220 Pascal Wrong Answer 3 0.015 409 КБ

Edited by author 04.10.2004 19:21
Re: SizeOf(Integer) = 4. Use SmallInt.
Posted by Sergey Simonchik, SPbETU#1 5 Oct 2004 17:42
Hmmm... Citation from statement : "...and B is an integer (0 <= B <= 10^9)...".  So it's impossible to use _only_ smallint type in program, is not it?

But you are right, my solution has little bug :). But I got ML on test#10 again after fixing it. And only after submitting it on C++ I finally got AC.

In any case, i think that "Stacks" is one of the worst problems on acm.timus.ru... :(((
Problemsolvers, who use C, have some superiority.
450+373=823 - it's to much for this problem


Edited by author 06.10.2004 20:09
Re: 450+373=823 - it's to much for this problem
Posted by Sergey Simonchik, SPbETU#1 7 Oct 2004 13:19
I realized fully it :)