369 - Combinations

[arjasepp]

I think that you should use long double when dividing numbers, because some results might come too big when trying to multiply.
Some data for testing perhaps:
100 6
23 5
34 20
17 9
98 6
88 12
67 21
34 34
12 11
90 6
80 7
70 7
60 8
50 9
45 10
These should be the correct answers:
1192052400
33649
1391975640
24310
1052618392
3730762732
64891431
1
12
622614630
3176716400
1198774720
2558620845
2505433700
3190187286

Try with these numbers and find out what is wrong, but I suggest you to use long double when calculating

[passwd]

hi, I'm getting time limit in this problem and I don't know why ?

/*---start---*/
[c]
#include <stdio.h>
/*#define DEBUG*/

long fact(long x) {
int i;
for(i=x-1;i!=1;--i) x*=i;
#ifdef DEBUG
printf("fact: %d\n",x);
#endif
return x;
}


long mdc(long _m,long _n) {
long resto;
do {
resto = _m % _n;
_m=_n;
_n=resto;
} while(resto!=0);
return(_m);
}

void reduz(long *n,long *m) {
int j;
j=mdc(*n,*m);
while(j!=1) {
*n/=j;
*m/=j;
j=mdc(*n,*m);
}
}


int main() {

int n,m;

while(scanf("%d%d",&n,&m)!=-1) {
int i;
if( n==0 && m==0 ) break;
if(n==m) printf("%d things taken %d at a time is 1 exactly.\n",n,m);
else {
long a,b,i,k;
long *pilha,total=1;
int t=0;
k=n-m;
if(k > m) k=m; /*usa o menor k*/
pilha=(long*) malloc(sizeof(long)*(k+1));

#ifdef DEBUG
printf("k: %d\n",k);
#endif
for(i=n,b=fact(k);i > n - k;--i) {
if(b==1) {
pilha[t++]=i;
}
else {
a=i;
reduz(&a,&b);
#ifdef DEBUG
printf("a: %d , b: %d\n",a,b);
#endif
pilha[t++]=a;
}
}

while(t!=0) total*=pilha[--t];
if(b!=1) total/=b;
printf("%d things taken %d at a time is %d exactly.\n",n,m,total);
}
}
return 0;

}

[/c]
/*---end--*/

[hank]

you should use "long double".

[passwd]

hi, I'm trying to solve p 369 but I'm getting WA , why ?

I have used long , unsigned long, long double , but still WA ...

[c]
#include <stdio.h>
/*#define DEBUG*/

int mdc(int _m,int _n) {
int resto;
do {
resto = _m % _n;
_m=_n;
_n=resto;
} while(resto!=0);
return(_m);
}

void reduz(int *n,int *m) {
int j;
j=mdc(*n,*m);
while(j!=1) {
*n/=j;
*m/=j;
j=mdc(*n,*m);
}
}


int main() {

int n,m;

while(fscanf(stdin,"%d%d",&n,&m)!=-1) {
if( n==0 && m==0 ) break;
if(n==m) fprintf(stdout,"%d things taken %d at a time is 1 exactly.\n",n,m);
else {
int k=m,j,p;
int *cima,*baixo;
unsigned long a,b,c;
if( n-m < k ) k=n-m; /*usa o menor k*/
cima = (int*) malloc(sizeof(int)*k);
baixo = (int*) malloc(sizeof(int)*k);
#ifdef DEBUG
for(j=0;j<k;++j) cima[j]=baixo[j]=-1;
#endif
for(j=0; j < k; ++j) cima[j]=n-j;
for(j=k; j > 0; --j) baixo[j-1]=j;
#ifdef DEBUG
printf("n: %d m: %d k: %d \n",n,m,k);
for(j=0;j<k;++j) printf("%d ",cima[j]); printf("\n");
for(j=0;j<k;++j) printf("%d ",baixo[j]); printf("\n");
#endif

for(j=0;j<k;++j) {
for(p=0;p<k;++p) {
if(baixo[p]==1) continue;
else reduz(&cima[j],&baixo[p]);
}
}

#ifdef DEBUG
printf("\n\n\n");
for(j=0;j<k;++j) printf("%d ",cima[j]); printf("\n");
for(j=0;j<k;++j) printf("%d ",baixo[j]); printf("\n");
printf("\n\n");
#endif

for(j=0,a=1;j<k;++j) a*=cima[j];
for(j=0,b=1;j<k;++j) b*=baixo[j];

c=a/b;

fprintf(stdout,"%d things taken %d at a time is %u exactly.\n",n,m,c);

free(cima);free(baixo);
}
}
return 0;

}

[/c]

[Red Scorpion]

Hmmm, your output is wrong for this test case:

Code: Select all

Input :
100 20
100 90
100 85

Your output:
100 things taken 20 at a time is 3820054042 exactly.
100 things taken 90 at a time is 1591253560 exactly.
100 things taken 85 at a time is 1489087776 exactly.

The output should be:
100 things taken 20 at a time is 1027792266232686106 exactly.
100 things taken 90 at a time is 17310309456440 exactly.
100 things taken 85 at a time is 253338471349988640 exactly.

NB : Try to use long long , instead of long, long double, ...

Hope this helps.

[angga888]

Btw, Red Scorpion, the problem stated :
You may assume that the final value of C will fit in a 32-bit Pascal LongInt or a C long.

I just used long in C++ and I got Accepted.
Use under calculation and you will not get overflow.

Good Luck !

[passwd]

I rewrite my code using another algorithm, but still WA
and I don't know where is the problem ...

[c]
#include <stdio.h>
#include <math.h>
int main() {
unsigned long n,m;
while(fscanf(stdin,"%d%d",&n,&m)==2) {
if( n==0 && m==0 ) break;
if(n==m) fprintf(stdout,"%d things taken %d at a time is 1 exactly.\n",n,m);
else {
unsigned long k=m,i;
long double r=1;
if (k>n-k) k=n-k; /*usa o menor k*/
for(i=1;i<=k;++i) r/=i;
for(i=n;i>=n-k+1;--i) r*=i;
fprintf(stdout,"%d things taken %d at a time is %.0f exactly.\n",n,m,fabs(r));
}
}
return 0;
}
[/c]

[Hisoka]

You not any problem with your code, but maybe your problem only at your via email. When I see your code, your algo is true and I don't get any mistake at yours. I just copy paste your code, and got AC.

[passwd]

thanks !! I got AC too , the problem was in the mail !!

[rjhadley]

I think a few of your results are wrong. They should be:

88 things taken 12 at a time is 205371886988268 exactly.
67 things taken 21 at a time is 129728497393775280 exactly.

[rjhadley]

Don't you mean:

100 things taken 20 at a time is 535983370403809682970 exactly.

[kenny1har]

[pascal]
program p369;
var m,n,i:longint;
r:real;
begin
while not eof(input) do begin
readln(m,n);
if (m=0) and (n=0) then exit;
r:=1;
if n>m-n then n:=m-n;
for i:=2 to n do r:=r/i;
for i:=m downto m-n+1 do r:=r*i;
writeln(m,' things taken ',n:0,' at a time is ',round(r):0,' exactly.');
end;
end.
[/pascal]

I think, it should be correct.
Please tell me where the error is.

[little joey]

You change n if n>m-n to m-n.

So for the input 7 5, you print "7 things taken 2 at the time...", which is obviously wrong.

I haven't checked it, but my intuition tells me dat by doing the calculation using reals will give precision errors quite rapidly.

[kenny1har]

thanks, I have got 'Accepted'.
It's only the output that was wrong.

[osan]

I