## 10532 - Combination! Once Again

Moderator: Board moderators

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Contact:

### 10532 - Combination! Once Again

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]
Hate WA
Visit phpBB!

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
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!
Kalo mau kaya, buat apa sekolah?

newtype feng
New poster
Posts: 8
Joined: Thu Jul 31, 2003 2:36 pm

### WA!!!!!!!!!!!!

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?
I like AC

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

### Re: WA!!!!!!!!!!!!

newtype feng wrote: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
New poster
Posts: 8
Joined: Thu Jul 31, 2003 2:36 pm

### still wa

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

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
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?
__nOi.m....

newtype feng
New poster
Posts: 8
Joined: Thu Jul 31, 2003 2:36 pm

### i got AC,now

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

### 10532: Combinations again?

Can someone post some inputs/output? Thanks..

Alexander Kozlov
New poster
Posts: 23
Joined: Sun Jun 15, 2003 4:45 pm
Location: Ukraine
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
New poster
Posts: 9
Joined: Thu May 29, 2003 11:37 pm
Location: Poznan

### 10532 WA

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
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
ello

cauchy
New poster
Posts: 9
Joined: Thu May 29, 2003 11:37 pm
Location: Poznan
miras wrote:ello
thanks. I already know where I have a bug . Stupid and hard to find bug, i must say. But, thanks, anyway

chameleons
New poster
Posts: 1
Joined: Sun Jul 11, 2004 4:00 pm

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]

mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia
You should write

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

if you dont wonna meet negative array index.

ehsanulbigboss
New poster
Posts: 32
Joined: Tue Jul 22, 2014 1:17 am