## 369 - Combinations

Moderator: Board moderators

Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
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
New poster
Posts: 9
Joined: Mon Oct 15, 2001 2:00 am
Use unsigned long. That is sufficient.
ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:
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
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
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
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
So much trouble...
Why not just build a Pascal triangle?
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
ok...
finally i got accecpted...
using unsigned long int
thanks to all for ur comments...
subeen.
Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Contact:
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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
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
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am
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
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

### 369 - Combinations

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
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:
you have to print the same n,m pair as readed (now you may print different m)
Rodrigo
New poster
Posts: 14
Joined: Sun Jul 07, 2002 12:03 am
Location: Brazil
Contact:
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?