201 - Squares

[FlyDeath]

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]

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]

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]

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]

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]

It works!!Really thank you

[libereal]

[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);
readln(n);
readln(m);
for i := 1 to m do
begin
readln(c,a,b);
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;
if not found then writeln('No completed squares can be found.')
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]

[Farid Ahmadov]

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

[erfan]

What types of I/O you need it is not clear.You can pm your code then I will try...

[shelly]

i got WA every times Q_Q
please help
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]

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

[Dominik Michniewski]

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

[dedeibel]

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]

*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.

[A1]

I think you should go for some easy and bug less problem before the hard one. you can go to this page to find some easy problems to start solving.
http://www.geocities.com/acmbeganer/Acm ... Tricks.htm