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

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:
My code works Ok with all the test cases. But I am getting "WA".Are there any special cases??

Code: Select all

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

using namespace std;

int isCom(int x,int y)
{
if(y==0) return x;
return isCom(y,x%y);
}

int main(){
int i,j,num;
int cNums;
int nums[51];

while(cin>>num)
{
if(num==0) break;
for(i=0;i<num;i++)
cin>>nums[i];

cNums=0;

for(i=num-1;i>=0;i--)
for(j=i-1;j>=0;j--)
{
//cout<<nums[i]<<" "<<nums[j]<<" "<<isCom(nums[i],nums[j])<<endl;
if(isCom(nums[i],nums[j])==1) cNums++;
}

num=num*(num-1)/2;
//cout<<num<<"*6/"<<cNums<<endl;
if(cNums==0)
cout<<"No estimate for this data set."<<endl;
else
cout<<(sqrt((double)(num*6)/cNums))<<endl;
}
return 0;
}
``````

C8H10N4O2
Experienced poster
Posts: 137
Joined: Wed Feb 27, 2002 2:00 am
Read the question. Round to 6 places:)

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:
I fixed it. But still getting WA

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

### ACM 412

Why does this code get WA?
[c]
#include<stdio.h>
#include<math.h>
int gcd(int,int);
void main(void)
{
int num[50],n,x,y,total,check;
while(1)
{
scanf("%d",&n);
if(n==0)
break;
for(x=0;x<n;x++)
scanf("%d",&num[x]);
total=n*(n-1)/2;
check=0;
for(x=0;x<n;x++)
for(y=x+1;y<n;y++)
if(gcd(num[x],num[y])==1)
check++;
if(check==0)
printf("No estimate for this data set.\n");
else
printf("%.6lf\n",sqrt(6*(double)total/(double)check));
}
}
int gcd(int x,int y)
{
int a,b,r;
a=x,b=y;
while(1)
{
r=a%b;
if(r==0)
return a;
if(r==1)
return 1;
a=b;
b=r;
}
}
[/c]

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
I think that the cause of the WA is that in this part

[c]
for(x=0;x<n;x++)
for(y=x+1;y<n;y++)
if(gcd(num[x],num[y])==1)
check++;
[/c]

You are calculating the MCD of the last number with some UNKNOWN number. thats because the 1st for must end when x < n - 1.

Hope this can help u.

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
But when x=n-1, then y=n and it won't pass the 'y<n' expression and terminate the loop, doesn't it?

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
htl wrote:But when x=n-1, then y=n and it won't pass the 'y<n' expression and terminate the loop, doesn't it?
Yep. You are right. My mistake

Another thing that could be is that the numbers are not sorted and in your mcd function you suposse that x >= y. Maybe you are trying to calculate MCD(3, 6) and in your mcd this is not the correct answer but MCD(6, 3) it is

Hope this can help u

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan
Is it possible that the same number appears more than once? And I think the gcd() will execute extra one time if x<y.

imranul
New poster
Posts: 12
Joined: Fri Jul 19, 2002 6:28 pm
Dear htl....

I think the problem is in the gcd function....

suppose you are going to calculate gcd(3,1)
then x=3,y=1 and as a=x and b=y a=3 and b=1

So, in the loop r=a%b=3%1 (!) and gcd returns a=3
But gcd(3,1) should be 1, isn't it?
Life is like a box of Chocolates,
you never know what you're going to get...

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:

### the other way

hi,

isn't it possible to do without using a GCD funtion??? i tries in the following way and the result is WA. here is my code :

[cpp]
/*@BEGIN_OF_SOURCE_CODE*/

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

void main()
{
int N, in[55], k, flag = 0, n, tmp, res;
register int i, j, count = 0;
long double pi;

for(;;)
{
scanf("%d", &N);

if(!N)
break;

for(i = 0; i < N; i++)
scanf("%d", &in);

count = 0;
n = (N * (N-1))/2;
for(i = 0; i < N; i++)
for(j = i+1; j < N; j++)
{
flag = 0;
if(!(in%in[j]) || !(in[j]%in) || (!(in%2) && !(in[j]%2)))
flag = 1;

if(!flag)
{
for(k = 2; k <= sqrt(in); k++)
{
tmp = in%k;

if(!tmp)
{
res = in/k;

if(!(in[j]%k) || !(in[j]%res))
{
flag = 1;
break;
}
}
}
}
if(!flag)
count++;
}

if(count)
{
pi = sqrt((6 * n)/count);
printf("%.6Lf\n", pi);
}
else
printf("No estimate for this data set.\n");
}
}
/*@END_OF_SOURCE_CODE*/
[/cpp]

razibcse
New poster
Posts: 50
Joined: Mon Jul 22, 2002 3:17 am
Contact:

### What's the problem with 412?

Please someone inform me abot my coding of this problem...

Code: Select all

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

void main()
{
int t,p,n,a,b,c,nm[50],i,j,u,l;
float pis,d;
for(;;)
{
scanf("%d",&n);
if(n==0) break;
for(a=0;a<n;a++)
scanf("%d",&nm[a]);
u=0;
l=0;
for(a=0;a<(n-1);a++)
for(b=a+1;b<n;b++)
{
p=1;
l++;
if(nm[a]>nm[b])
{
t=nm[a];
nm[a]=nm[b];
nm[b]=t;
}
i=nm[a];
j=nm[b];
for(c=2;c<=i;c++)
if((i%c==0) && (j%c==0))
{
p=0;
break;
}

if(p)u++;
}
if(!u)
{
printf("No estimate for this data set.");
printf("\n");
continue;
}
d=(float)l/u;
pis=6*d;
printf("%.6f\n",sqrt(pis));
}

}
``````

MAXX^FACTOR
New poster
Posts: 7
Joined: Mon Sep 16, 2002 7:29 am
Location: EARTH.ASIA.TAIWAN.TAIPEI
Contact:

### 412

the problem insist that
answers must be rounded to six digits after the decimal point.

If the answer we have is 2.44949
what value we have to output?
2.44949 or 2.449490?

And I don't know why W.A occurs at all...

Code: Select all

``````#include <iostream.h>
#include <math.h>
#include <iomanip.h>

int GCD(int a,int b){
while(1){
if(a<b)
a^=b^=a^=b;
if(a%b==0)
return b;
a%=b;
}
}

int C(int x,int y){
int i,j,mo[100],so[100],t,t2;
if(x-y>=y)
t=x-y;
else
t=y;
for(i=0,j=2;i<x-t-1;i++,j++)
so[i]=j;
for(i=0,j=t+1;i<x-t;i++,j++)
mo[i]=j;
for(i=0;i<x-t-1;i++)
for(j=0;j<x-t;j++){
if(so[i]==1)
break;
t2=GCD(so[i],mo[j]);
so[i]/=t2;
mo[j]/=t2;
}
t2=1;
for(i=0;i<x-t;i++)
t2*=mo[i];
return t2;
}

int main()
{
int i,j,num,seq[10000],S,M,tmp;
double PI;
while(1){
cin>>num;
if(num==0)
break;
for(i=0;i<num;i++)
cin>>seq[i];
M=C(num,2);
for(i=0,S=0;i<num-1;i++)
for(j=i+1;j<num;j++)
if(GCD(seq[i],seq[j])==1)
S++;
if(S==0){
cout<<"No estimate for this data set.\n";
continue;
}
PI=(double)sqrt(6*(double)M/(double)S);
}
return 0;
}

``````

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
In your code I couldn't find a final print od PI ) It's not good ....

If you have to print output value with 6 digits after decimal point, you must print 6 DIGITS (even if it's six zeroes ) .....

Dominik

Skywalker1982
New poster
Posts: 2
Joined: Thu Oct 24, 2002 10:47 am
Location: Paris
i had the same mistake with float numbers.
when i decided to use double instead of float, it suddenly worked.

takumi
New poster
Posts: 10
Joined: Tue Dec 10, 2002 6:15 pm

### 412 WA

i don't know why my code get WA
can anybody tell me why?
[c]
#include <stdio.h>
#include <math.h>
int test ( int a, int b ) {
for( ; ; ) {
if ( a < b )
a^=b^=a^=b;
if ( a % b == 0 )
return b;
a %= b;
}
}
int main()
{
int input, a[100], i, j, counter = 0, total;
double temp, temp2;

for ( ; ; ) {
scanf("%d", &input);
counter = 0;
if ( input == 0 )
break;

for ( i = 0; i < input; i++ ) {
scanf("%d", &a);
}
total = input * ( input - 1 ) / 2;

for ( i = 0; i < input - 1 ; i++ ) {
for ( j = i+1; j < input; j++ ) {
if ( a == a[j] )
break;
if ( test( a,a[j] ) == 1 ){
counter++;
}
}
}
if ( counter == 0 ){
printf("No estimate for this data set.\n");
continue;
}

temp = 6 /( double)counter;
temp2 = sqrt(total * temp);
printf("%.6f\n", temp2);
}
return 0;
}[/c]
thanks..