356 - Square Pegs And Round Holes

[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]

Positive integer means > 0

[seolv]

I have a same trouble as you

All output appear right.

but it's not accepted

is there something tricky?

[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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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