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

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

WA... help

Post by NaIx » Wed Jun 06, 2007 3:27 am

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

Post by Jan » Wed Jun 06, 2007 11:13 am

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

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

369 WA: tested all cases given above

Post by Suyash.Upadhyay » Tue Jun 12, 2007 7:17 am

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
Last edited by Suyash.Upadhyay on Tue Jun 12, 2007 1:07 pm, edited 1 time in total.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Jun 12, 2007 10:14 am

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.

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

@ little joey

Post by Suyash.Upadhyay » Tue Jun 12, 2007 1:05 pm

Thanx
I got AC.

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

369 - Runtime Error

Post by Jolanda » Fri Dec 21, 2007 11:27 am

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

User avatar
theharshest
New poster
Posts: 20
Joined: Thu Jan 17, 2008 10:47 pm
Location: India

Re: 369 , Why WA ?

Post by theharshest » Wed Jul 16, 2008 10:20 pm

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

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

Re: 369 WA

Post by subzero » Sat Aug 30, 2008 4:19 am

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

Post by KRUNCH » Wed Nov 05, 2008 9:58 am

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

Post by porker2008 » Wed Nov 05, 2008 11:49 am

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

Post by KRUNCH » Wed Nov 05, 2008 11:53 am

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.

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

Post by porker2008 » Wed Nov 05, 2008 1:47 pm

Keep trying...

You will succeed anyway...

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

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

Post by KRUNCH » Wed Nov 05, 2008 10:38 pm

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

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

Post by aliahmed » Tue Nov 18, 2008 10:51 pm

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

Post by tryingbest » Sun Dec 21, 2008 3:23 pm

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

Post Reply

Return to “Volume 3 (300-399)”