Page 2 of 3
Posted: Tue Aug 09, 2005 11:18 am
by mf
Some simple cases:
Code: Select all
5
1
0
1
-1
1
1
1
-555.5559
1
555.5559
Output:
Code: Select all
Case #1: 0.000
Case #2: -1.000
Case #3: 1.000
Case #4: -555.556
Case #5: 555.556
Input generator:
Code: Select all
#include <stdio.h>
#include <stdlib.h>
unsigned r = 123456; int T = 20, a[65536], i, n;
int R(unsigned m) { r = r * 1812433253 + 1; return (r >> 4) % m; }
int C(const void *p, const void *q) { return (*(int *)q - *(int *)p); }
int main() {
for(printf("%d\n",T);T--;) {
for(printf("%d\n",n=1+R(50000)),i=n;i--;)a[i]=R(2000000)-1000000;
qsort(a,n,sizeof(a[0]),&C);
while(n--)printf("%s%d.%.3d%c",(a[n]<0)?"-":"",abs(a[n]/1000),abs(a[n])%1000,n?' ':'\n');
}
return 0;
}
Output from my first program (uses long double, and binomial identities), to 10 decimal places:
Code: Select all
Case #1: -5.1383833008
Case #2: -7.5212485514
Case #3: -5.4755549144
Case #4: -22.0564143198
Case #5: -14.7081045826
Case #6: 2.1670052646
Case #7: -2.8371366794
Case #8: -64.6690314518
Case #9: -2.8069371800
Case #10: -6.3711452901
Case #11: -0.1070479581
Case #12: 9.9847964413
Case #13: -4.9372260331
Case #14: -5.3130527357
Case #15: 5.2135842771
Case #16: 3.0378944456
Case #17: 5.2404084182
Case #18: -8.1282949430
Case #19: 1.4519873897
Case #20: 0.7415996176
And here's output from another accepted program, which uses double, and approximation by logarithms:
Code: Select all
Case #1: -5.1383659629
Case #2: -7.5212348259
Case #3: -5.4755465033
Case #4: -22.0564002421
Case #5: -14.7080626664
Case #6: 2.1670022202
Case #7: -2.8371272209
Case #8: -64.6689788484
Case #9: -2.8069336197
Case #10: -6.3711423685
Case #11: -0.1070486464
Case #12: 9.9847738878
Case #13: -4.9372089784
Case #14: -5.3130318235
Case #15: 5.2135703089
Case #16: 3.0378827475
Case #17: 5.2403945592
Case #18: -8.1282549736
Case #19: 1.4519816612
Case #20: 0.7415916422
If you get similar answers and still WA, post you code here.
Posted: Tue Aug 09, 2005 11:41 am
by windows2k
mf wrote:Output from my first program (uses long double, and binomial identities), to 10 decimal places:
If you get similar answers and still WA, post you code here.
I also use long double , get the same result as yours.
Here is my code
Posted: Tue Aug 09, 2005 12:01 pm
by mf
I've sent you modified code by private message.
Posted: Fri Aug 19, 2005 10:42 am
by sunnycare
hi every kind man
i have taken your advisers.
but got WA...
it has spoiled me whole day....
so i need your help .....
my prog is here..
Code: Select all
//10883 Supermean
#include <cstdio>
#include <cmath>
//#include <ctime>
using namespace std;
double a[50000];
long test,tst,n,i,j;
void f()
{
double nCr;
long i;
double s=0;
double z=(n-1)*(double)log10((double)2);
nCr=0;
double tmp=log10(a[0])-z;
if(tmp>-7)
s+=(double)pow((double)10,tmp);
for(i=1;i<n;i++)
{
nCr+=(double)log10((double)(n-i)/(double)i);
tmp=nCr-z;
if(tmp>-15)
s+=a[i]*(double)pow((double)10,tmp);
}
a[0]=s;
}
int main()
{
//clock_t beg;
scanf("%ld",&test);
//beg=clock();
for(tst=1;tst<=test;tst++)
{
scanf("%ld",&n);
for(i=0;i<n;i++)
scanf("%lf",a+i);
f();
printf("Case #%d: %.3lf\n",tst,a[0]);
}//printf("process cost time:%d\n",clock()-beg);
}
Posted: Fri Aug 19, 2005 1:18 pm
by mf
The first number in the given sequence may be negative or zero. And you're taking its logarithm in this line:
Posted: Sun Aug 21, 2005 1:31 pm
by sunnycare
thanks...
ac now.
Re: 10883 - Supermean
Posted: Sun Jun 07, 2009 11:30 am
by alirezanoori
Hi,
I've read these posts and came with a solution, but I have a minor problem with the 2 ^ n part.
Could you please take a look at my code and help me?
Thanks in advance.
Code: Select all
#include <iostream>
#include <cmath>
using namespace std;
double arr[50000];
int n;
long double newComb(long double oldCm, int n, int i)
{
if(i == 0)
return 1;
if((n + 1 - i) == 0)
return 1;
long double oldLog = log(oldCm);
long double log2 = log((long double)(i));
long double log1 = log((long double)(n + 1 - i));
long double newLog = oldLog + log1 - log2;
return exp(newLog);
}
void process()
{
long double Cm = 1;
long double sum = 0;
n--;
long double pw = pow((long double)2.0, n);
for(int i = 0; i <= n; i++)
{
Cm = newComb(Cm, n, i);
sum += Cm / pw * arr[i];
}
cout << fixed << showpoint << setprecision(3) << sum << endl;
}
int main()
{
int tc;
cin >> tc;
for(int i = 0; i < tc; ++i)
{
cin >> n;
for(int j = 0; j < n; ++j)
cin >> arr[j];
cout << "Case #" << i + 1 << ": ";
process();
}
return 0;
}
Re: 10883 - Supermean
Posted: Sun Jun 07, 2009 11:48 am
by helloneo
alirezanoori wrote:Hi,
I've read these posts and came with a solution, but I have a minor problem with the 2 ^ n part.
Maybe somehow you can use n * log(2) instead of calculating pow(2, n)
Re: 10883 - Supermean
Posted: Sun Jun 07, 2009 7:37 pm
by alirezanoori
And how could I do that?
Re: 10883 - Supermean
Posted: Mon Jun 08, 2009 3:20 pm
by alirezanoori
Well, I managed to convert the formula to this format:
result = Sigma exp(log(a) + log(nCi) - (n * pow(2.0))
It works really great for positive numbers, but when it comes to negative numbers, program fails (because of log(a) part).
Any suggestions?
Re: 10883 - Supermean
Posted: Tue Jun 09, 2009 4:52 pm
by helloneo
alirezanoori wrote:Well, I managed to convert the formula to this format:
It works really great for positive numbers, but when it comes to negative numbers, program fails (because of log(a) part).
Any suggestions?
How about this way..?
Code: Select all
if (a[i] > 0)
result += exp(log(a[i]) ....);
else
result -= exp(log(-a[i]) ....);
Re: 10883 - Supermean
Posted: Wed Jun 10, 2009 9:40 am
by alirezanoori
Well, I changed my code to this, still WA!
Code: Select all
long double newComb(long double oldLog, int n, int i)
{
if(i == 0)
return log(1.0);
if((n + 1 - i) == 0)
return log(1.0);
long double log2 = log((long double)(i));
long double log1 = log((long double)(n + 1 - i));
long double newLog = oldLog + log1 - log2;
return newLog;
}
void process()
{
long double Cm = log(1.0);
long double sum = 0, cur;
n--;
double pw = n * log(2.0);
for(int i = 0; i <= n; i++)
{
Cm = newComb(Cm, n, i);
if(arr[i] > 0)
{
cur = log(arr[i]) + Cm - pw;
sum += cur;
}
else
{
cur = log(-arr[i]) + Cm - pw;
sum += exp(cur);
}
}
cout << fixed << showpoint << setprecision(3) << sum << endl;
}
Re: 10883 - Supermean
Posted: Wed Mar 23, 2011 5:32 pm
by sitz
Hi!
I tried this problem with algorithm mentioned here:
http://www.algorithmist.com/index.php/UVa_10883
which is:
((n-1)C0 * a1 + (n-1)C1 * a2 + .....+(n-1)Cmid-1 * a mid + ... + (n-1)C0 * an) / 2 ^ (n-1)
As we have
nCr = nCn-r, so, i just modified the algorithm to this:
((n-1)C0 * a1 + (n-1)C1 * a2 + .....+(n-1)Cmid-1 * a mid + ... + (n-1)Cn-1 * an) / 2 ^ (n-1)
i.e. sum of products of coefficients with the given numbers, but, it gives
WA 
( I'm using double for storing nCr and modular exponentiation for 2^(n-1)
Also, can it be done without using
logarithms
Regards,
-SITZ
Re: 10883 - Supermean
Posted: Thu Jul 18, 2013 5:58 pm
by Sabiha_Fancy
I am trying to understand this problem but failed. Can anyone explain how to solve this problem ?
Re: 10883 - Supermean
Posted: Thu Jul 18, 2013 11:20 pm
by brianfry713
"What's a supermean," you ask? I'll tell you. List the n given numbers in non-decreasing order. Now compute the average of each pair of adjacent numbers. This will give you n - 1 numbers listed in non-decreasing order. Repeat this process on the new list of numbers until you are left with just one number - the supermean.
First sample input n = 1 so the input number is the supermean.
Second sample input n = 2 so the supermean is the same as the average.
Third sample input: 1 2 3 becomes 1.5 2.5 then 2
Fourth sample input: 1 2 3 4 5 becomes 1.5 2.5 3.5 4.5 then 2 3 4 then 2.5 3.5 then 3