356 - Square Pegs And Round Holes

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

Moderator: Board moderators

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang »

Is there any trick in this problem? Can there be 0 as input? If so, what is the output? I have checked my program with the test cases at Ilham's page, and it is all correct except for case n = 0, which Ilham's output is wrong in my opinion.

FCS
New poster
Posts: 9
Joined: Mon Oct 15, 2001 2:00 am

Post by FCS »

Positive integer means > 0

seolv
New poster
Posts: 11
Joined: Wed Oct 24, 2001 2:00 am

Post by seolv »

I have a same trouble as you

All output appear right.

but it's not accepted

is there something tricky?

junyu
New poster
Posts: 3
Joined: Wed Mar 06, 2002 2:00 am

Post by junyu »

I don't know what's wrong with your program.
But I suggest that you can think the problem
in another way.
Try to consider only 1/4 graph.
Then to check each grid,if the distance from left_up point to original point is larger
than (2*n-1)/2,the grid is out of circle.
Else if the distance form right_down point
to original point is less than (2*n-2)/2,
the grid is in the circle.
Finally,the grid covered by circle is determined by n*n-(#of in circle)-(# of out circle)

junyu
New poster
Posts: 3
Joined: Wed Mar 06, 2002 2:00 am

Post by junyu »

I don't know what's wrong with your program.
But I suggest that you can think the problem
in another way.
Try to consider only 1/4 graph.
Then to check each grid,if the distance from left_up point to original point is larger
than (2*n-1)/2,the grid is out of circle.
Else if the distance form right_down point
to original point is less than (2*n-1)/2,
the grid is in the circle.
Finally,the grid covered by circle is determined by n*n-(#of in circle)-(# of out circle)

TaChung
New poster
Posts: 2
Joined: Wed Mar 06, 2002 2:00 am

Post by TaChung »

I don't know what is my program's wrong...

/* @JUDGE_ID: 14991MR 356 C "Dynamic Programming" */

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

int main()
{
float radius ;
int com , seg , n , x , y ;/*, y1;*/

while(scanf("%d" , &n)!=EOF) {
com = 0;
seg = 0;

radius = (float)(2*n-1)/2;

if (n==0)
seg = 0;
else
seg = (2*n-1)*4;

for (x=0 ; (x+1)<radius ; x++) {
y = (int)sqrt(radius * radius - (x+1) * (x+1));
com = com + y;

/* y1 = (int)sqrt(radius * radius - x * x);*/
/* seg = seg + (y1-y+1);*/
}

com = 4 * com;
/*seg = 4 * seg;*/

printf("In the case n = %d, %d cells contain segments of the circle.n" , n , seg);

printf("There are %d cells completely contained in the circle.nn" , com);

}
}

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang »

I'm not exactly sure what you mean, so I will post my method here.

First, my program also only considers 1/4 of a circle, and it happens to be the top-right quarter. For every square, I check the bottom-left and top-right points. If both are in the circle then the square is in the circle, if only the bottom-left then this square is a segment of the circle, else it is not in the circle. Then I multiply my results by 4 to get final results.

As said before, my program gives exactly the same output as an AC program. Can anyone spot any mistake?

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

TaChung: One mistake in your program is that you claim to use "Dynamic Programming". Although this will not change your result, this wrong comment is soooo annoying in the ranklists, especially when you don't actually used DP.

Please, everybody: If you write a comment, make sure it makes sense. Plus: don't give away the solution.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

Of course it's better (and feasible in this case) to do it without a hint, but here is one:

In the case n = 150, 1196 cells contain segments of the circle.
There are 69660 cells completely contained in the circle.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

TaChung: Sorry, that example won't help you much. Your program computes that correctly. In fact, your program computes the same as mine for all inputs.

But it's even better: I just got your program accepted without changing it!

Why do people continue posting their correct solutions here when there's nothing wrong? Could you please resubmit it and look at the "Program Received" mail from them? Is that program identical to the one you sent? I'd like to know where this problem comes from.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Post by shahriar_manzoor »

I think Tachung has problems with his mailer setting. So increase your line breaking limit or split the output printf into more than one printf.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann »

Youre right, that's probably it. Seems like many people have trouble with their mail programs.

Btw, third alternative:

Code: Select all

    printf( "In the case n = %d, %d cells "
            "contain segments of the circle.n", n, seg );

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang »

My program is definitely wrong. This is the code:

Code: Select all

@begin_of_source_code
{@JUDGE_ID: XXXXXX  356  PASCAL}
program square_pegs_and_round_holes(input,output);
const
epsilon : real = 0.0000001;
type
Tinteger = integer;
Tstore = record hal, ful : Tinteger end;
var
num, i, j, half, full : Tinteger;
store : array[0..150] of Tstore;
(*********************************)
function in_circle(x, y : Tinteger) : Boolean;
var
len, dist : real;
begin
dist := sqrt(x * x + y * y);
len := (2 * num - 1) / 2;
if (dist - len > epsilon) then in_circle := FALSE else in_circle := TRUE;
end;
(*************************)
begin
for num := 1 to 150 do begin
  full := 0;
  half := 0;

  for i := 0 to num - 1 do
    for j := 0 to num - 1 do begin
      if (in_circle(i, j) = TRUE) then begin
        if (in_circle(i + 1, j + 1) = TRUE) then full := full + 1
        else half := half + 1;
      end;
    end;

  full := full * 4;
  half := half * 4;

  store[num].ful := full;
  store[num].hal := half;
end;

while not eof(input) do begin
  readln(num);
  if (num <= 0) OR (num > 150) then while TRUE do writeln('CRAP');

  writeln('In the case n = ',num,', ',store[num].hal,' cells contain segments of the circle.');
  writeln('There are ',store[num].ful,' cells completely contained in the circle.');
  if not eof(input) then writeln;
end;
end.
@end_of_source_code
Can anyone find any problems?

<font size=-1>[ This Message was edited by: junjieliang on 2002-03-16 14:13 ]</font>

Ashok
New poster
Posts: 1
Joined: Sun Jul 14, 2002 8:02 am
Location: Bangladesh

356,where is the wrong

Post by Ashok »

can u pls point out the wrong .here is my source code,I dont know why it is wrong,help me please

#include<stdio.h>
#include<math.h>
void main()
{
int n,touches_circle,k;
long a=0,b=0;
double radius,temp;
while(scanf("%d",&n)==1)
{
touches_circle = 8*n-4;
if(touches_circle<0)touches_circle=0;
radius=n-0.5;
radius=radius*radius;
for(k=1;k<n;k++)
{
temp=radius-k*k;
temp=sqrt(temp);
a=(long)temp;
b=b+a;
}
b=4*b;
printf("In the case n = %d, %d cells contain segments of the circle.\n",n,touches_circle);
printf("There are %ld cells completely contained in the circle.\n\n",b);
b=0;
}

}
[cpp][/cpp]

NONAME_SUST
New poster
Posts: 8
Joined: Tue Jul 23, 2002 9:15 am

SAME PROBLEM

Post by NONAME_SUST »

Hi,
I have solved the problem in the following way.. It satisfies the example input and output but generate a wrong answer when I submit it.

Can u say what's the wrong here

#include<stdio.h>

void main(){
long n,com_in,out;
while(scanf("%ld",&n)==1){
com_in =2*n*(n-1);
out = 4*(2*n-1);
printf("In the case n = %ld,",n);
printf(" %ld cells contain ",out);
printf("segments of the circle.\n");
printf("There are %ld cells ",com_in);
printf("completely contained in the circle.\n\n");
}
}

/*@END_OF_SOURCE_CODE*/
HEY WANT TO GET SOL.TRY ON http://www.uvexam.zzn.com from 1st September

Post Reply

Return to “Volume 3 (300-399)”