201 - Squares

All about problems in Volume 2. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan

Post by FlyDeath » Thu Mar 14, 2002 4:00 pm

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:

Post by Stefan Pochmann » Fri Mar 15, 2002 3:38 am

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

Post by FlyDeath » Fri Mar 15, 2002 3:44 pm

I got the correct answer with the sample input on my computer.(BTW,I'm using Microsoft Windows XP :sad: )
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

Post by FlyDeath » Fri Mar 15, 2002 4:11 pm

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 :smile:

<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:

Post by Stefan Pochmann » Fri Mar 15, 2002 10:36 pm

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

Post by FlyDeath » Sat Mar 16, 2002 4:11 pm

It works!!Really thank you :smile:

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

p201 - what's wrong? help me

Post by libereal » Sat Jun 08, 2002 3:12 pm

[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
Experienced poster
Posts: 131
Joined: Thu Apr 17, 2003 8:39 am
Location: Baku, Azerbaijan

201 - Squares

Post by Farid Ahmadov » Sat Oct 18, 2003 5:37 pm

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
Location: Chittagong,Bangladesh
Contact:

Post by erfan » Sun Oct 19, 2003 12:29 pm

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

Post by shelly » Sun Oct 19, 2003 7:54 pm

i got WA every times Q_Q
please help
thx :wink:

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;
}

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

201 - Squares - Incorrect/Incomplete Problem Description

Post by Dreamer#1 » Fri Jul 23, 2004 10:57 am

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. :lol:

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:

Post by Dominik Michniewski » Sun Jul 25, 2004 10:29 pm

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?

Post by dedeibel » Mon Mar 14, 2005 9:48 pm

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:

Post by dedeibel » Tue Mar 15, 2005 8:59 pm

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

User avatar
A1
Experienced poster
Posts: 173
Joined: Wed Jan 28, 2004 3:34 pm
Location: Bangladesh

Post by A1 » Thu Mar 17, 2005 1:17 pm

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

Post Reply

Return to “Volume 2 (200-299)”