530 - Binomial Showdown

[lendlice]

thanks
i know where is wrong with my code.
and i got ac thanks.

[Joseph Kurniawan]

This code is AC:
[c]
#include<stdio.h>
long double n,k,sum,c;
void main(){
while(1){
scanf("%Lf %Lf",&n,&k);
if(n==0) break;
if(k>n/2) k=n-k;
if(k<2){
if(k==0) printf("1\n");
else printf("%.0Lf\n",n);
}
else{
if(n<2) printf("1\n");
else{
if(n<37){
if(n==35) printf("%.0Lf\n",n);
else{
for(sum=1,c=k;c>0;c--,n--) sum*=n;
for(;k>1;k--) sum/=k;
printf("%.0Lf\n",sum);
}
}
else{
for(sum=1,c=k;c>0;c--,n--) sum*=n;
for(;k>1;k--) sum/=k;
printf("%.0Lf\n",sum);
}
}
}
}
}
[/c]

Check the bold part, this line mean if the n is 35 then the output will always be 35.

[Dominik Michniewski]

that only means that judge has not such case ... and this is not a bug ...

Best regards
DM

[Joseph Kurniawan]

Well, if the judge doesn't have such case, that's a bug alright!

[shahriar_manzoor]

Judge data does not contain all possible input. So it is not a bug.

[Riyad]

i used a very simple algorithm for counting nCr. i used array for solving the problem . cant find any problem , but getting wa all the time . pliiiizzzzzzzzzzzzzzz help . here is my code:---------->

plizzzzzzzzzzzzzzzzzz help me
Bye
Riyad

[yahoo]

I think in your program the output may not fit into long int. You may try with long long int or double. Hope this helps

[Riyad]

used long double instead of long int and got ac . thanx buddy for u help.
Bye
Riyad

[yahoo]

Riyad delete your source code. So that no one can get accepted by changing it.

[Thozz]

Hi there!. This is my code:

Code: Select all

#include <stdio.h>

long double Factorial(int f, int s) {
    if (f < s) return 1;
    else return f*Factorial(f-1, s);    
}

main() {
    long double n, k;
    while ((scanf("%Lf %Lf\n", &n, &k)>0)&&(n>0))
        if (k > 0)
            printf("%.0Lf\n", Factorial(n, n-k+1)/Factorial(k, 1));
        else printf("0\n");
}

While running at home I get a right output, but the judge always answers: Runtime Error (SIGSEGV). Does anyone know what happend?.

[Riyad]

hey man what u tried is purely brute force . when u r counting the factorial it is going beyond the boundary of long double . as a matter u have to find a tricky way to find the NcR.
regards
RIYAD

[Frostina]

why ? ... ^^"

Please help me... T____T

[cpp]
#include <iostream>
using namespace std;
int combi(int n,int m) {
long i,p;
for (i=1,p=1;i<=m;i++)
p = p*(n-i+1)/i;
return p;
}
int main() {
long n,m;
while (cin>>n>>m) {
if (m==0&&n==0) break;
if (m==0) cout << 1 << endl;
else cout << combi(n,m) << endl;
}
return 0;
}
[/cpp]

[sohel]

Hi Frostina,

Remember nCr = n! / ( (r!) * (n-r)!);

So you can either run a loop from r+1 to n or
from n-r+1 to n;

Starting from max( r+1, n-r+1) is certainly better.

I changed this part of your code and got it AC in 0.00 seconds.

And in your combi() function why are you using int n, and int m; when they are long. By the way I think you should use long long.

Hope it helps.

[WR]

Hi,

I'm still new, so the question might be silly- but it's
frustrating anyway.

Recently I switched from Pascal to C, no special reason,
just for fun.

And now I have a problem with a couple of programs.
They all give a wrong answer in 0.000 seconds.

Quote:
"Your program has not solved the problem. It ran during 0.000 seconds."

The main function's always similar, like the one following (Problem 530):

[c]int main(void)
{
long k, n;
unsigned long p;
while (scanf("%ld %ld",&k,&n) == 2)
if ((k > 0) && (n > 0)){
if (k >= n)
p = binom(k,n);
else
p = binom(n,k);
printf("\n%ld",p);
}
return 0;
}[/c]

The programs run ok on my computer!

Do I have a problem with my program, with the e-mail program
or with the OJ?.

Answers are very appreciated!
Thanks in advance.

[CDiMa]

And now I have a problem with a couple of programs.
They all give a wrong answer in 0.000 seconds.

It looks like incorrect input handling or incorrect checking for data termination...

The main function's always similar, like the one following (Problem 530):

[c]int main(void)
{
long k, n;
unsigned long p;
while (scanf("%ld %ld",&k,&n) == 2)
if ((k > 0) && (n > 0)){
[/c]

Two observations:

• -here you discard inputs in the form "n 0" while the problem specification allows for k=0;
  -input is terminated by "0 0", you should check for this and exit, although this shouldn't affect your early termination problem.

[c] if (k >= n)[/c]

This check is redundant since prob specification says explicitly that 0<=k<=n.

[c] p = binom(k,n);
else
p = binom(n,k);
printf("\n%ld",p);
[/c]

here you put a newline at the very beginning of the output and the last line of output isn't terminated.

[c]
}
return 0;
}[/c]

The programs run ok on my computer!

You don't have judge input data, do you?

Do I have a problem with my program, with the e-mail program
or with the OJ?.

In this case it looks like it's your program at fault... as most of the times the problem lies in my programs

Ciao!!!

Claudio