@anil : it works for large numbers as well... u did not check properly i
guess
1. #include <iostream>
2. #include <vector>
3. #include <map>
4. using namespace std;
5.
6. unsigned long long choose(unsigned n, unsigned k) {
7. if (k > n)
8. return 0;
9. if (k > n/2)
10. k = n-k; // Take advantage of symmetry
11. long double accum = 1;
12. for (unsigned i = 1; i <= k; i++)
13. accum = accum * (n-k+i) / i;
14. return accum + 0.5; // avoid rounding error
15. }
16.
17.
18. int main(){
19. long int a; cin>>a;
20. for(int i=0;i<a;i++){
21. long int n,k;
22. cin>>n; cin>>k;
23. cout<<choose((float)n-1,(float)k-1)<<endl;
24. }
25. return 0;
26. }
-Rohit
On Sun, Mar 7, 2010 at 3:22 PM, Rohit Saraf <[email protected]>wrote:
> @sharad : yes... prime number generation for RSA :P
> -Rohit
>
>
>
> On Sun, Mar 7, 2010 at 3:19 PM, Rohit Saraf
> <[email protected]>wrote:
>
>> even my code would work if u make everything long long... i guess..
>>
>> -Rohit
>>
>>
>>
>> On Sun, Mar 7, 2010 at 3:15 PM, B |_ /\ C |<--D ! /\ /\/\ O /\| D <
>> [email protected]> wrote:
>>
>>> long long r=N-K<K?(N-K):K;//chose small to miimize the loop
>>> int n=N-(N-r)+1;
>>> r=1;
>>> long long res=1;
>>> for(long long i=n;i<=N;i++)
>>> {
>>> res=res*i;
>>> res=res/r++;
>>> }
>>> cout<<res<<endl;
>>> //-----------------------------------
>>> this is working ...code...
>>>
>>> On Sun, Mar 7, 2010 at 3:12 PM, Anil C R <[email protected]> wrote:
>>>
>>>> doesn't work for big numbers :P
>>>> Anil
>>>>
>>>>
>>>>
>>>> On Sun, Mar 7, 2010 at 2:53 PM, Rohit Saraf <
>>>> [email protected]> wrote:
>>>>
>>>>> Here is the code if you want... i have not written it...
>>>>> it's directly copied from wiki :)
>>>>>
>>>>> unsigned long long choose(unsigned n, unsigned k) {
>>>>> if (k > n)
>>>>> return 0;
>>>>>
>>>>> if (k > n/2)
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> k = n-k; // Take advantage of symmetry
>>>>>
>>>>> long double accum = 1;
>>>>> unsigned i;
>>>>> for (i = 1; i <= k; i++)
>>>>> accum = accum * (n-k+i) / i;
>>>>>
>>>>> return accum + 0.5; // avoid rounding error
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> }
>>>>>
>>>>> call choose(n-1,k-1);
>>>>>
>>>>>
>>>>> -Rohit
>>>>>
>>>>>
>>>>>
>>>>> On Sun, Mar 7, 2010 at 2:49 PM, Rohit Saraf <
>>>>> [email protected]> wrote:
>>>>>
>>>>>> The answer is simply : (N-1) Choose (k-1)
>>>>>>
>>>>>>
>>>>>> -Rohit
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Sun, Mar 7, 2010 at 2:11 PM, naga vinod kumar <
>>>>>> [email protected]> wrote:
>>>>>>
>>>>>>> How to solve this problem....
>>>>>>>
>>>>>>> http://www.codechef.com/problems/MARBLES/
>>>>>>>
>>>>>>>
>>>>>>> K.Naga Vinod Kumar
>>>>>>>
>>>>>>> --
>>>>>>> You received this message because you are subscribed to the Google
>>>>>>> Groups "Algorithm Geeks" group.
>>>>>>> To post to this group, send email to [email protected].
>>>>>>> To unsubscribe from this group, send email to
>>>>>>> [email protected]<algogeeks%[email protected]>
>>>>>>> .
>>>>>>> For more options, visit this group at
>>>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>>>
>>>>>>
>>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to [email protected].
>>>>> To unsubscribe from this group, send email to
>>>>> [email protected]<algogeeks%[email protected]>
>>>>> .
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected]<algogeeks%[email protected]>
>>>> .
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to [email protected].
>>> To unsubscribe from this group, send email to
>>> [email protected]<algogeeks%[email protected]>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
