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

Post Reply
ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

Post by ram » Wed Mar 27, 2002 2:40 am

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
Location: Pasadena, CA

Post by C8H10N4O2 » Wed Mar 27, 2002 2:17 pm

Read the question. Round to 6 places:)

ram
New poster
Posts: 30
Joined: Wed Mar 06, 2002 2:00 am
Contact:

Post by ram » Wed Mar 27, 2002 9:25 pm

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

Post by htl » Wed Jul 03, 2002 1:17 pm

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

Post by ithamar » Wed Jul 03, 2002 6:06 pm

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

Post by htl » Wed Jul 03, 2002 6:39 pm

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

Post by ithamar » Wed Jul 03, 2002 8:37 pm

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

Post by htl » Thu Jul 04, 2002 4:57 am

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
Location: Bangladesh

Post by imranul » Sun Jul 28, 2002 5:01 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 :o
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
Location: Dhaka, Bangladesh
Contact:

the other way

Post by Shahid » Fri Aug 30, 2002 11:42 pm

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
Location: SUST,BANGLADESH
Contact:

What's the problem with 412?

Post by razibcse » Mon Sep 16, 2002 8:19 pm

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));
}

}

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

412

Post by MAXX^FACTOR » Wed Oct 09, 2002 3:49 pm

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:

Post by Dominik Michniewski » Thu Oct 10, 2002 8:07 am

In your code I couldn't find a final print od PI :-)) It's not good ....
Answer to your question:

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

Post by Skywalker1982 » Mon Oct 28, 2002 1:13 pm

i had the same mistake with float numbers.
when i decided to use double instead of float, it suddenly worked.

:roll:

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

412 WA

Post by takumi » Sat Dec 21, 2002 11:41 am

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

Post Reply

Return to “Volume 4 (400-499)”