10703 - Free spots

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

Moderator: Board moderators

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: >>10703 need help....

Post by Martin Macko »

Suppose you have a rectangular grid drawn on a paper. You draw some filled rectangles on the paper. Your task is to find the area that is not filled.

Code: Select all

5 5 2
1 1 3 2
3 0 3 5
For this input the grid would be like this ("." empty, "F" filled)

Code: Select all

  12345
1 ..F..
2 .FFF.
3 .FFF.
4 ..F..
5 ..F..
And answer would be 16.

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

10703 need help!!!

Post by mohsincsedu »

Hello All.....
May be i do not understand What the problem says!!!!!!!!
Plz explain.
I got WA.
here is my coding:

Code: Select all

int W,H,N,i,j,x1,x2,y1,y2,k,max_x,min_x,max_y,min_y;
	long long count;

	while(scanf("%d %d %d",&W,&H,&N)==3)
	{
		if(!W&&!H&&!N)
			break;
		for(i = 0; i < W; i++)
			for(j = 0; j < H; j++)
				board[i][j] = '0';
		for(k = 0; k < N; k++ )
		{
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			if(x1>x2)
			{
				max_x = x1;
				min_x = x2;
			}
			else
			{
				max_x = x2;
				min_x = x1;
			}
			if(y1>y2)
			{
				max_y = y1;
				min_y = y2;
			}
			else
			{
				max_y = y2;
				min_y = y1;
			}
			for(i = min_x; i < max_x; i++)
			{
				for(j = min_y; j < max_y; j++)
				{
					board[i][j] = '1';
				}
			}
		}
		count = 0;
		for(i = 0; i < W; i++)
			for(j = 0; j < H; j++)
				if(board[i][j]=='0')
					count++;
		if(!count)
			printf("There is no empty spots.\n");
		else if(count==1)
			printf("There is one empty spot.\n");
		else
			printf("There is %lld empty spots.\n",count);
	}

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

It will fail with this:
2 2 1
1 1 1 1
0 0 0
Output:
3

But I don't think you code can pass the sample io. And even you submit it, you should get TLE intead of WA.

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu »

hi Cho..
I do not understant!!!! Why TLE???
i changed my code:
But WA

Code: Select all

for(i = min_x-1; i < max_x; i++) 
         { 
            for(j = min_y-1; j < max_y; j++) 
            { 
               board[i][j] = '1'; 
            } 
         } 
Plz help me!!!:(

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris »

Your code Shows
There is 83470 empty spots.
Try by changing is to are :-?
Where's the "Any" key?

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu »

Thanks Solaris.................................
I got Acc..

I always follow your Advice..

:)):)):))

xintactox
New poster
Posts: 14
Joined: Thu Dec 01, 2005 3:17 pm
Location: Brazil

Here is what I did...

Post by xintactox »

I did the following algorthm to get AC:

1) Initialized an array of bool board[500][500], all true;
2)Read the sub_boards. This is an important point, because X1,Y1,X2,Y2 are NOT NECESSARILY given in that order. So you need to swap X1 and X2 if X1 > X2, and swap Y1 and Y2 if Y1 if Y1 > Y2.
3) With 2 nested loops I marked each sub_board, marking false into each position of the main board. Start at x1,y1 and go through the board until u reach x2, y2;
4) After that, just scan the board with two loops, counting the number of positions setted to true.
5) Pay attention to the format of the output.
Zero "true positions" means
There is no empty spots.
One "true position" means
There is one empty spots.
More than one "true positions" means
There are <true positions> empty spots.

And Be Happy!

altaf hussain(sust_2002)
New poster
Posts: 10
Joined: Sat Aug 19, 2006 7:23 pm
Location: bangladesh
Contact:

Post by altaf hussain(sust_2002) »

hi,
i am getting WA in that problem.
my program generates good ans for all the inputs in the board.
will any one help me.
here is my code:

Code: Select all

#include<stdio.h>
#define sz 502

int main()
{
	long arr[sz][sz],w,h,sub,s,i,j,x1,y1,x2,y2,flag=0,temp,count;
	while(scanf("%ld %ld %ld",&w,&h,&sub)==3 && (w!=0 ||h!=0 || sub!=0 ))
	{		
		for(i=1;i<=w;i++)
			for(j=1;j<=h;j++)
				arr[i][j]=1;
		count = 0;
		for(s=0;s<sub;s++)
		{
			scanf("%ld %ld %ld %ld",&x1,&y1,&x2,&y2);
			if(x1>x2)
			{
				temp =x2;
				x2=x1;
				x1=temp;
			}
			if(y1>y2)
			{
				temp =y2;
				y2=y1;
				y1=temp;
			}
			for(i=x1;i<=x2;i++)
				for(j=y1;j<=y2;j++)
					arr[i][j]=0;
		}
		for(i=1;i<=w;i++)
			for(j=1;j<=h;j++)
				if(arr[i][j]==1)
					count++;
		if(count==0)
			printf("There is no empty spots.\n");
		else if(count==1)
			printf("There is one empty spots.\n");
		else
			printf("There are %ld empty spots.\n",count);
	}
	return 0;
}

waiting for reply:

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Post by Mushfiqur Rahman »

Altaf Wrote
hi,
i am getting WA in that problem.
my program generates good ans for all the inputs in the board.
will any one help me.
here is my code:
I found your bug. The problem is in the following line

"else if(count==1)
printf("There is one empty spots.\n");


You should check the output format for output "one" .

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi »

:( i am getting tired can't find out the bug....i think my outputs are also ok.plz anyone help....

Code: Select all

cut..
Last edited by kolpobilashi on Sat Nov 11, 2006 6:01 pm, edited 1 time in total.
Sanjana

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

Try the following I/O set..

Input:

Code: Select all

500 500 0
0 0 0
Output:

Code: Select all

There are 250000 empty spots.
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

kolpobilashi
Learning poster
Posts: 54
Joined: Mon Jan 02, 2006 3:06 am
Location: Dhaka,Bangladesh
Contact:

Post by kolpobilashi »

thanx a lot JAN...didn think abt that input... :D
Sanjana

Post Reply

Return to “Volume 107 (10700-10799)”