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

joydip
New poster
Posts: 4
Joined: Tue Sep 23, 2003 2:33 pm

### Help...........356 WA

I think I have problem creating formula
My formula is:
Cells contain segments of the circle is =8*n-4
And
Cells completely contained in the circle is=m=2*n*(n-1)

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
The first formula is okay. But the second?? it's very far from correct. The failure will occur when n>=5. For n=5, the cells completely contained in the circles are 76, not 40.
I solved this prob using looping method since my geometry isn't so good.
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
If n = 5, then
a) 8*n-4 = 36 [squares w/ segments]
b) 4*n*n = 100 [number of squares]

How can 36+76 > 100 cells? I counted 52 w/ a graphing calculator.

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
There should be a newline between blocks. You have an extra newline at the end of your output.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
Yes, yes my mistake.
76 is the answer for n = 6. For n = 5, you're right, the number of cells is 52. Thnx UFP2161!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
Well, as far as I know, extra blank lines commonly will only cause P.E.
I suggest not to mix the non floating-point data type (int & long) with floating-point data type (float, double and long double). The method seems alright to me. Just change the int and long type with float or double. As for the extra blank lines, you may use:

[cpp]
if (line) printf("\n");
line=1;
touches_circle = 8*n-4;
[/cpp]

Good luck!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

joydip
New poster
Posts: 4
Joined: Tue Sep 23, 2003 2:33 pm
Thanks I got it and make it A.c

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

### Formula?.

Greetings!.
I solved problem 356 (http://online-judge.uva.es/cgi-bin/Onli ... Info:42085), but I read there's some formula for it.
Will any of you please e-mail me that formula and why it works?.
bernardolg@cantv.net
_.

JiaYun
New poster
Posts: 12
Joined: Thu May 01, 2003 4:27 am

### 356 - Square Pegs And Round Holes

My program has the same output with an AC code from n = 1 to n = 150, but I can't understand why it got WA.

[cpp]#include <iostream>

using namespace std;

int
main(void)
{
int n;
bool first = true;
while (cin >> n) {
if (!first)
cout << endl;
first = false;

double radiusp2 = n;

int segment = 0;
int complete = 0;

for (double i = 0; i < n; i++) {
for (double j = 0; j < n; j++) {
if ( (i+1)*(i+1) + (j+1)*(j+1) < radiusp2 ) {
complete++;
} else if ( i*i + j*j < radiusp2 ) {
segment++;
}
}
}

cout << "In the case n = " << n << ", " << segment * 4
<< " cells contain segments of the circle." << endl
<< "There are " << complete * 4 << " cells completely contained in the circle." << endl;
}

return 0;
}[/cpp]

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Are you mailing your code in? If so, the really long cout code might be getting broken off at a bad place which would cause a WA.

If so, try submitting it using the online form. Otherwise, I don't know what could be wrong. Matches my AC code as well.

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

### Can be easier

You can solve this problem in an easier way too. Do some pen & paper works for the first few values of n i.e. n = 1,2,3,4... & you will find 2 formula refer to Concrete Math (Knuth) , floor & ceiling functions chapter.
You should never take more than you give in the circle of life.

JiaYun
New poster
Posts: 12
Joined: Thu May 01, 2003 4:27 am
to UFP2161:
I modified the cout code and got AC now, thank you!

to Mohammad Mahmudur Rahman:
Thanks for your suggestion, I will try to find the formulas.

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### Help me... I have WA!!!!

My solution for the problem 356 is :

#include <stdio.h>

int main() {

int n;

while (scanf("%d", &n) != EOF) {

printf("In the case n = %d, %d cells contain segments of the circle.\n", n, 8 * n - 4);
printf("There are %d cells completely contained in the circle.\n\n", 2 * n * (n - 1));

}

return 0;

}

Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET
You need to use long int for calculation. Otherwise your program will fail to inputs greater than some 104 or 105, I guess.
& also, why not mentioning the problem number & name in the topic? Surely it increases the chance of getting a reply.
You should never take more than you give in the circle of life.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Are these formulas ok...???

cells with segments of the circle = 4 * (2 * n - 1) = 8 * n - 4
cells completely contained in the circle = 2 * n * (n - 1)

...???