OJ Board

Posted: **Wed Jan 01, 2003 5:27 am**

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]

Posted: **Sat Jan 11, 2003 5:07 am**

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]

Posted: **Sun Jan 26, 2003 6:53 pm**

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.

Posted: **Fri May 09, 2003 6:46 am**

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

Posted: **Sun May 11, 2003 8:39 pm**

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

Posted: **Mon May 12, 2003 4:21 am**

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

Posted: **Fri Jun 06, 2003 3:41 pm**

Is there any special case in 412?

Posted: **Tue Sep 16, 2003 7:05 pm**

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

Posted: **Sat Sep 20, 2003 6:25 am**

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.

Posted: **Sat Sep 20, 2003 6:32 am**

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.

Posted: **Sat Sep 20, 2003 2:35 pm**

thanx got it ac.
Bye
Riyad

Posted: **Mon Nov 03, 2003 2:45 pm**

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]

Posted: **Mon Nov 10, 2003 4:45 am**

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

Posted: **Mon Nov 10, 2003 4:46 am**

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

Posted: **Fri Feb 20, 2004 8:05 pm**

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

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

OJ Board

412 - Pi

412 Runtime Error (SIGFPE)

problem 412 get WA

412 WA.. why??

412 Is there any special case

any trick in 412 , pliiiiiiiizzzzzzzzzzzzz help

please help me in 412 prob.

412 -PI- wrong answer