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

Post by prom » Tue Oct 29, 2002 1:49 am

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

Post by Caesum » Wed Dec 25, 2002 2:26 pm

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

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

10375 help!

Post by sohel » Mon Feb 24, 2003 10:01 am

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

Post by tinapon » Tue Mar 25, 2003 5:23 pm

I got WA too......
what wrong with that........ :oops:
#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);
}
}

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Wed Mar 26, 2003 2:39 pm

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 :wink:

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

Post by tinapon » Wed Mar 26, 2003 2:58 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);
}
}

User avatar
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal » Wed Mar 26, 2003 6:32 pm

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!!:wink:

good luck
-sohel

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

Post by tinapon » Thu Mar 27, 2003 5:59 pm

Thanks you input ....... :D

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Post by stcheung » Thu Jun 12, 2003 1:45 am

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

Post by danifart » Wed May 12, 2004 6:57 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??

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed May 12, 2004 9:39 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

Post by danifart » Wed May 12, 2004 10:55 pm

Thx 4 the answer, I hope you meant the mantissa to be a number betwen 0.0 and 1.0, didn't you?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed May 12, 2004 11:24 pm

No, actualy it's between 1 and 10 :oops:
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

Post by danifart » Fri May 14, 2004 5:16 am

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

Post by 45793HM » Mon Sep 26, 2005 12:18 am

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);
}

Post Reply

Return to “Volume 103 (10300-10399)”