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

Post by joydip »

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)
please help

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan »

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:

Post by UFP2161 »

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:

Post by UFP2161 »

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

Post by Joseph Kurniawan »

Yes, yes my mistake. :oops: :oops: :oops:
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

Post by Joseph Kurniawan »

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

Post by joydip »

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

Post by _.B._ »

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?.
Thanks in advance.
bernardolg@cantv.net
_.

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

356 - Square Pegs And Round Holes

Post by JiaYun »

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;
radiusp2 -= 0.5;
radiusp2 *= radiusp2;

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:

Post by UFP2161 »

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.

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

Can be easier

Post by Mohammad Mahmudur Rahman »

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

Post by JiaYun »

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.

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

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

Post by dovier_antonio »

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;

}

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

Post by Mohammad Mahmudur Rahman »

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

Post by neno_uci »

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)

...??? :roll:

Thanx in advance,

Yandry.

Post Reply

Return to “Volume 3 (300-399)”