Admins, why does my program that was AC earlier gets WA 10 now? This problem was not rejudged... Please answer my question. Please check test#5, i think it wrong. expression contains successively two registers without the operator between them. #define S 32768 inline bool sc(char*a,char*b){ while(*a==*b)++a,++b; return *b==0; } ............ ............ char s[S],*j; {char a[S]; gets(a); char *i; for(i=a;*i;++i)if(*i>='a' && *i<='z')*i+='A'-'a'; for(i=a,j=s;*i;){ if(sc(i,"NOT"))*(j++)='!',i+=3; else if(sc(i,"AND"))*(j++)='&',i+=3; else if(sc(i,"OR"))*(j++)='|',i+=2; else if(sc(i,"TRUE"))*(j++)='1',i+=4; else if(sc(i,"FALSE"))*(j++)='0',i+=5; else if(*i>='A' && *i<='Z' || *i=='(' || *i==')') *(j++)=*(i++); else ++i; } *j='*'; #define IsReg(x) (x>='A' && x<='Z' || x=='0' || x=='1') for(i=s;*i!='*';++i) if(IsReg(i[0]) && IsReg(i[1])){ *i/=*i-*i; } } ............ ............ Edited by author 02.08.2006 15:47 if the last word FALSE or TRUE, then this fucntion returun wrong result... inline bool sc(char*a,char*b){ while(*a==*b)++a,++b; return *b==0; } A) How large can the boolean expression be? Where are no restrictions about the first line in the statement. B) Is it necessary to optimize the expression? Or we can just read it in reverse polish manner and use without worrying about TLE? I didn't do any optimizations - just what I have invented by myself without thinking hard - and got AC 0.015. Got AC with 0.001 sec from the first try. I used Bauer algo (You can read about it at algolist.manual.ru). What was Your idea? Just so-so. See mine : 932980 10:09:29 25 Sep 2005 ahyangyi_newid 1101 C++ Accepted 0.015 226 KB Only used 5kb more than you , and our programs run in the same speed. And my program consumes 100 kb more than Yours :(, but runs 10 times faster (0.001 sec:) I used boolean Expression to deal with the it . I can not find where is wrong in my code indeed. can anyone help me ? Program Bolan; Const h:array[0..4] of string=('(',')','OR','AND','NOT'); g:array[1..4,1..2] of shortint= ((1,0),(0,-1),(-1,0),(0,1)); Type Lion=record Value,bj:Shortint; end; xm=array[0..5000] of Lion; Var i,j,k,m,n,atop,btop,x,y,k1,k2,bak1:longint; code,direct:integer; s:string; c:char; a,bak:xm; b:array[0..5000] of longint; e:array[0..26] of longint; d:array[0..26,1..2] of longint; Turn:array[0..100,1..2] of longint; Function Find(c:string):integer; var i:integer; begin for i:=0 to 4 do if h[i]=c then begin Find:=i; exit; end; end; Procedure Go(c:string); var i,j:integer; d:char; Begin j:=find(c); if btop=0 then begin inc(btop); b[1]:=j; end else begin if j=0 then begin inc(btop); b[btop]:=0; end else if (b[btop]=0)and(j=1) then dec(btop) else begin while (j<b[btop])and(btop>0) do begin inc(atop); a[atop].value:=b[btop]; a[atop].bj:=b[btop]; dec(btop); end; if (b[btop]=0)and(j=1)and(btop<>0) then dec(btop) else begin inc(btop); b[btop]:=j; end; end; end; End; Function Main:boolean; var i,j:longint; bb:boolean; Begin for i:=1 to atop do if a[i].bj=5 then a[i].value:=e[a[i].value]; repeat bb:=true; for i:=1 to atop do if a[i].bj<5 then begin bb:=false; break; end; if not(bb) then begin case a[i].bj of 2:a[i-2].value:=a[i-2].value or a[i-1].value; 3:a[i-2].value:=a[i-2].value and a[i-1].value; 4:a[i-1].value:=1-a[i-1].value; end; if a[i].bj=4 then begin a[i-1].bj:=6; move(a[i+1],a[i],(atop-i)*2); dec(atop); end else begin a[i-2].bj:=6; move(a[i+1],a[i-1],(atop-i)*2); dec(atop,2); end; end; until bb; if a[1].value=1 then Main:=true else Main:=false; End; Procedure Inside(s:string); Begin while s[1]=' ' do delete(s,1,1); while s[Length(s)]=' ' do delete(s,length(s),1); if s='TRUE' then begin inc(atop); a[atop].value:=1; a[atop].bj:=6; end else if s='FALSE' then begin inc(atop); a[atop].value:=0; a[atop].bj:=6; end else if (s='OR')or(s='AND')or(s='NOT') then Go(s) else if (length(s)=1)and(ord(s[1])>64) and(ord(s[1])<91) then begin inc(atop); a[atop].value:=ord(s[1])-64; a[atop].bj:=5; end; End; Procedure Init; Var i:longint; s:string; c:char; Begin fillchar(a,sizeof(a),0); fillchar(e,sizeof(e),0); fillchar(b,sizeof(b),0); fillchar(turn,sizeof(turn),0); for i:=1 to 26 do begin d[i,1]:=maxlongint; d[i,2]:=maxlongint; end; s:=''; atop:=0; btop:=0; while not(eoln) do begin read(c); if (c='(')or(c=')')or(c=' ') then begin if s<>'' then Inside(s); if (c='(')or(c=')') then go(c); s:=''; end else s:=s+c; end; readln; if s<>'' then Inside(s); for i:=btop downto 1 do begin inc(atop); a[atop].value:=b[i]; a[atop].bj:=b[i]; end; btop:=0; End; Begin Init; readln(n,m,k); for i:=1 to m do readln(turn[i,1],turn[i,2]); for i:=1 to k do begin read(k1,k2); readln(s); while s[1]=' ' do delete(s,1,1); while s[Length(s)]=' ' do delete(s,length(s),1); j:=ord(s[1])-64; d[j,1]:=k1; d[j,2]:=k2; end; Direct:=1; x:=0; y:=0; while true do begin writeln(x,' ',y); for j:=1 to 26 do if (x=d[j,1])and(y=d[j,2]) then e[j]:=1-e[ How foolish am I ! I actually thought that there is only one point for one register , so I set the array d:array[1..26,1..2] of integer to record the Capital Letter's position . My God ! My English is poor, but my IQ is even Poorer I guess that you meant your English was nicer than your IQ ... :) Can onyone tell me, where my programm fails. My programm gets Output Limit, and I don't know where it wrong. I convert Boolean expression into a postfix form and simply simulate a robot movement. CONST Dim = 10007; Dim2 = 101; TYPE TBuf = Array[0..Dim] of char; VAR Buf,Stack:TBuf; BST:Array[0..3007] of boolean; BP,SP:integer; CurrCh:char; F:Array[-Dim2..Dim2,-Dim2..Dim2] of char; Reg:Array['A'..'\'] of boolean; N:integer; FUNCTION GetLexem:char; var S:string; begin S:=''; while not (CurrCh in ['A'..'Z','(',')',#13]) do read(CurrCh); if CurrCh=#13 then begin GetLexem:=#13; Exit end; if (CurrCh='(') or (CurrCh=')') then begin GetLexem:=CurrCh; read (CurrCh); Exit end; while CurrCh in ['A'..'Z'] do begin S:=S+CurrCh; read(CurrCh) end; if S='NOT' then S:='!'; if S='AND' then S:='&'; if S='OR' then S:='|'; if S='TRUE' then S:='['; if S='FALSE' then S:='\'; GetLexem:=S[1]; if length(S)>1 then begin writeln('Error!'); Halt(0) end; end; PROCEDURE AddBuf(C:char); begin inc(BP); Buf[BP]:=C; end; FUNCTION Prior(C:char):integer; begin case C of '(':Prior:=0; '|':Prior:=1; '&':Prior:=2; '!':Prior:=3; end; end; PROCEDURE AddStack(C:char); var P:integer; begin if C='(' then begin inc(SP); Stack[SP]:='('; Exit end; if C=')' then begin while Stack[SP]<>'(' do begin AddBuf(Stack[SP]); dec (SP) end; dec(SP); Exit; end; P:=Prior(C); while (SP>0) and (P<=Prior(Stack[SP])) do begin AddBuf(Stack[SP]); dec(SP); end; inc(SP); Stack[SP]:=C; end; PROCEDURE ConvertProgram; var C:char; begin BP:=0; SP:=0; CurrCh:=#0; repeat C:=GetLexem; if C=#13 then break; if (C>='A') and (C<='\') then AddBuf(C) else AddStack(C); until C=#13; read(CurrCh); while SP>0 do begin AddBuf(Stack[SP]); dec(SP) end; end; PROCEDURE ReadPoints; var M,K,R,C,i:integer; ch1,ch2:char; begin readln(N,M,K); for i:=1 to M do begin readln(R,C); F[R,C]:='#'; end; for i:=1 to K do begin readln(R,C,ch1,ch2); F[R,C]:=ch2; end; end; PROCEDURE TurnRight(var DR,DC:integer); begin if Abs(DR)=1 then begin DC:=-DR; DR:=0 end else begin DR:=DC; DC:=0 end; end; PROCEDURE TurnLeft(var DR,DC:integer); begin if Abs(DR)=1 then begin DC:=DR; DR:=0 end else begin DR:=-DC; DC:=0 end; end; FUNCTION Count:boolean; var BSP,i:integer; begin BSP:=0; for i:=1 to BP do begin if Buf[i] in ['A'..'\'] then begin inc(BSP); BST[BSP]:=Reg[Buf[i]] end else begin if Buf[i]='!' then BST[BSP]:=not BST[BSP]; if Buf[i]='&' then begin BST[BSP]:=BST[BSP-1] and BST [BSP]; dec(BSP) end; if Buf[i]='|' then begin BST[BSP]:=BST[BSP-1] or BST [BSP]; dec(BSP) end; end; end; Count:=BST[BSP]; if BSP<>1 then begin writeln('Error!'); Halt(0) end; end; PROCEDURE Simulate; var ch:char; R,C,DR,DC:integer; begin for ch:='A' to '\' do Reg[ch]:=false; Reg['[']:=true; R:=0; C:=0; DR:=1; DC:=0; if F[0,0]<>#0 then Reg[F[0,0]]:=not Reg[F[0,0]]; repeat writeln(R,' ',C); R:=R+DR; C:=C+DC; if (Abs(R)>N) or (Abs(C)>N) then break; if F[R,C]='#' then begin if Count then TurnRight(DR,DC) else TurnLeft(DR,DC); end else if F[R,C]<>#0 then Reg[F[R,C]]:=not Reg[F [R,C]]; until false; end; BEGIN { assign(INPUT,'robot.dat'); reset(INPUT);} ConvertProgram; ReadPoints; Simulate; END. > Can onyone tell me, where my programm fails. > My programm gets Output Limit, and I don't know where it wrong. > I convert Boolean expression into a postfix form and simply simulate > a robot movement. > > CONST Dim = 10007; > Dim2 = 101; > > TYPE TBuf = Array[0..Dim] of char; > VAR Buf,Stack:TBuf; > BST:Array[0..3007] of boolean; > BP,SP:integer; > CurrCh:char; > F:Array[-Dim2..Dim2,-Dim2..Dim2] of char; > Reg:Array['A'..'\'] of boolean; > N:integer; > > FUNCTION GetLexem:char; > var S:string; > begin > S:=''; > while not (CurrCh in ['A'..'Z','(',')',#13]) do read(CurrCh); > if CurrCh=#13 then begin GetLexem:=#13; Exit end; > if (CurrCh='(') or (CurrCh=')') then begin GetLexem:=CurrCh; read > (CurrCh); Exit end; > while CurrCh in ['A'..'Z'] do > begin S:=S+CurrCh; read(CurrCh) end; > if S='NOT' then S:='!'; > if S='AND' then S:='&'; > if S='OR' then S:='|'; > if S='TRUE' then S:='['; > if S='FALSE' then S:='\'; > GetLexem:=S[1]; > if length(S)>1 then begin writeln('Error!'); Halt(0) end; > end; > > PROCEDURE AddBuf(C:char); > begin > inc(BP); Buf[BP]:=C; > end; > > FUNCTION Prior(C:char):integer; > begin > case C of > '(':Prior:=0; > '|':Prior:=1; > '&':Prior:=2; > '!':Prior:=3; > end; > end; > > PROCEDURE AddStack(C:char); > var P:integer; > begin > if C='(' then begin inc(SP); Stack[SP]:='('; Exit end; > if C=')' then begin > while Stack[SP]<>'(' do begin AddBuf(Stack[SP]); dec > (SP) end; > dec(SP); > Exit; > end; > P:=Prior(C); > while (SP>0) and (P<=Prior(Stack[SP])) do > begin > AddBuf(Stack[SP]); > dec(SP); > end; > inc(SP); Stack[SP]:=C; > end; > > PROCEDURE ConvertProgram; > var C:char; > begin > BP:=0; SP:=0; > CurrCh:=#0; > repeat > C:=GetLexem; > if C=#13 then break; > if (C>='A') and (C<='\') then AddBuf(C) else AddStack(C); > until C=#13; > read(CurrCh); > while SP>0 do begin AddBuf(Stack[SP]); dec(SP) end; > end; > > PROCEDURE ReadPoints; > var M,K,R,C,i:integer; > ch1,ch2:char; > begin > readln(N,M,K); > for i:=1 to M do > begin > readln(R,C); > F[R,C]:='#'; > end; > for i:=1 to K do > begin > readln(R,C,ch1,ch2); > F[R,C]:=ch2; > end; > end; > > PROCEDURE TurnRight(var DR,DC:integer); > begin > if Abs(DR)=1 then begin DC:=-DR; DR:=0 end > else begin DR:=DC; DC:=0 end; > end; > > PROCEDURE TurnLeft(var DR,DC:integer); > begin > if Abs(DR)=1 then begin DC:=DR; DR:=0 end > else begin DR:=-DC; DC:=0 end; > end; > > FUNCTION Count:boolean; > var BSP,i:integer; > begin > BSP:=0; > for i:=1 to BP do > begin > if Buf[i] in ['A'..'\'] > then begin inc(BSP); BST[BSP]:=Reg[Buf[i]] end > else begin > if Buf[i]='!' then BST[BSP]:=not BST[BSP]; > if Buf[i]= const dir : array[1..4, 1..2]of shortint = ((1, 0), (-1, 0), (0, 1), (0, -1)); left : array[1..4]of byte = (3, 4, 2, 1); right : array[1..4]of byte = (4, 3, 1, 2); var a : array[-101..101, -101..101]of byte; v : array['A'..'Z']of boolean; i, n, m, k, d : integer; x, y : shortint; exp : string; ch : char; ans : boolean; function leftbracket(i : integer) : integer; var j : integer; begin j := 0; repeat if exp[i] = '(' then inc(j); if exp[i] = ')' then dec(j); dec(i); until j = 0; leftbracket := i + 1; end; function getopr(a, b : integer) : integer; var i, j, k : integer; begin i := b; j := 0; while i >= a do begin if exp[i] = '|' then begin getopr := i; exit; end; if exp[i] = '&' then if j < 2 then begin k := i; j := 2; end; if exp[i] = '!' then if j < 4 then begin k := i; j := 3; end; if exp[i] = ')' then i := leftbracket(i); dec(i); end; getopr := k; end; function eval(a, b : integer) : boolean; var i : integer; l, r : boolean; begin if a = b then begin if exp[a] = 't' then eval := true else if exp[a] = 'f' then eval := false else eval := v[exp[a]]; exit; end; if (exp[a] = '(') and (exp[b] = ')') and (leftbracket(b) = a) then begin eval := eval(a + 1, b - 1); exit; end; i := getopr(a, b); if exp[i] = '|' then begin l := eval(a, i - 1); r := eval(i + 1, b); eval := l or r; end else if exp[i] = '&' then begin l := eval(a, i - 1); r := eval(i + 1, b); eval := l and r; end else begin l := eval(i + 1, b); eval := not l; end; end; procedure convert; var i : integer; begin i := pos('OR', exp); while i > 0 do begin delete(exp, i, 2); insert('|', exp, i); i := pos('OR', exp); end; i := pos('AND', exp); while i > 0 do begin delete(exp, i, 3); insert('&', exp, i); i := pos('AND', exp); end; i := pos('NOT', exp); while i > 0 do begin delete(exp, i, 3); insert('!', exp, i); i := pos('NOT', exp); end; i := pos('TRUE', exp); while i > 0 do begin delete(exp, i, 4); insert('t', exp, i); i := pos('TRUE', exp); end; i := pos('FALSE', exp); while i > 0 do begin delete(exp, i, 5); insert('f', exp, i); i := pos('FALSE', exp); end; i := pos(' ', exp); while i > 0 do begin delete(exp, i, 1); i := pos(' ', exp); end; end; begin assign(input, '1101.in'); reset(input); readln(exp); convert; readln(n, m, k); for i := 1 to m do begin readln(x, y); a[x, y] := 1; end; for i := 1 to k do begin read(x, y); read(ch); while not (ch in ['A'..'Z']) do read(ch); a[x, y] := ord(ch); end; close(input); fillchar(v, sizeof(v), 0); x := 0; y := 0; d := 1; repeat writeln(x, ' ', y); x := x + dir[d, 1]; y := y + dir[d, 2]; if a[x, y] = 1 then begin ans := eval(1, length(exp)); if ans then d := right[d] else d := left[d]; end else if a[x, y] > 60 then v[chr(a[x, y])] := not v[chr(a[x, y])]; until (abs(x) > n) or (abs(y) > n); end. there's a bug in getopr function > there's a bug in getopr function change 4 numbers in getopr function and u'll get accepted ;) HINT : if exp = 'NOT FALSE AND FALSE' ur program evaluate it this way : NOT (FALSE AND FALSE) Please say how to fix the bug clearly. function getopr(a, b : integer) : integer; var i, j, k : integer; begin i := b; j := 0; while i >= a do begin if exp[i] = '|' then begin getopr := i; exit; end; if exp[i] = '&' then if j < 4 then begin k := i; j := 3; end; if exp[i] = '!' then if j < 2 then begin k := i; j := 2; end; if exp[i] = ')' then i := leftbracket(i); dec(i); end; getopr := k; end; > function getopr(a, b : integer) : integer; > var i, j, k : integer; > begin > i := b; > j := 0; > while i >= a do > begin > if exp[i] = '|' then begin getopr := i; exit; end; > if exp[i] = '&' then > if j < 4 then > begin k := i; j := 3; end; > if exp[i] = '!' then > if j < 2 then > begin k := i; j := 2; end; > if exp[i] = ')' then i := leftbracket(i); > dec(i); > end; > getopr := k; > end; |
|