## 10375 - Choose and divide

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

prom
New poster
Posts: 10
Joined: Thu Jul 25, 2002 11:58 pm
Location: Poland

### 10375 - Choose and divide

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

int a,b;
int p,q,r,s;
long double sum;
int main(){
cout.setf(ios::fixed);
cout.precision(5);
while (cin >> p >> q >>r >>s){
a=p-q; b=r-s;
sum=0.0;
for (int i=2;i<=p;++i) sum+=log10((long double)i);
for (int i=2;i<=q;++i) sum-=log10((long double)i);
for (int i=2;i<=s;++i) sum+=log10((long double)i);
for (int i=2;i<=a;++i) sum-=log10((long double)i);
for (int i=2;i<=b;++i) sum+=log10((long double)i);
for (int i=2;i<=r;++i) sum-=log10((long double)i);
cout <<pow(10.0,sum)<<endl;
}
return 0;
}
[/cpp]

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
This is almost certainly a rounding problem. Consider that adding a lot of logs and then subtracting those very same values can lose accuracy at the end eg.
.000000001+0.1
followed by subtracting 0.1 could give 0.0 or something like .00000000099 or whatever.

I turned this into an ac simply by changing it to one loop and adding/subtracting things to sum as little as possible

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### 10375 help!

[cpp]

Can someone tell me why I get a wrong answer?
Thank you!
here is my source code

#include<stdio.h>
#include<math.h>
int main()
{

long double p,q,r,s,lc=0.0,c,i,k;
while(scanf("%Lf %Lf %Lf %Lf",&p,&q,&r,&s)!=EOF)
{
for(i=q+1;i<=p;i++)
lc=lc+log(i);
for(i=s+1;i<=r;i++)
lc=lc-log(i);
if((r-s)>=(p-q))
for(i=p+1-q;i<=(r-s);i++)
lc=lc+log(i);
else
for(i=r+1-s;i<=p-q;i++)
lc=lc-log(i);
c= exp(lc);
printf("%.5Lf\n",c);
lc=0.0;
}
return 0;
} [/cpp]

tinapon
New poster
Posts: 4
Joined: Tue Mar 25, 2003 5:20 pm

### Re: 10375 help!

I got WA too......
what wrong with that........
#include<stdio.h>
#include<math.h>
main()
{
double ans;
double ru[10001];
int i , j , min;
int a, b, c, d;
ru[0] = 0;
ru[1] = 0;
for(i = 2; i < 10001; i++)
ru = ru + log10(i);
while(scanf("%d %d %d %d",&a,&b, &c, &d) == 4)
{
ans = ru[a] - ru - ru[a - b];
ans += (ru[d] + ru[c - d] - ru [c]);
ans = pow(10,ans);
printf("%.5lf\n", ans);
}
}

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:
using log doesn't work for this problem. i tried to use log too but faild. it seems that the judge solution was not written using log so there exists some precision error. i solved this using brutforce

i wish this problem cud have been an special judge problem.

thanx
-sohel

tinapon
New poster
Posts: 4
Joined: Tue Mar 25, 2003 5:20 pm
I got Wa again.
Can you give me some test data.......
#include<stdio.h>
#include<math.h>

main()
{
double ans;
int i;
int max;
int a, b, c, d;
while(scanf("%d %d %d %d",&a,&b, &c, &d) == 4)
{
ans = 1;
if(a > b / 2)
b = a - b;
if(c > d / 2)
d = c - d;
if(b > d )
max = b;
else
max = d;
for(i = 0;i < max; i++)
{
if(b > i)
{
ans *=(a - i);
ans /=(b - i);
}
if(d > i)
{
ans /= (c - i);
ans *= (d - i);
}
}
printf("%.5lf\n", ans);
}
}

saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Contact:
consider the following input:
9999 5000 9999 5256
my program's output is:
521350.34067
your program doesn't seems like giving the same result!!

good luck
-sohel

tinapon
New poster
Posts: 4
Joined: Tue Mar 25, 2003 5:20 pm
Thanks you input .......

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:
Anyone got input that can break my code? I keep getting WA. I used the brute-force approach and have taken considerable care to avoid overflow/underflow already. Any help would be much appreciated.

[cpp]
#include <iostream.h>
#include <stdlib.h>
#include <string>
#include <iomanip>

int remaining[6];

int value(int);
int main()
{
cout.setf(ios::fixed);
cout << setprecision(5);
int p,q,r,s;
while(true)
{
cin >> p >> q >> r >> s;
if(cin.eof())
break;
remaining[0] = p;
remaining[1] = s;
remaining[2] = r-s;
remaining[3] = q;
remaining[4] = p-q;
remaining[5] = r;

long double result=1.0;
long double temp1, temp2, temp;
while(remaining[0] > 0 || remaining[1] > 0 || remaining[2] > 0 ||
remaining[3] > 0 || remaining[4] > 0 || remaining[5] > 0)
{
temp1 = (long double)(1.0 * value(0) / value(3) / value(4));
temp2 = (long double)(1.0 * value(1) * value(2) / value(5));
temp = temp1*temp2;
result*=temp;
// cout << "result:" << result << "\n";
}
cout << result << "\n";
}
return 0;
}

int value(int pos)
{
int temp = (remaining[pos] == 0 ? 1 : remaining[pos]);
if(remaining[pos] > 0)
remaining[pos]--;
return temp;
}[/cpp]

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm
Does anybody know how to manipulate such big integers with the input saiqbal gave?? (9999 5000 9999 5256). Using doubles it's impossible! do I have to use an integer matrix or anything like that??

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Split intermediate numbers into a mantissa (a double with a value between 0.1 and 1.0) and an exponent (an integer), and combine them at the end to get the answer (a double).

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm
Thx 4 the answer, I hope you meant the mantissa to be a number betwen 0.0 and 1.0, didn't you?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
No, actualy it's between 1 and 10
so:
123.456 -> mant=1.23456 exp=2
0.009876 -> mant=9.876 exp=-3
0.1111 -> mant=1.111 exp=-1
4.0 -> mant=4.0 exp=0

1.0 <= mant < 10.0
-2^31 <= exp < 2^31

danifart
New poster
Posts: 10
Joined: Thu Mar 18, 2004 5:51 pm
Hi again!

I did it as you said, with the mantissa and the exponent, I get correct solution for all the example Input cases (although that's not too much difficult ) and for the Input from saiqbal: 9999 5000 9999 5256 which outputs exactly: 521350.34067

So I can't get the input that makes it fail, can anyone post the worse case which may output a number near 100,000,000 (result must be lower than these number) and/or anyone can break my code?? (little joey? :p)

Thank you very much!

(I don't hope you to understand it, just try to find a test case that makes it not to be accepted... I'm missing it...)

Code: Select all

``````#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

using namespace std;
int fp,fq,fr,fs,frms,fpmq;			//Factorial de p,q,r,r menys s i p menys q

int simplifica(double* p,double* q,double* r,double* s,double* pmq,double* rms)
{
int dif=10001;
char select1='n';
char select2='n';

if ( (abs(*p-*q) < dif) && ((*p-fp)==1) && ((*q-fq)==1) && fp && fq)
{
select1='p';
select2='q';
if (*p>=*q)
{
dif=*p-*q;
}
else
{
dif=*q-*p;
}
}
if ( (abs(*p-*r) < dif) && ((*p-fp)==1) && ((*r-fr)==1) && fp && fr)
{
select1='p';
select2='r';
if (*p>=*r)
{
dif=*p-*r;

}
else
{
dif=*r-*p;
}
}
if (abs(*p-*pmq)<dif && ((*p-fp)==1) && ((*pmq-fpmq)==1) && fp && fpmq)
{
select1='p';
select2='y';
if (*p>=*pmq)
{
dif=*p-*pmq;
}
else
{
dif=*pmq-*p;
}
}
if (abs(*s-*r)<dif && ((*s-fs)==1) && ((*r-fr)==1) && fs && fr)
{
select1='s';
select2='r';
if (*s>=*r)
{
dif=*s-*r;
}
else
{
dif=*r-*s;
}

}
if (abs(*s-*q)<dif && ((*s-fs)==1) && ((*q-fq)==1) && fs && fq)
{
select1='s';
select2='q';
if (*s>=*q)
{
dif=*s-*q;
}
else
{
dif=*q-*s;
}
}
if (abs(*s-*pmq)<dif && ((*s-fs)==1) && ((*pmq-fpmq)==1) && fs && fpmq)
{
select1='s';
select2='y';
if (*s>=*pmq)
{
dif=*s-*pmq;
}
else
{
dif=*pmq-*s;
}
}
if (abs(*rms-*r)<dif && ((*rms-frms)==1) && ((*r-fr)==1) && frms && fr)
{
select1='x';
select2='r';
if (*rms>=*r)
{
dif=*rms-*r;
}
else
{
dif=*r-*rms;
}
}
if (abs(*rms-*q)<dif && ((*rms-frms)==1) && ((*q-fq)==1) && frms && fq)
{
select1='x';
select2='q';
if (*rms>=*q)
{
dif=*rms-*q;
}
else
{
dif=*q-*rms;
}
}
if (abs(*rms-*pmq)<dif && ((*rms-frms)==1) && ((*pmq-fpmq)==1) && frms && fpmq)
{
select1='x';
select2='y';
if (*rms>=*pmq)
{
dif=*rms-*pmq;
}
else
{
dif=*pmq-*rms;
}
}
//Aqui tenim la diferencia minima entre dos nombres
if (select1=='p')
{
if (select2=='q')
{
if (*p > *q)
{
fp=dif-1;
*q=1;
fq=0;
}
else
{
if (*p < *q)
{
fq=dif-1;
*p=1;
fp=0;
}
else
{
//p=q
*p=1;
*q=1;
fp=0;
fq=0;
}
}

}
else
{
if (select2=='r')
{
if (*p > *r)
{
fp=dif-1;
*r=1;
fr=0;
}
else
{
if (*p < *r)
{
fr=dif-1;
*p=1;
fp=0;
}
else
{
//p=r
*p=1;
*r=1;
fp=0;
fr=0;
}
}
}
else
{
if (select2=='y')
{
//select2='y'
if (*p > *pmq)
{
fp=dif-2;
*pmq=1;
fpmq=0;
}
else
{
if (*p < *pmq)
{
fpmq=dif-1;
*p=1;
fp=0;

}
else
{
//p=pmq
*p=1;
*pmq=1;
fp=0;
fpmq=0;
}
}
}
else
{
return 0;
}
}
}

}
else
{
if (select1=='s')
{
if (select2=='q')
{
if (*s > *q)
{
fs=dif-1;
*q=1;
fq=0;
}
else
{
if (*s < *q)
{
fq=dif-1;
*s=1;
fs=0;
}
else
{
//s=q
*s=1;
*q=1;
fs=0;
fq=0;
}
}
}
else
{
if (select2=='r')
{
if (*s > *r)
{
fs=dif-1;
*r=1;
fr=0;
}
else
{
if (*s < *r)
{
fr=dif-1;
*s=1;
fs=0;
}
else
{
//s=r
*s=1;
*r=1;
fs=0;
fr=0;
}
}
}
else
{
//select2='y'
if (*s > *pmq)
{
fs=dif-1;
*pmq=1;
fpmq=0;
}
else
{
if (*s < *pmq)
{
fpmq=dif-1;
*s=1;
fs=0;
}
else
{
//s=pmq
*s=1;
*pmq=1;
fs=0;
fpmq=0;
}
}
}
}

}
else
{
if (select1=='x')
{
if (select2=='q')
{
if (*rms > *q)
{
frms=dif-1;
*q=1;
fq=0;
}
else
{
if (*rms < *q)
{
fq=dif-1;
*rms=1;
frms=0;
}
else
{
//rms=q
*rms=1;
*q=1;
frms=0;
fq=0;
}
}
}
else
{
if (select2=='r')
{
if (*rms > *r)
{
frms=dif-1;
*r=1;
fr=0;
}
else
{
if (*rms < *r)
{
fr=dif-1;
*rms=1;
frms=0;
}
else
{
//rms=r
*rms=1;
*r=1;
frms=0;
fr=0;
}
}
}
else
{
//select2='y'
if (*rms > *pmq)
{
frms=dif-1;
*pmq=1;
fpmq=0;
}
else
{
if (*rms < *pmq)
{
fpmq=dif-1;
*rms=1;
frms=0;
}
else
{
//rms=pmq
*rms=1;
*pmq=1;
frms=0;
fpmq=0;
}
}
}
}
}
else
{
return 0;
}
}
}
``````

45793HM
New poster
Posts: 4
Joined: Tue Jun 14, 2005 4:49 pm
Location: Portugal

### 10375 - WA

Can't find error. I try all inputs and it works, but WA.

/* Choose and Divide */
#include <stdio.h>
double c[2000],d[2000];

int qsortc (n)
int n;
{ int i,j=0;
double s;
for (i=1;i<n;i++)
if (c<c[i+1]) { s=c; c=c[i+1]; c[i+1]=s;j=1;}
return(j);
}

int qsortd (n)
int n;
{ int i,j=0;
double s;
for (i=1;i<n;i++)
if (d<d[i+1]) { s=d; d=d[i+1]; d[i+1]=s;j=1;}
return(j);
}

int main(void)
{ int p,q,m,n,r,s,i,n1,n2,n3,k1,k2,k3,cc,dd,el=2000;
double max,res;

/* -2,147,483,648 max long */
max=21474839;

while (scanf("%d%d%d%d",&p,&q,&r,&s)==4)
{
for (i=0;i<el;i++) c=d=1;
cc=dd=1;
for (i=2;i<=p;i++) if (c[cc]*i>max) c[++cc]*=i; else c[cc]*=i;
for (i=2;i<=s;i++) if (c[cc]*i>max) c[++cc]*=i; else c[cc]*=i;
for (i=2;i<=r-s;i++) if (c[cc]*i>max) c[++cc]*=i; else c[cc]*=i;

for (i=2;i<=r;i++) if (d[dd]*i>max) d[++dd]*=i; else d[dd]*=i;
for (i=2;i<=q;i++) if (d[dd]*i>max) d[++dd]*=i; else d[dd]*=i;
for (i=2;i<=p-q;i++) if (d[dd]*i>max) d[++dd]*=i; else d[dd]*=i;

while(qsortc(el-1)!=0) ;
while(qsortd(el-1)!=0) ;

res=1; for(i=1;i<el;i++) res*=c/d;
if (res<0) res=-res;
printf("%.5f\n",res);
}

return(0);
}