10532 - Combination! Once Again

[Jewel of DIU]

Hai everybody. Any one tell me why this code got WA:
[# include <stdio.h>

double fact(double a)
{
double i,b;
b = 1;
for( i = 1; i <= a; i++)
{
b = b*i;
}
return b;
}
int main()
{
double a,b,c,n,r,t,out,d;
long cas = 0,j,i;
char cls, grb[1000];

while(scanf("%lf %lf%c",&n,&t,&cls)==3)
{
if(n == 0) break;
a = fact(n); /* nCr = n! / { (n-r)! * r! } */
gets(grb);

printf("Case %ld:\n",cas+1);

for(j = 0; j < t; j++)
{
scanf("%lf",&r);
b = fact(r);
c = fact(n-r);
d = b*c;
out = a/d;
printf("%0.0lf\n",out);
}
cas++;
}
return 0;
}
][c]
I use nCr to calculate the combination.[/c][/code]

[titid_gede]

try this input :

Code: Select all

5 1
1 1 1 3 3
2
0 0

output should be:

Code: Select all

Case 1:
3

hope this help & good luck!

[newtype feng]

for this input my code can output the right answer,but i still got WA.
this is my code
[cpp]#include<iostream.h>
long k=0,b[50]={0},a[50];
long res[60][60];
long f( long k, long r)
{
long re=0;
long i;
if(k==0)
{
if(r>a[k])
return 0;
else
return 1;
}
if(r==1)
return k+1;

for(i=0;i<=a[k];i++)
{
if(r-i==0)
{
re+=1;
continue;
}
if(r-i<0)
continue;
if(res[k-1][r-i]==-1)
{
res[k-1][r-i]=f(k-1,r-i);
}
re+=res[k-1][r-i];
}
return re;
}
long doit( long n, long m)
{
long i,j,tmp;
char s[1000];
for(i=0;i<50;i++)
{
b=0;
a=0;
}
k=0;
for(i=0;i<60;i++)
for(j=0;j<60;j++)
res[j]=-1;
for(i=0;i<n;i++)
{
cin>>tmp;
for(j=0;j<k;j++)
if(b[j]==tmp)
{
a[j]++;
break;
}
if(j==k)
{
a[k]=1;
b[k]=tmp;
k++;
}
}
// cin.getline(s,1000);
for(i=0;i<m;i++)
{
cin>>tmp;
cout<<f(k-1,tmp)<<endl;
}
// cin.getline(s,1000);
return 0;
}
long main()
{
long n,k,i=1;
cin>>n>>k;
while(n||k)
{
cout<<"Case "<<i<<":"<<endl;
doit(n,k);
cin>>n>>k;
i++;
}
return 0;
}[/cpp]
can some body help me?

[windows2k]

for this input my code can output the right answer,but i still got WA.
this is my code
[cpp]omit[/cpp]
can some body help me?

try to use long long int instead of long

[newtype feng]

i have tried long long.but still WA.
is there some more sample test case?

[Noim]

newtype feng,

i have solved this problem first. then i make a input file randomly having 100000 input case with maximum value of all "r". i found no dis-similarty between your output and mine. then i change your code: "cin" and "cout" with scanf() and printf() respectively, the interesting matter is that i got AC with your code. changing only those!!! ( i also use "long long int"instead of your usning only "long")

isn't it very funny?

if you want i can pm to you with your modified code.

take care.

PS: one thing. i didn't submit your code directly. i don't know if your above code show really WA or not?

[newtype feng]

thank you!
i got AC now.
it is really strange,but i really don't then different between cin,cout and printf ,scanf

[Larry]

Can someone post some inputs/output? Thanks..

[Alexander Kozlov]

Input:

4 4
2 2 3 3
1 2 3 4
5 5
1 2 3 3 3
1 2 3 4 5
4 4
2 2 2 2
1 2 3 4
10 5
1 4 2 3 5 4 3 4 5 7
2 3 4 5 6
20 10


1 2 3 2 4 6 5 6 7 9 14 7 13 17 19 11 12 16 18 1
1 2 3 4 5 6 7 8 9 10
0 0

Output:

Case 1:
2
3
2
1
Case 2:
3
4
4
3
1
Case 3:
1
1
1
1
Case 4:
18
36
53
60
53
Case 5:
16
124
620
2246
6272
14018
25688
39209
50348
54692

[cauchy]

Could somebody give me carrect output for this input? I am really mad about this problem. What's the trick?

4 1
1 1 2 2
2

5 2
1 2 3 4 5
2 1

4 1
1 2 3 4
2

1 0
1

5 2
1 2 2 2 5
0 1

50 50
1 2 2 2 2 2 2 3 3 3 4 2 1 2 3 4 5 6 7 9 50 1 2 3 4 2 1 2 3 2 2 5 9 8 5 4 3 2 9 49 29 24 2 2 6 9 9 9 9 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

50 50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

50 50
1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

0 0

My output is:

Case 1:
3
Case 2:
10
5
Case 3:
6
Case 4:
Case 5:
1
3
Case 6:
13
85
376
1275
3553
8501
17990
34399
60396
98601
151186
219474
303596
402261
512696
630809
751590
869691
980054
1078428
1161651
1227661
1275298
1304014
1313602
1304014
1275298
1227661
1161651
1078428
980054
869691
751590
630809
512696
402261
303596
219474
151186
98601
60396
34399
17990
8501
3553
1275
376
85
13
1
Case 7:
1
50
1225
19600
230300
2118760
15890700
99884400
536878650
2505433700
10272278170
37353738800
121399651100
354860518600
937845656300
2250829575120
4923689695575
9847379391150
18053528883775
30405943383200
47129212243960
67327446062800
88749815264600
108043253365600
121548660036300
126410606437752
121548660036300
108043253365600
88749815264600
67327446062800
47129212243960
30405943383200
18053528883775
9847379391150
4923689695575
2250829575120
937845656300
354860518600
121399651100
37353738800
10272278170
2505433700
536878650
99884400
15890700
2118760
230300
19600
1225
50
Case 8:
1
25
325
2900
19850
110630
520950
2125200
7646925
24597925
71473765
189147400
458917850
1026360050
2125371350
4090293780
7338519150
12306291450
19331110150
28496073100
39478598170
51465297950
63191778950
73133433800
79818194925
82176836301
79818194925
73133433800
63191778950
51465297950
39478598170
28496073100
19331110150
12306291450
7338519150
4090293780
2125371350
1026360050
458917850
189147400
71473765
24597925
7646925
2125200
520950
110630
19850
2900
325
25

[miras]

ello
your output is OK!!!!!!!!!!!

[cauchy]

ello
your output is OK!!!!!!!!!!!

thanks. I already know where I have a bug . Stupid and hard to find bug, i must say. But, thanks, anyway

[chameleons]

Hi, could you please help me? I am sure my recurrence formula is correct. I get the same output for your input, but I get WA. Maybe I have the same stupid bug as u.
[cpp]
#include <iostream.h>

void main()
{
int m, n, data[51], r[50], i, j, k, counter, temp;
unsigned long long tab[51][51];

counter = 1;
while(true){
cin>>n>>m;
if(n==0)break;
for(i=0; i<=50; i++)data = 0;
for(i=1; i<=n; i++){
cin>>temp;
data[temp]++;
}
for(j=0; j<m; j++) cin>>r[j];

for(i=1; i<=n; i++) tab[0] = 0;
for(i=0; i<=n; i++) tab[0] = 1;
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
tab[j] = tab[j-1];
for(k=1; k<=data[j]; k++){
tab[j] += tab[j-1][i-k];
}
}
}
cout<<"Case "<<counter<<":\n";
for(i=0; i<m; i++) cout<<tab[n][r]<<endl;
counter++;
}
}
[/cpp]
Above is my code. Could u please help me check? Thanks a lot!!!!

[mlvahe]

You should write

for (k = 1; k <= min(i,data); k++)

if you dont wonna meet negative array index.

[ehsanulbigboss]

Anyone Please help me to solve the problem?