Yes. I have WA on test 22 too. Hello! I had WA on 22 test too. But later I realized that the two numbers in the input N and M mean N - the number of boxes verticaly and M - the number of boxes horizontaly. While I read the input as if they were the opposite. So, if you are wondering why your program doesn't work check this :). Maybe all the previous tests (1-21) hare N=M i don't know. yes, me too, WA on 22. I flipped M and N and AC. I flipped M and n and AC,too! Maybe the problem's description is wrong... 5 6 4 1 1 1 V 6 1 1 H 1 5 2 H 5 5 2 H 1 ans: 10 Can number of decks for already placed ships be more than 4? In another words, is this test possible: 30000 30000 1 1 1 30000 H 1 ? No. Read "Site news". Thank you! But there is one more problem: about what is N and what is M. Many people (and me) had WA #22, and when they flip n and m in their input they got AC. It happens because statement is not very clear: it's said N and M are "vertical/horizontal size of the playing field". This way of describing field size is not very common and makes some misunderstandings. Can't you change it to just "height/width of the playing field" or "number of horizontals/verticals of the playing field" ? Edited by author 24.08.2009 17:36 да, вполне на мой взгляд нечто похожее в тесте №6 can be. by my mind, the 6th test is like My idea of the problem was the following: 1) I know, how many K-ships can be placed on the FREE board. It's a rather simple formula 2) After that I check each placed ship. For him I found all the K ships that cannot be placed on the board thanks to this ship and add them to the special array (if they aren't there already). After that I subtract the number of elements in the array out of FREE board amount and that's the answer. Who can give me test 4? I didn't think about the case K=1. But now I fixed it and have WA 11. What's that test about? Maybe you don't check when n<k or m<k (than common formula return incorrect value) excuse me, can give me test 4? 7 7 4 3 3 1 V 5 3 1 H 3 5 1 H 5 5 1 V 1 Ans:24 A very important problem that you may forgot.When you calculate the sum of the ship could placed,if we Sum:=(n-k+1)*m+(m-k+1)*n. It's wrong,because k may >n&m. There is a test: 6 2 1 1 1 2 H 4 You should output 2. Good Luck! Need more tests to pass 14th test. Can anybody give me it? I have checked everything... But I have WA in this test. Help plz. #include <stdio.h> #include <math.h> int X,Y,L,E,P; struct NAV { int x,y,h,e,x1,x2,y1,y2; }; NAV Nav[50]; int V[30100],H[30100]; int Max(int a, int b) { if (a>b) return a; return b; } int OKH(int x,int y) { int i,k=1,j; for (j=0; j<L; ++j) for (i=0; i<E; ++i) if ((y>=Nav[j].y1) && (y<=Nav[j].y2)) if ((x+i>=Nav[j].x1) && (x+i<=Nav[j].x2)) return 0; return 1; } int OKV(int x,int y) { int i,k=1,j; for (j=0; j<L; ++j) for (i=0; i<E; ++i) if ((x>=Nav[j].x1) && (x<=Nav[j].x2)) if ((y+i>=Nav[j].y1) && (y+i<=Nav[j].y2)) return 0; return 1; } int main() { int i,j; scanf("%d %d %d",&Y,&X,&L); for (i=0; i<L; ++i) { scanf("%d %d %d %c",&Nav[i].x,&Nav[i].y,&Nav[i].e,&Nav[i].h); if (Nav[i].h=='V') { for (j=-1; j<=Nav[i].e; ++j) V[Nav[i].y+j]=1; H[Nav[i].x-1]=H[Nav[i].x]=H[Nav[i].x+1]=1; Nav[i].x1=Nav[i].x-1; Nav[i].y1=Nav[i].y-1; Nav[i].x2=Nav[i].x+1; Nav[i].y2=Nav[i].y+Nav[i].e; } else { for (j=-1; j<=Nav[i].e; ++j) H[Nav[i].x+j]=1; V[Nav[i].y-1]=V[Nav[i].y]=V[Nav[i].y+1]=1; Nav[i].x1=Nav[i].x-1; Nav[i].y1=Nav[i].y-1; Nav[i].x2=Nav[i].x+Nav[i].e; Nav[i].y2=Nav[i].y+1; } } scanf("%d",&E); for (j=1; j<=Y; ++j) { if (V[j]>0) { for (i=1; i<=X-E+1; ++i) if (OKH(i,j)) P++; } else { P+=X-E+1; } } if (E>1) for (i=1; i<=X; ++i) { if (H[i]>0) { for (j=1; j<=Y-E+1; ++j) if (OKV(i,j)) P++; } else { P+=Y-E+1; } } printf("%d",P); return 0; } I have WA #12? may be my program really have a bug, but how i can guess about your tricky tests? please help me, post there some test cases I have found a bug :) there was for (int i = 0; i < n; i++) instead of for (int i = 0; i <= n; i++) If you consider this problem two parts: put the ship vertically and horizontally, please notice that k=1. I checked at first all horizontal lines, then all vertical and had WA#17, but when I changed them, I got AC! HELP I need tests Edited by author 05.04.2006 17:14 I have tried to submit my program and got Wrong Answer on test 23. Also I have already read a topic below, but still WA. Give me some tests or tell what is wrong with my program: {$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+} {$M 16384,0,655360} Program SeaBattle; Type Point=Record X,Y:Integer; End; Var N,M:Integer;L:Byte; Points:Array[1..200] Of Point;PointsCount:Byte; K:Byte; PointersOnBeginning:Array[1..30001] Of Byte; I,J,P,R,S,W:Integer; Result:LongInt; Procedure ReadData; Var ShipX,ShipY,ShipLen:Integer; ShipDir:Char; Procedure AddPoint(X,Y:Integer); Var Index:Byte; Begin For Index:=1 To PointsCount Do If (Points[Index].X=X) And (Points[Index].Y=Y) Then Exit; Inc(PointsCount); Points[PointsCount].X:=X; Points[PointsCount].Y:=Y; End; Begin ReadLn(M,N,L); For I:=1 To L Do Begin Read(ShipX,ShipY,ShipLen); For J:=1 To 2 Do Read(ShipDir); ReadLn; If ShipDir='H' Then Begin For J:=1 To ShipLen Do AddPoint(ShipX+J-1,ShipY); If ShipY>=2 Then For J:=1 To ShipLen Do AddPoint(ShipX+J-1,ShipY-1); If ShipY<M Then For J:=1 To ShipLen Do AddPoint(ShipX+J-1,ShipY+1); If ShipX>=2 Then Begin If ShipY>=2 Then AddPoint(ShipX-1,ShipY-1); AddPoint(ShipX-1,ShipY); If ShipY<M Then AddPoint(ShipX-1,ShipY+1); End; If ShipX+ShipLen<=N Then Begin If ShipY>=2 Then AddPoint(ShipX+ShipLen,ShipY-1); AddPoint(ShipX+ShipLen,ShipY); If ShipY<M Then AddPoint(ShipX+ShipLen,ShipY+1); End; End Else Begin For J:=1 To ShipLen Do AddPoint(ShipX,ShipY+J-1); If ShipX>=2 Then For J:=1 To ShipLen Do AddPoint(ShipX-1,ShipY+J-1); If ShipX<N Then For J:=1 To ShipLen Do AddPoint(ShipX+1,ShipY+J-1); If ShipY>=2 Then Begin If ShipX>=2 Then AddPoint(ShipX-1,ShipY-1); AddPoint(ShipX,ShipY-1); If ShipX<N Then AddPoint(ShipX+1,ShipY-1); End; If ShipY+ShipLen<=M Then Begin If ShipX>=2 Then AddPoint(ShipX-1,ShipY+ShipLen); AddPoint(ShipX,ShipY+ShipLen); If ShipX<N Then AddPoint(ShipX+1,ShipY+ShipLen); End; End; End; ReadLn(K); End; Procedure Solve; Procedure SwapPoints(Var A,B:Point); Var TmpPoint:Point; Begin TmpPoint:=A; A:=B; B:=TmpPoint; End; Function GetCount(A:Integer):Integer; Begin If A>=K Then GetCount:=A-K+1 Else GetCount:=0; End; Begin For I:=1 To M Do PointersOnBeginning[I]:=0; For I:=1 To PointsCount-1 Do For J:=I+1 To PointsCount Do If Points[I].Y>Points[J].Y Then SwapPoints(Points[I],Points[J]); J:=1;If PointsCount>=1 Then PointersOnBeginning[Points[J].Y]:=J; For I:=2 To PointsCount Do If Points[I].Y<>Points[J].Y Then Begin For P:=J To I-2 Do For R:=P+1 To I-1 Do If Points[P].X>Points[R].X Then SwapPoints(Points[P],Points[R]); J:=I; PointersOnBeginning[Points[J].Y]:=J; End; If J<>PointsCount Then For P:=J To PointsCount-1 Do For R:=P+1 To PointsCount Do If Points[P].X>Points[R].X Then SwapPoints(Points[P],Points[R]); For J:=1 To M Do Begin W:=1; If PointersOnBeginning[J]<>0 Then Begin For I:=PointersOnBeginning[J] To PointsCount Do If Points[I].Y=J Then Begin Result:=Result+GetCount(Points[I].X-W); W:=Points[I].X+1; If Points[I].Y>J Then Break; End; End; Result:=Result+GetCount(N-W+1); End; If K=1 Then Exit; For I:=1 To N Do PointersOnBeginning[I]:=0; For I:=1 To PointsCount-1 Do For J:=I+1 To PointsCount Do If Points[I].X>Points[J].X Then SwapPoints(Points[I],Points[J]); J:=1;If PointsCount>=1 Then PointersOnBeginning[Points[J].X]:=J; For I:=2 To PointsCount Do If Points[I].X<>Points[J].X Then Begin For P:=J To I-2 Do For R:=P+1 To I-1 Do If Points[P].Y>Points[R].Y Then SwapPoints(Points[P],Points[R]); J:=I; PointersOnBeginning[Points[J].X]:=J; End; If J<>PointsCount Then For P:=J To PointsCount-1 Do For R:=P+1 To PointsCount Do If Points[P].Y>Points[R].Y Then SwapPoints(Points[P],Points[R]); For J:=1 To N Do Begin W:=1; If PointersOnBeginning[J]<>0 Then Begin For I:=PointersOnBeginning[J] To PointsCount Do If Points[I].X=J Then Begin Result:=Result+GetCount(Points[I].Y-W); W:=Points[I].Y+1; If Points[I].X>J Then Break; End; End; Result:=Result+GetCount(M-W+1); End; End; Procedure WriteData; Begin WriteLn(Result); End; Begin ReadData; Solve; WriteData; End. Program Sea_Battle; Var i,j,k,x,y,m,n,tot,ans:longint; d:array[1..30,1..4] of longint; a:array[1..2000,1..4] of longint; s:string; Procedure Cut(x1,y1,x2,y2:longint); Var i,j,k,L,bj,x,y:longint; xx,k1:longint; Begin j:=0; k1:=tot; while j<k1 do begin inc(j); if (a[j,1]>=x1)and(a[j,2]>=y1)and (a[j,3]<=x2)and(a[j,4]<=y2) then begin for L:=1 to 4 do a[j,L]:=0; end else begin bj:=0; if (x1>=a[j,1])and(x1<=a[j,3])and (((y1>=a[j,2])and(y1<=a[j,4]))or ((y2>=a[j,2])and(y2<=a[j,4]))or ((y1<=a[j,2])and(y2>=a[j,4]))) then bj:=1; if (x2>=a[j,1])and(x2<=a[j,3])and (((y1>=a[j,2])and(y1<=a[j,4]))or ((y2>=a[j,2])and(y2<=a[j,4]))or ((y1<=a[j,2])and(y2>=a[j,4]))) then begin if bj=0 then bj:=2 else begin inc(tot); a[tot]:=a[j]; a[tot,1]:=x2+1; end; end; if (y1>=a[j,2])and(y1<=a[j,4])and (((x1>=a[j,1])and(x1<=a[j,3]))or ((x2>=a[j,1])and(x2<=a[j,3]))or ((x1<=a[j,1])and(x2>=a[j,3]))) then begin if (x1<=a[j,1])and(x2>=a[j,3])and(bj=0) then bj:=3 else begin if x1<a[j,1] then x:=a[j,1] else x:=x1; if x2<a[j,3] then xx:=x2 else xx:=a[j,3]; inc(tot); a[tot]:=a[j]; a[tot,1]:=x; a[tot,4]:=y1-1; a[tot,3]:=xx; end; end; if (y2>=a[j,2])and(y2<=a[j,4])and (((x1>=a[j,1])and(x1<=a[j,3]))or ((x2>=a[j,1])and(x2<=a[j,3]))or ((x1<=a[j,1])and(x2>=a[j,3]))) then begin if (x1<=a[j,1])and(x2>=a[j,3])and(bj=0) then bj:=4 else begin if x1<a[j,1] then x:=a[j,1] else x:=x1; if x2<a[j,3] then xx:=x2 else xx:=a[j,3]; inc(tot); a[tot]:=a[j]; a[tot,1]:=x; a[tot,2]:=y2+1; a[tot,3]:=xx; end; end; case bj of 1:begin a[j,3]:=x1-1; end; 2:begin a[j,1]:=x2+1; end; 3:begin if x1<a[j,1] then x:=a[j,1] else x:=x1; if x2<a[j,3] then xx:=x2 else xx:=a[j,3]; a[j,1]:=x; a[j,4]:=y1-1; a[j,3]:=xx; end; 4:begin if x1<a[j,1] then x:=a[j,1] else x:=x1; if x2<a[j,3] then xx:=x2 else xx:=a[j,3]; a[j,1]:=x; a[j,2]:=y2+1; a[j,3]:=xx; end end; end; end; inc(tot); a[tot,1]:=x1; a[tot,2]:=y1; a[tot,3]:=x2; a[tot,4]:=y2; End; Procedure Search(z:longint); Var i,j,k,x1,y1,x2,y2:longint; Begin for i:=1 to n do begin if z=1 then begin x1:=d[i,1]-1; y1:=d[i,2]-m; if d[i,4]=1 then x2:=d[i,1]+1 else x2:=d[i,1]+d[i,3]; if d[i,4]=0 then y2:=d[i,2]+1 else y2:=d[i,2]+d[i,3]; end else begin x1:=d[i,1]-m; y1:=d[i,2]-1; if d[i,4]=1 then x2:=d[i,1]+1 else x2:=d[i,1]+d[i,3]; if d[i,4]=0 then y2:=d[i,2]+1 else y2:=d[i,2]+d[i,3]; end; if x1<1 then x1:=1; if y1<1 then y1:=1; if x2>x then x2:=x; if y2>y then y2:=y; Cut(x1,y1,x2,y2); end; for i:=1 to tot do if (a[i,1]<>0)and((a[i,3]-a[i,1]+1)* (a[i,4]-a[i,2]+1)>0) then ans:=ans-(a[i,3]-a[i,1]+1)* (a[i,4]-a[i,2]+1); End; Begin readln(x,y,n); ans:=x*y*2; fillchar(d, At first: what boundings for sizes of already placed ships? Can it be 0 or greater than 5? At second: my solution is not very fast and based on small size and quantity of already placed ships. Idea is simple: i have two arrays for verticals and horizontals and sets true if vertical or horizontal is empty and false otherwise. Then i look for all verticals and horizontals, trying locate vertical ship in all verticals and horizontal ship in all horizontals ( if number of decks of placing ship is 1 then i divide output value by 2 ). If current vertical (horizontal) line is empty, i just increment total value by "n- k+1"("m-k+1"), otherwise use full enumeration for line. I can predict TL, but always got a WA... =( I searched for bug many times and conclused, that i have bug in understanding statement of problem. Thank you for reading that. Could anyone help me? =) Code below: {$APPTYPE CONSOLE} var cur, i, j, n, m, l, k, r: longint; ships: array[1..100] of record x, y, d: longint; o: char; end; st: string; total: extended; curline, vempty, hempty: array[0..30001] of boolean; {} begin { assign( input, 'p1212.in' ); reset( input ); assign( output, 'p1212.out' ); rewrite( output );} {} readln( n, m, l ); for i := 1 to l do begin read( ships[i].x, ships[i].y, ships[i].d ); readln( st ); if ( ( pos( 'V', st ) = 0 ) and ( pos( 'v', st ) = 0 ) ) then ships[i].o := 'H' else ships[i].o := 'V'; end; read( k ); {} for i := 0 to 30001 do begin curline[i] := true; vempty[i] := true; hempty[i] := true; end; {} for i := 1 to l do begin case ( ships[i].o ) of 'V': begin for j := ( ships[i].y - 1 ) to ( ships[i].y + ships [i].d ) do hempty[j] := false; vempty[ships[i].x - 1] := false; vempty[ships[i].x] := false; vempty[ships[i].x + 1] := false; end; 'H': begin for j := ( ships[i].x - 1 ) to ( ships[i].x + ships [i].d ) do vempty[j] := false; hempty[ships[i].y - 1] := false; hempty[ships[i].y] := false; hempty[ships[i].y + 1] := false; end; end; end; {} total := 0; {} for i := 1 to n do begin if ( hempty[i] ) then total := total + m - k + 1 else begin for j := 0 to 30001 do curline[j] := true; curline[0] := false; curline[m+1] := false; for j := 1 to l do begin case ( ships[j].o ) of 'V': begin if ( ( ships[j].y - 1 <= i ) and ( ( ships[j].y + ships[j].d ) >= i ) ) then begin curline[ships[j].x-1] := false; curline[ships[j].x] := false; curline[ships[j].x+1] := false; end; end; 'H': begin if ( ( ( ships[j].y - 1 ) = i ) or ( ( ships [j].y ) = i ) or ( ( ships[j].y + 1 ) = i ) ) then for r := ( ships[j].x - 1 ) to ( ships[j].x + ships[j].d ) do curline[r] := false; end; end; end; {} cur := 0; for j := 1 to ( m + 1 ) do if ( curline[j] ) then inc( cur ) else begin if ( cur >= k ) then total := total + cur - k + 1; cur := 0; end; end; end; {} for i := 1 to m do begin if ( vempty[i] ) then total := total + n - k |
|