## 412 - Pi

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

Moderator: Board moderators

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
Random Input:
6
924
11365
5809
10130
14903
28986
0
Should output:
3.000000
But you output:
3.464102

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:
thanks a lot UFP2161!!!!!(I don't understand your nick)
I finally got AC!!
I just forgot some stupid part of the problem!! Thanks again!!!!
wish you good luck!!!
byee

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
If you've ever watched Star Trek, you might get it.. Yes, I know it has absolutely nothing to do w/ the picture.

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
tried all those..still WA can anyone give me critcal IO for this one
if u can think of it .. u can do it in software.

RustB
New poster
Posts: 16
Joined: Mon Jun 14, 2004 5:08 pm
Change your gcd function to this

Code: Select all

``````int gcd(int p,int q)
{
if (q > p) return(gcd(q,p));
if (q == 0) return(p);
return( gcd(q, p % q) );
}``````
Change the call accordingly.
Then, remove the check for repeated numbers.
Further, get rid of the extra variables x and x and change 6 to 6.0
Then, remove the various increments for total, just change it to
total=n*(n-1)/2;
*whew* That should do it

Rolando_de_Gilead
New poster
Posts: 3
Joined: Thu Feb 24, 2005 1:32 am

### Help 412

Someone can help me? I can't see where is the problem but the systems says WA.
-------------------------------------------------------------------------------------

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

typedef struct {
int dim;
int v;
} set;

int readinput (set f[]) {
int i=0, j=0;

while(f.dim!=0) {

scanf("%d",&f.dim);

if (f.dim!=0) {

for (j=0;j<f.dim;j++) {

scanf("%d",&f.v[j]);}

i++; }}

return i;}

int cmp (int a, int b) {

int i; double r=0;

if (a>b && b!=1) {

for (i=2;i<=b;i++) {

if (a%i==0 && b%i==0 ) {

r= 1; } }
}

else if (b>a && a!=1) {

for (i=2;i<=a;i++) {

if (a%i==0 && b%i==0 ) {

r= 1; } }
}

else if (a==b ) {

r= 1; }

return r;
}

double sum (int n) {

int i, r=0;
for (i=1; i<n;i++) {
r=r+i; }
return r; }

void main() {
int i, max, j, k;
double r2;
set f;
double count;
double r;
max = readinput (f);

for (i=0; i<max; i++) {
count=0;

for (j=0; j<f.dim; j++) {

for (k=0; k<f.dim; k++) {

if (cmp( f.v[j], f.v[k]) ==0 ){

count [i] ++; } }

}
if (count [i]>0) {
r = sqrt ( 6*(2*sum(f[i].dim)) / (count[i]) );

printf ("%.6lf\n", r); }
else
printf ("No estimate for this data set.\n") ;
}

}

--------------------------------------------------------------------------------------
Thanks

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

### Hi Rolando_de_Gilead !!!!

Tries by this way:

int gcd(int a, int b) {
return (a % b == 0) ? b : gcd(b, a % b);
}
Last edited by dovier_antonio on Fri Feb 03, 2012 9:56 am, edited 2 times in total.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

### Again

Hi,
Please dont post your AC code. You have post lots of your ACC code which is not a good work.
Last edited by Raj Ariyan on Thu Mar 17, 2005 3:23 pm, edited 1 time in total.
Some Love Stories Live Forever ....

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### sample I/O

Some sample I/O for anyone who might be interested.

Hope it will be helpful for someone.

INPUT

Code: Select all

``````5
2
3
4
5
6
2
13
39
3
4
5
6
22
2
4
5
6
90
99
101
102
103
104
105
106
1001
1002
1003
1004
10005
10008
10009
20001
30001
30003
9
32767
32000
16001
15050
1001
1002
100
99
101
11
9999
10001
20000
185
193
202
303
304
305
555
551
5
14
222
770
552
1110
0``````

OUTPUT

Code: Select all

``````3.162278
No estimate for this data set.
3.000000
3.113247
2.939388
2.872281
No estimate for this data set.``````

Yu Fan
New poster
Posts: 26
Joined: Thu Nov 13, 2003 3:52 am

### a strange question about 412

in the problem we have to estimate the value of pi by evaluating the number of pairs of numbers without common factor.

i computed the pairs and use the fomula problem provides to produce the answer, but i always get WA. my value is like this:

sqrt((3*n*(n+1)/p)),

the n is the size of input and p is the number of pairs.
finally, i eliminate the outer parenthesizes in sqrt() like this

sqrt(3*n*(n+1)/p),

and got AC.
i don't understand why this got AC but the former didn't?
somebody help?

Hector_Hsu
New poster
Posts: 13
Joined: Thu May 26, 2005 1:16 pm

### 412 - Pi

Here is my code

Will some function like sqrt() make errors or I miss any part here?

Please tell me , thanks a lot. ^^

Code: Select all

``````#include<cstdio>
#include<cmath>
using namespace std;
int prime=0;
int judge(int a,int b);
int main(void)
{
int N,n;
double pi;
while(scanf("%d",&N)==1)
{
if(N==0)
return 0;

for(int j=0;j<N;j++)
{
scanf("%d",&n[j]);
}
for(int k=0;k<N-1;k++)
{
for(int l=k+1;l<N;l++)
{
judge(n[k],n[l]);
}
}
if(prime==0)
{
printf("No estimate for this data set.\n");
}
else
{
pi = (double)sqrt(3.0*N*(N-1)/(double)(prime+0.0));
printf("%.6lf\n",pi);
}

for(int i=0;i<50;i++)
{
n[i] = 0;
}
prime = 0;
pi = 0;
}
}
int judge(int a,int b)
{
int c,d;
if(a==b)
{
return 0;
}
else if(a>=b)
{
c = a;
d = b;
}
else if(b>a)
{
c = b;
d = a;
}

int r = c%d;
if(r==1)
{
prime++;
return 0;
}
else if(r==0)
{
return 0;
}
else
{
c = d;
d = r;
judge(c,d);
}
}

``````

Hector_Hsu
New poster
Posts: 13
Joined: Thu May 26, 2005 1:16 pm
Sorry,

the title is find the "bug" , not the "big" |||

/________________________\

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
I did it like this

Code: Select all

``````double pairs = n*(n-1)/2;
double pi = sqrt(6*pairs/count);``````
where pairs are the maximum quantity of pairs and count is amount;) of pairs in which greatest common divisor is 1

and your function may be done much easier(actually I dont understand what you've tried to do there, it could be as well as void, couse it returns value to nothin', but your prog succeded in/out, so nevermind)

Code: Select all

``````int judge(int a,int b) // gcd algo...
{
while(a != b) if(a > b) a -= b; else b -= a;
return(a);
}``````
(your "prime" is my "count")

Regards
keep it real!

jaracz
Learning poster
Posts: 79
Joined: Sun Sep 05, 2004 3:54 pm
Location: Poland
and sqrt() in <cmath> sometimes calculate incorrect answers(dont know why),so you'd better not to declare "namespace" standard, just change it to <math.h> instead of <cmath> and remove "using namespace std;"
(stdio also)
keep it real!

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:

### 419 PI getting TLE

why TLE plz help,,,

time limit exceeded

Code: Select all

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

int _fact(long int a,long int b)
{
long int i,j;
for(i=2;i<=a || i<=b;i++)
{
if(a%i==0 && b%i==0)
return 1;
}
return 0;
}

int main(void)
{

long int N,count=0,total=0,i,j;
long int arr;
while(1)
{
scanf("%ld",&N);
if(N==0)
break;
for(i=0;i<N;i++)
scanf("%ld",&arr[i]);
for(i=0;i<N-1;i++)
{
for(j=i+1;j<N;j++)
{
total++;
if(!_fact(arr[i],arr[j]))
count++;
}
}
/*	       	printf("%ld %ld\n",total,count);    */
if(count==0)
printf("No estimate for this data set.\n");
else
printf("%.6f\n",sqrt((total*6)/count));
count=0;
total=0;
}
return 0;
}

``````
i itried all the inputs pz help....