369 - Combinations

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

Moderator: Board moderators

Post Reply
Subeen
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » Sat Dec 01, 2001 8:44 pm

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

Post by FCS » Tue Dec 04, 2001 3:30 am

Use unsigned long. That is sufficient.

ahanys
New poster
Posts: 24
Joined: Mon Nov 19, 2001 2:00 am
Location: N/A
Contact:

Post by ahanys » Wed Feb 27, 2002 2:56 pm

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:

Post by pochmann » Thu Feb 28, 2002 4:52 am

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:

Post by pochmann » Thu Feb 28, 2002 4:57 am

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

Post by junjieliang » Thu Feb 28, 2002 10:54 am

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:

Post by Stefan Pochmann » Thu Feb 28, 2002 11:36 am

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

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
Location: Bangladesh
Contact:

Post by Subeen » Mon Mar 18, 2002 7:23 am

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:

Post by Stefan Pochmann » Mon Mar 18, 2002 8:10 am

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
Location: Bangladesh
Contact:

Post by Subeen » Fri Mar 22, 2002 7:01 am

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:

Post by Stefan Pochmann » Fri Mar 22, 2002 7:24 am

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Post by shahriar_manzoor » Fri Mar 22, 2002 10:52 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
:smile:

#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>

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

369 - Combinations

Post by hank » Thu Jul 04, 2002 6:12 am

i solved it but i got WA many times
i can't find the wrong.. :cry:
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:

Post by Picard » Thu Jul 04, 2002 9:00 am

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:

Post by Rodrigo » Sun Jul 07, 2002 12:18 am

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. :cry:

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.

Post Reply

Return to “Volume 3 (300-399)”