## 369 - Combinations

Moderator: Board moderators

NaIx
New poster
Posts: 4
Joined: Sat Jun 02, 2007 5:49 pm
Location: indonesia

### WA... help

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
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.
Ami ekhono shopno dekhi...
HomePage

New poster
Posts: 5
Joined: Sat Jun 02, 2007 6:03 pm

### 369 WA: tested all cases given above

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

Suyash
Last edited by Suyash.Upadhyay on Tue Jun 12, 2007 1:07 pm, edited 1 time in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
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).
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

New poster
Posts: 5
Joined: Sat Jun 02, 2007 6:03 pm

### @ little joey

Thanx
I got AC.

Jolanda
New poster
Posts: 2
Joined: Fri Dec 21, 2007 11:17 am

### 369 - Runtime Error

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 {

while (true) {
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
New poster
Posts: 20
Joined: Thu Jan 17, 2008 10:47 pm
Location: India

### Re: 369 , Why WA ?

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;
}
}
``````
"if u r goin thru hell, keep goin"

subzero
New poster
Posts: 26
Joined: Mon Aug 15, 2005 5:21 am

### Re: 369 WA

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...
There is no knowledge that is no power.

KRUNCH
New poster
Posts: 8
Joined: Sun May 18, 2008 1:03 pm

### 369 WA even if it works for every test case i found :S

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
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

### Re: 369 WA even if it works for every test case i found :S

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.
``````
Last edited by porker2008 on Wed Nov 05, 2008 11:54 am, edited 1 time in total.

KRUNCH
New poster
Posts: 8
Joined: Sun May 18, 2008 1:03 pm

### Re: 369 WA even if it works for every test case i found :S

porker2008 wrote: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.

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
New poster
Posts: 21
Joined: Wed Oct 08, 2008 7:04 am

### Re: 369 WA even if it works for every test case i found :S

Keep trying...

You will succeed anyway...

KRUNCH
New poster
Posts: 8
Joined: Sun May 18, 2008 1:03 pm

### Re: 369 WA even if it works for every test case i found :S

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
New poster
Posts: 24
Joined: Fri Oct 24, 2008 8:37 pm
Contact:

### Re: 369 WA even if it works for every test case i found :S

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
New poster
Posts: 1
Joined: Sun Dec 21, 2008 3:13 pm

### Plz help me in 369..i am getting WA..plz

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;
}