2 2 0
2
ans:4.

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

?

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?

Try this

6 2 1
1 1 2 H
4

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

If you consider this problem two parts: put the ship vertically and
horizontally, please notice that k=1.

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