How I can do it on 0.001?

Edited by author 31.10.2008 02:29

You should find maximum matrix which is square, black and also contains white square inside rotated by 45 degrees. For instance:
1)
1 1 1 0 1 1 1
1 1 0 0 0 1 1
1 0 0 0 0 0 1
0 0 0 0 0 0 0
1 0 0 0 0 0 1
1 0 0 0 0 1 1
1 1 1 0 1 1 1
2)
1 1 1 1 0 1 1 1 1
1 1 1 0 0 0 1 1 1
1 1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1 1
1 1 1 0 0 0 1 1 1
1 1 1 1 0 1 1 1 1
are desired matrices maximum width of which you must find

I don't understand what dp has to do with this problem. I solved it using string hashing.

I test all case in discussion,but all answers right...
Can someone help..Thanks!!!

Maybe there is just small limits or not right topic??

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1
1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

20
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1
1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

I got WA 1. I think this problem is, easy but WA 1!!!

If anyone knows what test 2 is?

8
1 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 0 0 0 1 1
1 1 0 0 0 0 0 1
1 1 1 0 0 0 1 1
1 1 1 1 0 1 1 1
8
1 0 1 1 1 1 1 1
0 0 0 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 0 0 0 1 1
1 1 0 0 1 0 0 1
1 1 1 0 0 0 1 1
1 1 1 1 0 1 1 1
0

Answers:
5
3

isn't the output for:
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1

supposed to be 1?

the 1x1 sub-matrix containing just a single 0 should be a valid figure to cut out

8
1 0 1 1 0 1 1 1
0 0 0 1 0 1 1 1
1 0 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 0 0 0 1 1
1 1 0 0 0 0 0 1
1 1 1 0 0 0 1 1
1 1 1 1 0 1 1 1
0
answer: 5

Thank you.

here is test:
input:
7
1 1 1 0 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
0 0 0 0 0 0 0
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 1 1 1
0

output:
No solution

first my program write 3 for this.
hope can help you!!!

What can I do?

I use full search to solve this problem. But I don't know why WA for the 1st case. My code below:

[code deleted]

Thanks.

Edited by moderator 10.06.2006 21:12

program Project2;

{$APPTYPE CONSOLE}

uses
  SysUtils;
   var
   zzz:array[1..100,1..100,1..100] of byte;
   a:array[1..100,1..100] of byte;
   i,j,n,otv:integer;
procedure profi(x:integer);
   var
     i1,j1,i2,j2:integer;
     qy:boolean;
begin
   i1:=1;
   repeat
   j1:=1;
   repeat
     qy:=true;
     for i2:=i1 to n do
     for j2:=j1 to n do
     if a[i2,j2]<>zzz[x,i2-i1+1,j2-j1+1] then qy:=false;
     inc(j1);
   until (j1+x>n) or qy;
   inc(i1);
   until  (i1+x>n) or qy;
   if qy then otv:=x;
end;
begin
   for n:=3 to 100 do
   if n mod 3 = 0 then
   begin
   for i:=1 to n div 2 do
   for j:=1 to n div 2-i+1 do
   begin
    zzz[n,i,j]:=1;
    zzz[n,i,n-j+1]:=1;
    zzz[n,n-i+1,j]:=1;
    zzz[n,n-i+1,n-j+1]:=1;
   end;
   end;
   repeat
     fillchar(a,sizeof(a),0);
     readln(n);
     if n>2 then
     begin
     for i:=1 to n do
     begin
     otv:=0;
     for j:=1 to n do
     read(a[i,j]);
     readln;
     end;
     for i:=n downto 3 do
      if (i mod 2 =1) and (otv=0) then profi(i);
     if otv=0 then writeln('No solution')
     else writeln(otv);
     end
     else
     if n<>0 then writeln('No solution');
   until n=0;
end.
end.

I simplely do not understand it;