369 - Combinations

[Subeen]

i solved it and it gives correct ans for sample data set but got wrong ans.
can anyone help me with some in/out data???
i used long int (in c) variable in this problem. do i need to use unsigned long?
do anyone know about long long int (in linux)??? plz write abt it.

[FCS]

Use unsigned long. That is sufficient.

[ahanys]

In linux when you want to use the long long int, you only use it in function scanf and printf.
For example:
long long a;
scanf("%lli",&a);
printf("%lli",a);

If you want to use unsigned long long, then use scanf("%llu",&a);

unsigned long long is 64bits long. then you can store in it the value from 0 to 2^64-1.

Else long long usage is the same as any other integer type.





<font size=-1>[ This Message was edited by: ahanys on 2002-02-27 14:02 ]</font>

[pochmann]

int is totally sufficient, guys! You just have to be a bit clever. Hint example:

If you want to multiply (41*40*39)/(1*2*3) with (38/4), then you can first divide it by 2 and then multiply it by 19.

This way you never have temporary values that are higher than the end result.

Stefan

[pochmann]

Correction to previous post: of course you should always calculate C(N,N-M) instead of C(N,M) if M>N/2. Otherwise you can get higher temporary values, even with my modification.

Stefan

P.S. double should also work fine and has the advantage over "long long int" to really be in standard c/c++.

[junjieliang]

So much trouble...
Why not just build a Pascal triangle?

[Stefan Pochmann]

Because that's the slow, space-hungry, and most importantly, the ugly variant

Stefan

P.S. "slow" of course only if the number of test cases is small, I know... but then it's still ugly.

[Subeen]

ok...
finally i got accecpted...
using unsigned long int
thanks to all for ur comments...
subeen.

[Stefan Pochmann]

As far as I know, "int", "long int" and "long" are almost always the same. "long long" is better, but not supported by ANSI C++. Don't know about standard C++. Try this:

Code: Select all

int main () {
  cout << sizeof( unsigned int ) << endl;
  cout << sizeof( unsigned long int ) << endl;
  cout << sizeof( unsigned long ) << endl;
  cout << sizeof( unsigned long long ) << endl;
}

You could also try to find out what the Valladolid guys have with a small test program. If you do, let us know about the results...

[Subeen]

stefan, i got this prog. accecpted (10079)
#include <stdio.h>

void main()
{
long long int n, m;
while(1)
{
scanf("%lli", &n);
if(n<0) break;
m = .....;
printf("%llin", m);
}
}


<font size=-1>[ This Message was edited by: Subeen on 2002-03-29 13:57 ]</font>

[Stefan Pochmann]

Yep, that's exactly what I meant. This type seems to usually have 8 bytes. Of course the king is "long double", at my computer 12 bytes.

Btw, you don't have to post your whole solution here to demonstrate it. The board is getting flooded with solutions right now, which I don't think is good.

[shahriar_manzoor]

The Windows users can use 64 bit integer in the following way, and then before submitting to the OJ change it to long long


#include<stdio.h>
__int64 test;

void main(void)
{
scanf("%I64d",&test);
printf("%I64dn",test);
}

<font size=-1>[ This Message was edited by: shahriar_manzoor on 2002-03-22 09:53 ]</font>

<font size=-1>[ This Message was edited by: shahriar_manzoor on 2002-03-22 09:54 ]</font>

[hank]

i solved it but i got WA many times
i can't find the wrong..
help me!!
thanks!!

(problem 369)
(i use TurboC++ 3)
-------------------------

#include "stdio.h"
void main()
{
unsigned long n,m,c;
while(scanf("%lu %lu",&n,&m)==2){
unsigned long i,j; long double cc=1;
if(n==0&&m==0)break;
if(n-m<m) m=n-m;
for(i=n,j=(unsigned long)1;j<=m;i--&&j++)
{
cc *=(long double)i;
cc /=(long double)j;
}
c=(unsigned long)cc;
printf("%lu things taken %lu at a time is %lu exactly.\n",n,m,c);
}
}

[Picard]

you have to print the same n,m pair as readed (now you may print different m)

[Rodrigo]

Ok, people, there's something REALLY wrong about this problem. I tried tons of different approaches, and I got more W.A.'s than I can remember. But, for each one of them, I couldn't find one single test case for which my solution was wrong.

Anyway, my last desperate attempt was to use a Big Integer data type to calculate. So I did. The main part of the program appears below:

...
void main()
{
int n, m, M, i;
TBigNumber *c = (TBigNumber *) malloc (sizeof(TBigNumber));
TBigNumber *aux = (TBigNumber *) malloc (sizeof(TBigNumber));

scanf("%d %d", &n, &M);
while (n)
{
m = (M > n / 2) ? n - M : M;
InitNumber(c, 1); /* initializes c with "1" */
for (i = 1; i <= m; i++)
{
InitNumber(aux, n - i + 1);
BigMul(c, aux, c); /* multiplies c and aux, result in c */
}
for (i = 1; i < m; i++)
{
InitNumber(aux, m - i + 1);
BigDivMod(c, aux, c, aux); /* divides c by aux, result in c, remainder in aux */
}

printf("%d things taken %d at a time is ", n, M);
for (i = 0; i < c->Size; i++)
printf("%d", c->Digits);
printf(" exactly.\n");
scanf("%d %d", &n, &M);
}
free(c);
free(aux);
}
...

In this last version, I didn't use any trick - it was straight from the formula. It just CAN'T be wrong, I've used this same Big Integer structure lots of times, it is 100% correct. Is there anyone who got "accepted" in this problem and would be willing to send me a text file in the form

<value of N> <value of M> <right answer>

so I can check my program one last time before shooting my computer?

Thanks in advance,

Rodrigo

PS: I won't use your file to create a huge look-up array , I just wanna know what's wrong.