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

User avatar
SeaViperz
New poster
Posts: 4
Joined: Mon Dec 30, 2002 9:44 am

412 Runtime Error (SIGFPE)

Post by 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]
*****SeaViperz*****
Draw your fangs and let's duel.
For my poison serves forever as my fuel!

supermin
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Post by 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
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by 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
New poster
Posts: 3
Joined: Sun Mar 02, 2003 5:25 am

problem 412 get WA

Post by 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
New poster
Posts: 14
Joined: Tue May 06, 2003 11:04 pm
Location: Portugal
Contact:

412 WA.. why??

Post by 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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by 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......
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Sayutee
New poster
Posts: 9
Joined: Wed Jun 04, 2003 7:50 am
Location: Bangladesh

412 Is there any special case

Post by Sayutee »

Is there any special case in 412?

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

any trick in 412 , pliiiiiiiizzzzzzzzzzzzz help

Post by 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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

FCS
New poster
Posts: 9
Joined: Mon Oct 15, 2001 2:00 am

Post by 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
New poster
Posts: 9
Joined: Mon Oct 15, 2001 2:00 am

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

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad »

thanx got it ac.
Bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

37951ZR
New poster
Posts: 2
Joined: Mon Nov 03, 2003 2:31 pm
Location: Japanese

please help me in 412 prob.

Post by 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]

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by 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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by 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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

412 -PI- wrong answer

Post by jagadish »

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

[c] // thanks got Ac [/c]
Last edited by jagadish on Mon Jul 26, 2004 6:35 am, edited 1 time in total.
if u can think of it .. u can do it in software.

Post Reply

Return to “Volume 4 (400-499)”