## 201 - Squares

Moderator: Board moderators

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I am in a very strange situation.I got output limit exceeded.
Is there any strange input??

Here is my code(maybe there is some problem in it,BTW,I use DP)

Code: Select all

``````#include <stdio.h>
#include <math.h>

void main()
{
/*	freopen("out.txt","w",stdout);
freopen("in.txt","r",stdin);*/
int dot;
int lines;
char temp;
int x,y;
bool cv[10][10];
bool ch[10][10];
int v[10][10];
int h[10][10];
int i,j,k,l;
int cases=0;
int count=0;
int flag=0;
while(scanf("%d",&dot)!=EOF)
{
scanf("%d",&lines);
cases++;
if(cases!=1)
printf("n**********************************nn");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
{
cv[i][j]=0;
ch[i][j]=0;
v[i][j]=0;
h[i][j]=0;
}
}
for(i=0;i<lines;i++)
{
scanf("%s %d %d",&temp,&x,&y);
if(temp=='H')
ch[x-1][y-1]=1;
else if(temp=='V')
cv[y-1][x-1]=1;
}
for(i=0;i<dot;i++)
for(j=0;j<dot;j++)
for(k=0;k<j;k++)
h[i][j]=h[i][j]+(int)fabs(ch[i][k]-1);
for(i=0;i<dot;i++)
for(j=0;j<dot;j++)
for(k=0;k<i;k++)
v[i][j]=v[i][j]+(int)fabs(cv[k][j]-1);
printf("Problem #%dnn",cases);
flag=0;
for(i=1;i<dot;i++)
{
count=0;
for(j=0;j<dot-i;j++)
for(k=0;k<dot-i;k++)
if(h[j][k+i]-h[j][k]==0&&h[j+i][k+i]-h[j+i][k]==0)
if(v[j][k]-v[j+i][k]==0&&v[j][k+i]-v[j+i][k+i]==0)
count++;
if(count!=0)
{
flag=1;
printf("%d square (s) of size %dn",count,i);
}
}
if(flag==0)
printf("No completed squares can be found.n");
}
}
``````

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
You already produce endless output for the sample input. Btw, it should be "int main", otherwise I have to change it to make it compile.

I guess the bug is that you should use "%c" instead of "%s" for reading the single char tmp.

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I got the correct answer with the sample input on my computer.(BTW,I'm using Microsoft Windows XP )
I can't figure out what make it get endless output.
And %c will get 'n'.That's why I use %s
Can you give me the answer of sample input my program make on you computer?

<font size=-1>[ This Message was edited by: FlyDeath on 2002-03-15 14:47 ]</font>

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I got AC by changing the code of %s into this:

Code: Select all

``````			while(1)
{
temp=getchar();
if(temp=='H'||temp=='V')
break;
}
scanf("%d %d",&x,&y);
``````
I Really appreciate you,Stefan

<font size=-1>[ This Message was edited by: FlyDeath on 2002-03-15 15:11 ]</font>

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
You're right. But if you add a space character before the %c, like scanf( " %c", ...), then it will skip all whitespace before the character you really want. Try it.

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
It works!!Really thank you

libereal
New poster
Posts: 1
Joined: Sat Jun 08, 2002 3:10 pm

### p201 - what's wrong? help me

[pascal]
program squares (input , output);

const
MaxN = 9;
var
found : boolean;
nump : integer;
n , m : integer;
h , v : array[0..MaxN,0..MaxN] of shortint;
d : array[1..2,0..MaxN,0..MaxN] of integer;
num , key : array[1..MaxN] of integer;

procedure init;
var
i , j : integer;
begin
found := False;
for i := 1 to n do
begin
num := 0;
for j := 1 to n do
begin
h[i,j] := 0;
v[i,j] := 0;
d[1,i,j] := 0;
d[2,i,j] := 0;
end;
end;

end;

procedure put;
var
i : integer;
c : char;
a , b : integer;
begin
inc(nump);
for i := 1 to m do
begin
if c = 'H' then h[a,b] := 1
else if c = 'V' then v[b,a] := 1;
end;
end;

procedure swap ( var a , b : integer );
var
t : integer;
begin
t := a;
a := b;
b := t;
end;

function min ( a , b : integer ) : integer;
begin
if a < b then min := a else min := b;
end;

procedure process;
var
i , j , k : integer;
begin
for i := 1 to n do
for j := 1 to n do
begin
if h[i,j-1] = 1 then d[1,i,j] := d[1,i,j-1] + 1;
if v[i-1,j] = 1 then d[2,i,j] := d[2,i-1,j] + 1;
end;

for i := 2 to n do
for j := 2 to n do
for k := 1 to min(i,j) do
if ( d[1,i,j] >= k ) and ( d[1,i-k,j] >= k ) then
if ( d[2,i,j] >= k ) and ( d[2,i,j-k] >= k ) then
begin
found := True;
inc(num[k]);
end;

for i := 1 to n do key := i;
for i := 1 to n - 1 do
for j := i + 1 to n do
if num > num[j] then
begin
swap(num,num[j]);
swap(key,key[j]);
end;
end;

procedure output;
var
i : integer;
begin
if nump > 1 then
begin
writeln('**********************************');
writeln;
end;
writeln('Problem #',nump);
writeln;
else
begin
for i := 1 to n do
if num > 0 then
writeln(key,' square (s) of size ',num);
end;
writeln;
end;

procedure main;
begin
init;
put;
process;
output;
end;

begin
while not eof(input) do main;
end.
[/pascal]

Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

### 201 - Squares

Hi. I need your help. I get WA. My program gives correct answers for sample input and all inputs I made. Please give some correct I/O
_____________
NO sigNature

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:
What types of I/O you need it is not clear.You can pm your code then I will try...

shelly
New poster
Posts: 1
Joined: Tue Sep 30, 2003 3:49 pm

### help 201 WA

i got WA every times Q_Q
thx

Code: Select all

``````#include <iostream.h>

void init_array(int H[][11], int V[][11])
{
int i,j;
for (i=0;i<11;i++)
for (j=0;j<11;j++){
H[i][j] = 0;
V[i][j] = 0;
}
}
void init_count(int Size[])
{
for (int i=0;i<11;i++)
Size[i]=0;
}

int main()
{
int i,j,k,t,num=0;
int max_size,lines,count;
int H[11][11],V[11][11],size[11];
char ch;
bool issquare;

while (cin >> max_size) {
cin >> lines;
init_array(H,V);
for (k=0;k<lines;k++){
cin >> ch >> i >> j;
if (ch == 'H')
H[i][j] = 1;
else
V[i][j] = 1;
}
num++;
init_count(size);
for(k=1;k<max_size;k++) {
count = 1;
for (i=1;i<max_size;i++)
for (j=1;j<max_size;j++) {
for (t=0;t<k;t++) {
if ((H[i][j+t]==1)&&(V[j][i+t]==1))
issquare = true;
else{
issquare = false;
break;
}
}
if (issquare) {
for(t=0;t<k;t++)
if ((H[i+k][j+t]==1)&&(V[j+k][i+t]==1))
issquare = true;
else {
issquare = false;
break;
}
}
if (issquare) {
size[k] = count;
count++;
}
}
}
issquare = false;
cout << endl;
cout << "*************************************"<<endl;
cout <<endl<< "Problem #"<<num<<endl<<endl;
for (i=1;i<=max_size;i++)
if (size[i]!=0){
cout <<size[i] << " square (s) of size "<<i<<endl;
issquare = true;
}
if (!issquare)
cout << "No completed squares can be found.";

cout <<endl;
}
return 0;
}
``````

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

### 201 - Squares - Incorrect/Incomplete Problem Description

From Problem Decription:

Output for a record consists of the number of squares of each size on the board, from the smallest to the largest. lf no squares of any size exist, your program should print an appropriate message indicating so.
I don't think this is enough to mean that if there are squares of sizes say 2 and 9 but no other squares of intermediate sizes then you should only print two lines indicating that information and not print any lines for the intermediate sizes ( 3 to 8 ). It wasted me 30 mins to figure out that is what I'm supposed to do to get AC, and that also I did simply by guessing.

The problem description should clearly specify that number of squares of an intermediate size (between the smallest and largest) should NOT be printed if the number is zero, which clearly is missing in the problem statement. It only states that print a line stating no squares exist only if there is no squares of any size which surely doesn't mean that I should skip to print what I mentioned above.

regards

-Dreamer
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I think, that description is clear enough.
If they wrote , that you have to print number of squares of each size on the board , it's simple to me: print only founded squares, without such , which aren't on board
I also think, that in all problems if you have to print zeros, they write this direct.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

dedeibel
New poster
Posts: 3
Joined: Sun Mar 13, 2005 11:39 pm
Location: Germany
Contact:

### 201 Output?

Hi,

I found this page and wanted to solve some problems. I chosed number 201, counting the squares.

http://online-judge.uva.es/p/v2/201.html

I am creating the output just like the example but I am not sure if it is right, getting WA all the time.

For one of my tests it would be:

Code: Select all

``````Problem #1

3 square (s) of size 1
1 square (s) of size 4
1 square (s) of size 7
1 square (s) of size 8

**********************************

Problem #2

4 square (s) of size 1

**********************************

Problem #3

No completed squares can be found.

**********************************

Problem #4

1 square (s) of size 1
1 square (s) of size 3
``````
There is also a mistake note, does it mean the output in the example is correct now?

http://online-judge.uva.es/p/v2/201.fix.html

If you have some time, maybe you could give me another output example how you would understand the description.

One more thing, is it ok to trust in the right and valid input, I mean is there a test for error handling?

Thanks.

dedeibel
New poster
Posts: 3
Joined: Sun Mar 13, 2005 11:39 pm
Location: Germany
Contact:
*sight* after 3 days of trying my code became more and more crapy and my motivation reached zero. Still WA.

Too bad my first try here had to go like this, it will take some time untill I get the mood to go for another problem.
so little time ...

A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm