369 - Combinations

[NaIx]

I submit new code but still got WA... I'm really confuse because my Dev C++ doesn't have compiler for long long int type... somebody help me... what wrong with my algorithm........

Code: Select all

#include<cstdio>
#include<cstdlib>

int main()
{
    long int N, M, C, i, j, k;
    while(scanf("%ld %ld",&N,&M)==2)
    {
        if(N==0&&M==0) break;
        if(N==M) printf("%ld things taken %ld at a time is 1 exactly.\n",N,M);
        else
        {
            C=1;
            k=M;
            if(N-k < k) k=N-k;
            for(i=N;i>=N-k+1;i--)
            {
                C*=i;
        //        printf("%ld %ld",C,i);
          //      system("pause");
            }
            for(j=1;j<=M;j++)
            {
                C/=j;
           //     printf("%ld %ld",C, j);
           //     system("pause");   
            }
            printf("%ld things taken %ld at a time is %ld exactly.\n",N,M,C);
        }   
    }
    return 0;
}

[Jan]

Try the cases.

Input:

Code: Select all

100 99
100 96
96 6
0 0

Output:

Code: Select all

100 things taken 99 at a time is 100 exactly.
100 things taken 96 at a time is 3921225 exactly.
96 things taken 6 at a time is 927048304 exactly.

Hope these help.

[Suyash.Upadhyay]

Hello all,
I have tested all cases given by different programmers in this thread and my algorithm seems to be correct, even though I am getting wrong answer. Can any one help me by viewing my code, where is flaw in my algorithm:-

Thanx in advance,
Suyash

[little joey]

For the input "100 1" your code prints "100 things taken 99 at a time is 100 exactly.". It also seems that it doesn't handle cases where N==M well: for "5 5" it prints "5 things taken 0 at a time is exactly." (note the zero and the space).

[Suyash.Upadhyay]

Thanx
I got AC.

[Jolanda]

I always get Runtime Error and I can't fugure it out why. Do you know why?

My code in Java:

import java.io.*;
import java.util.*;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader vhod = new BufferedReader(new InputStreamReader(System.in));

while (true) {
String v = vhod.readLine();
StringTokenizer space = new StringTokenizer(v, " ");
int n = Integer.parseInt(space.nextToken());
int m = Integer.parseInt(space.nextToken());
if (n == 0 && m == 0) break;
System.out.println(m + " things taken " + n + " at a time is " + C(m,n) + " exactly.");
}
}

public static int C(int m, int n) {
if (n > 2*m) return del(up(n,n-m),fact(m));
else return del(up(n,m),fact(n-m));
}

public static int[] fact(int n) {
int[] tab = new int[n-1];
for (int i = 2; i <= n; i++) {tab[i-2] = i;}
return tab;
}

public static int[] up(int n, int m) {
int[] tab = new int[n-m];
for (int i = m+1; i <= n; i++) {tab = i;}
return tab;
}

public static int del(int[] a, int[] b) {
for (int i = a.length-1; i >= 0; i--) {
for (int j = b.length-1; j >= 0; j--) {
if (a%b[j]== 0 && b[j] != 1) {
a /= b[j];
b[j] = 1;
}
}
}
int c = 1;
for (int i = 0; i < a.length; i++) {c *= a;}
return c;
}
}

[theharshest]

I am getting WA for the following code.. please help

Code: Select all

#include<iostream>
#include<cmath>

using namespace std;

int main()
{
 long double n,m,t,d;
 long double c,i;
 
 cin>>n>>m;
 
 while(1)
 {
 if(n==0 && m==0)
 break;
 
 if(n==m)
 cout<<(long long)n<<" things taken "<<(long long)m<<" at a time is "<<"1"<<" exactly."<<endl;
 else
 {
 t=min(n-m,m);
 cout<<t<<endl;
 
 c=n/t;
 
 for(i=1;i<t;i++)
 {
 
 cout<<c<<" "<<n-i<<" "<<t-i<<" "<<(n-i)/(t-i)<<endl;
 c*=(n-i)/(t-i);
 
 }   
 cout.setf(ios::fixed);
// cout.unsetf(ios::showpoint);
 cout<<(long long)n<<" things taken "<<(long long)m<<" at a time is "<<(long long)c<<" exactly."<<endl;
 }    
 cin>>n>>m;
 }    
}

[subzero]

I had a headache with this problem

I tried using different ways,
but, at the end the AC code produces:
input

Code: Select all

100 20

output

Code: Select all

100 things taken 20 at a time is 0 exactly. 

and further...

[KRUNCH]

So im stuck at problem 369 - Combinations , first of i tought it was damn easy , but i've run in some problems later I cleared it all out.
The problem is i still get WA , so i searched the forum , and pretty much every test case i tried is correct , i dont think its a problem with the sollution , but with the presentation.
Heres the code:

Code: Select all

#include <iostream>
#include <vector>

using namespace std;

int gcd (int u, int v)
{
    int t;
    while (u>0)
    {
          if (u<v) {t=u;u=v;v=t;}
          u=u-v;
    }
    return v;
}

int main ()
{
    unsigned long int n,m,r,h;
    bool first=true;
    vector <int> n1,m1;
    while (cin>>n>>m && n!=0 && m!=0)
    {
          if (!first) cout<<endl; else first=false;
          r=1;
          n1.clear();
          m1.clear();
          for (int i=n-m+1;i<n+1;i++)
          {n1.push_back(i);}
          for (int i=2;i<m+1;i++)
          {m1.push_back(i);}
          for (int i=0;i<n1.size();i++)
          {
              for (int j=0;j<m1.size();j++)
              {
                  h=gcd(n1[i],m1[j]);
                  if (n1[i]>1 && m1[j]>1 && h>1)
                  {
                      n1[i]/=h;m1[j]/=h;
                  }
              }
          }
          for (int i=0;i<n1.size();i++) {r*=n1[i];}
          cout<<n<<" things taken "<<m<<" at a time is "<<r<<" exactly."<<endl;
    }
    return 0;
}

Help guys ^^

[porker2008]

This problem is the same as Problem 530.
You can find some test cases on thread 530.

------------------------

I recommand you to use long long integer to record the result.

Also, you can not assume m could not be ZERO.
If n!=0 && m=0, you should output 1.

Sample input:

Code: Select all

10 0
 0 0

Sample output:

Code: Select all

10 things taken 0 at a time is 1 exactly.

BTW. Don't create a new thread if there exist one already.

[KRUNCH]

This problem is the same as Problem 530.
You can find some test cases on thread 530.

I recommand you to use long long integer to record the result.

BTW. Don't create a new thread if there exist one already.

Yeah i found problem 530 , its pretty much the same , and i wouldnt create a new thread if i found a soltution in the other topics , the problem is that i have none of those other problems :S

anyway , ill keep trying...

[porker2008]

Keep trying...

You will succeed anyway...

If you have further questions, please feel free to ask.

[KRUNCH]

As my algo seems too slow for 530 ill redo both problems , and previously you stated that i cannot take for sure that m != 0 but in the problem it states that 5<=m<=n therefore i didnt bother , eaven after i changed it it still gives wa , well wouldn't be fun to solve if it was easy , if I get any further problems ill post thank you for the help.
Maths is the way i should consider ^^.

[aliahmed]

I got ac with this code in 530 but why wa in369

#include<stdio.h>
int main()
{

long i,j,n,k;
double r,s;
while(scanf("%ld%ld",&n,&k))
{
if(n==0 && k==0)
break;
if(n==k || k==0)
{
printf("%ld things taken %ld at a time is 1 exactly.\n",n,k);
continue;
}
else if((n-1)==k || k==1)
{
printf("%ld things taken %ld at a time is %ld exactly.\n",n,k,n);
continue;
}
if(k>=(n/2))
k=n-k;
i=2;
r=k+1;
s=r+1;
while(1)
{
r*=s;
r/=i;
i++;
if(n==s || i==(n-k)+1)
break;
s++;
}
printf("%ld things taken %ld at a time is %.lf exactly.\n",n,k,r);
}

return 0;
}

[tryingbest]

hi...I am new in this section..please someone help me ...I have tried my best but I am getting WA evrytime.here is my code..please kindly help me.one thing my code gives right answer in my compiler I dont know what to now..



#include<iostream.h>

int main()
{
int m,n,i,j,p[100],q[100],range,min,r,k;
long long double result;


while(1)
{
result=1;
cin>>n>>m;
if(n==0 && m==0)break;
else if(m==0) cout<<n<<" things taken "<<m<<" at a time is 1 exactly.\n";
else{
for(i=0;i<m;i++)
{
p=n-i;
q=m-i;
}

for(k=0;k<m;k++)
{
for(j=0;j<m;j++)
{
min=p[j]<q[k]?q[k]:p[j];

for (i=1;i<=min;i++)
{
if(p[j]%i==0 && q[k]%i==0)
{
r=i;
p[j]=p[j]/r;
q[k]=q[k]/r;
}
}
}
}

for(i=0;i<m;i++)
result=result*p;

cout<<n<<" things taken "<<m<<" at a time is "<<result<< " exactly.\n";
}

}



return 0;
}