412 - Pi

[SeaViperz]

I got Runtime Error when i submitted. Can someone help me? thx!

[cpp]#include <stdio.h>
#include <math.h>
int main(){
int setsize,arr[50]={0},i,j,k,search,tmp,pairs;
while(scanf("%d",&setsize)==1){
if(setsize==0) break;
for(i=0;i<setsize;i++) scanf("%d",&arr);
search=0;
while(search==0){
search=1;
for(i=0;i<(setsize-1);i++){
if(arr>arr[i+1]){
tmp=arr;
arr=arr[i+1];
arr[i+1]=tmp;
search=0;
}
}
}
search=0;
pairs=(setsize*(setsize-1))/2;
for(i=0;i<(setsize-1);i++){
for(j=i;j<setsize;j++){
tmp=0;
for(k=2;k<=arr;k++){
if(arr%k==0 && arr[j]%k==0) tmp++;
}
if(tmp==0) search++;
}
}
if(search>0) printf("%.6f\n",sqrt(pairs/(search/6)));
else printf("No estimate for this data set.\n");
}
return 0;
}[/cpp]

[supermin]

Try this case:
3
3 6 8

pairs:3
search:1

And take a look at your source code:

Code: Select all

if(search>0) printf("%.6f\n",sqrt(pairs/(search/6)));

search/6 => 0
and pairs/0=> Runtime Error

and be careful about sqrt => return "double".
[/code]

[rjhadley]

Since the largest value in the input set is less than 32768, you can use Eratosthenes's Sieve to create a list of all the prime divisors for all possible values. (There will be at most 6 unique prime divisors, so you can use less than 1 MB of memory for this structure, which will be an array of lists). Then simply consider each input pair and compare their lists. Building this data structure should only take a fraction of a second, indexing it to find each list is constant time, and comparing 2 lists for a common member can be done in at most 6 comparisons (think merge sort), so this will be fast, but a bit complicated.

Note, however, that you don't really care about what the common factor is, just whether or not one exists, so it is much simpler to consider the greatest common divisor for each input pair. A gcd can be calculated in logarithmic time, so this method will also be fast.

[ccpz]

[cpp]
#include <iostream.h>
#include <math.h>
#include <iomanip.h>

int main()
{
int dn=0;
int data[50]={0};
int a=0,b=0,temp=0;
int total=0,ncf=0;
while(1)
{
total=0;
ncf=0;
cin>>n;
if(n==0) break;
for(int i=0;i<n;i++)
{
cin>>data;
for(int j=0;j<i;j++)
{
total++;
a=data>=data[j]?data:data[j];
b=data<=data[j]?data:data[j];
while(b)
{
a-=b*((int)a/b);
temp=a;
a=b;
b=temp;
if(b==1) {ncf++;break;}
}
}
}
if(ncf==0) cout<<"No estimate for this data set."<<endl;
else
cout<<setprecision(7)<<setiosflags(ios::showpoint)<<sqrt(6*total/ncf)<<endl;
}
return 0;
}
[/cpp]
what`s the problem?

[neowarez]

Can somone help me with this... I have WA ... why??

[pascal]

Program Acm_412(Input, Output);

Function Verificou(X, Y: Integer): Boolean;
Var
I: Integer;
Begin
Verificou:=True;
If (Y Mod (Y Div 2)=0) And (X Mod (Y Div 2)=0) And (Y Div 2<>1) Then
Verificou:=False
Else
For I:=2 To Trunc(Sqrt(Y)) Do
If (Y Mod I=0) And (X Mod I=0) Then
Begin
Verificou:=False;
Break;
End;
End;

Procedure GetData;
Var
N, I, Temp, J, Conta, Casos: Integer;
Verifica: Boolean;
Numeros: Array[1..50] Of Integer;
Begin
Repeat
ReadLn(Input, N);
If N=0 Then
Break;
Casos:=0;
Conta:=0;
For I:=1 To N Do
ReadLn(Input, Numeros);
Repeat
Verifica:=True;
For I:=2 To N Do
If Numeros[I-1]>Numeros Then
Begin
Temp:=Numeros;
Numeros:=Numeros[I-1];
Numeros[I-1]:=Temp;
Verifica:=False;
End;
Until Verifica;
For I:=1 To N-1 Do
For J:=I+1 To N Do
Begin
Inc(Casos);
If Not (Numeros[J] Mod Numeros = 0) Then
If Verificou(Numeros[J], Numeros) Then
Inc(Conta);
End;
If Conta=0 Then
Begin
WriteLn(Output, 'No estimate for this data set.');
End
Else
Begin
WriteLn(Output, Sqrt((Casos*6)/Conta):2:6);
End;
Until N=0;
End;

BEGIN
GetData;
END.
[/pascal]

Thanks ..

[Observer]

Try this set of data:

• 3
  10
  15
  25
  4
  28
  21
  35
  14
  0

Your answer:
4.242641
3.464102

Furthermore, your algorithm is way too slow......

[Sayutee]

Is there any special case in 412?

[Riyad]

hi , i am having wa at 412 all the time . can u provide me with some test input output . i think i covered everything , and did not seem to miss , did i miss some thing ????????/ plizzzzzzz help . wagerly waiting for u r help .
here is my code :

Code: Select all

#include<stdio.h>
#include<math.h>
int input[52];
int index ;
int gcd(int a , int b){
	if(b==0)
		return a ;
	else 
		return gcd(b,a%b);

}
void calculate(){

	double count=0 , total=0,result;
	register int i , j,flag;
	for(i=0;i<index;i++){
	           for(j=i+1;j<index;j++){
		total++;
			if(input[i]>input[j]){
				
				flag=gcd(input[j],input[i]);
			}
			else if(input[i]<input[j]){
				
				flag=gcd(input[i],input[j]);

			}
			if(flag==1){
				
				count++;
			}
			else 
				continue;
			
		}
		
		
	}

	if(count==0){
	
		printf("No estimate for this data set.\n");
	}

	else{
	
		
		result= (total*6)/count;
		result=sqrt(result);
		printf("%.6lf\n",result);
	
	}
}




int main(){

	register int count;
	
	freopen("input.in","rt",stdin);
	
	while(scanf("%d",&count)==1){
		if(count==0)
			break;
		for(index=0;index<count;index++){
		
			scanf("%d",&input[index]);
		}

		calculate();
	
	}
	
	return 0;
}

thanx in advance
Bye
Riyad

[FCS]

did you remember to take out the freopen when you submitted?

besides, there are nC2 = n(n-1)/2 unique pairs for a set of n numbers. when you increment your total counter, you do not check whether i=j for this is not considered.

on a side note, you do not need to test input>input[j] for your gcd will automatically take care of this.

[FCS]

did you remember to take out the freopen when you submitted?

besides, there are nC2 = n(n-1)/2 unique pairs for a set of n numbers. when you increment your total counter, you do not check whether i=j for this is not considered.

on a side note, you do not need to test input>input[j] for your gcd will automatically take care of this.

[Riyad]

thanx got it ac.
Bye
Riyad

[37951ZR]

I cannot find what is worng.
when I imput all of the sample data,
It worked correctly...
but why online judge system never accept my code?

please tell me the reason.

[code][c]
#include <stdio.h>
#include <math.h>

int check(int a, int b);

int main(void){

int i, j, count, num[50], n;
double pi;

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

if(n == 0){
break;
}

count = 0;

for(i = 0 ; i < n ; i++){
scanf("%d", &num[i]);
}

i = 0;

while(i < n){
for(j = i + 1 ; j < n ; j++){
count += check(num[i], num[j]);
}
i++;
}

if(count == 0){
printf("No estimate for this data set.\n");
}
else{
pi = sqrt(6 * n * (n - 1) / 2 / count);

printf("%f\n", pi);
}
}

return 0;
}

int check(int a, int b){

int tmp;

if(a < b){
tmp = a;
a = b;
b = tmp;
}

while(a % b != 0){

tmp = a % b;
a = b;
b = tmp;
}

if(b == 1){
return 1;
}
else{
return 0;
}

}


[/c][/code]

[Riyad]

hey try this simple algo .

[c]
if(gcd(num,num[j])==1)
count++;
else
continue;
...................
...................
..................
if(count==0)
printf("No Es.......");
else
calculate the Value of Pie
[/c]

Best Regards
Hope u ll get Ac .
Riyad

[Riyad]

hey try this simple algo .

[c]
if(gcd(num,num[j])==1)
count++;
else
continue;
...................
...................
..................
if(count==0)
printf("No Es.......");
else
calculate the Value of Pie
[/c]

Best Regards
Hope u ll get Ac .
Riyad

[jagadish]

here is the code..
i tried it with the duplicates retained too...

[c] // thanks got Ac [/c]