Page 1 of 7

Posted: Sat Dec 01, 2001 8:44 pm
by 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.

Posted: Tue Dec 04, 2001 3:30 am
by FCS
Use unsigned long. That is sufficient.

Posted: Wed Feb 27, 2002 2:56 pm
by 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>

Posted: Thu Feb 28, 2002 4:52 am
by 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

Posted: Thu Feb 28, 2002 4:57 am
by 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++.

Posted: Thu Feb 28, 2002 10:54 am
by junjieliang
So much trouble...
Why not just build a Pascal triangle?

Posted: Thu Feb 28, 2002 11:36 am
by Stefan Pochmann
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.

Posted: Mon Mar 18, 2002 7:23 am
by Subeen
ok...
finally i got accecpted...
using unsigned long int
thanks to all for ur comments...
subeen.

Posted: Mon Mar 18, 2002 8:10 am
by 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...

Posted: Fri Mar 22, 2002 7:01 am
by 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>

Posted: Fri Mar 22, 2002 7:24 am
by 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.

Posted: Fri Mar 22, 2002 10:52 am
by 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
: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>

369 - Combinations

Posted: Thu Jul 04, 2002 6:12 am
by hank
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);
}
}

Posted: Thu Jul 04, 2002 9:00 am
by Picard
you have to print the same n,m pair as readed (now you may print different m)

Posted: Sun Jul 07, 2002 12:18 am
by 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. :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.