369 - Combinations
Moderator: Board moderators
Rodrigo wrote:Ok, people, there's something REALLY wrong about this problem. I tried tons of different approaches, and I got more W.A.'s than I can remember. But, for each one of them, I couldn't find one single test case for which my solution was wrong.![]()
Anyway, my last desperate attempt was to use a Big Integer data type to calculate. So I did. The main part of the program appears below:
...
void main()
{
int n, m, M, i;
TBigNumber *c = (TBigNumber *) malloc (sizeof(TBigNumber));
TBigNumber *aux = (TBigNumber *) malloc (sizeof(TBigNumber));
scanf("%d %d", &n, &M);
while (n)
{
m = (M > n / 2) ? n - M : M;
InitNumber(c, 1); /* initializes c with "1" */
for (i = 1; i <= m; i++)
{
InitNumber(aux, n - i + 1);
BigMul(c, aux, c); /* multiplies c and aux, result in c */
}
for (i = 1; i < m; i++)
{
InitNumber(aux, m - i + 1);
BigDivMod(c, aux, c, aux); /* divides c by aux, result in c, remainder in aux */
}
printf("%d things taken %d at a time is ", n, M);
for (i = 0; i < c->Size; i++)
printf("%d", c->Digits);
printf(" exactly.\n");
scanf("%d %d", &n, &M);
}
free(c);
free(aux);
}
...
In this last version, I didn't use any trick - it was straight from the formula. It just CAN'T be wrong, I've used this same Big Integer structure lots of times, it is 100% correct. Is there anyone who got "accepted" in this problem and would be willing to send me a text file in the form
<value of N> <value of M> <right answer>
so I can check my program one last time before shooting my computer?
Thanks in advance,
Rodrigo
PS: I won't use your file to create a huge look-up array, I just wanna know what's wrong.
[CORRECT!!]
(intput)
100 90
100 50
99 40
100 6
20 5
18 6
0 0
(output)
1591253560
445776180
445776180
1192052400
15504
18564
(THE TEST DATA WHICH SOMEBODY TOLD ME IS CORRECT)

Picard wrote:if you correct that small mistake i mentioned in hank's source, you will get an accpeted (by the online judge) example.
#include "stdio.h"
void main()
{
unsigned long n,m,c,t;
while(scanf("%lu %lu",&n,&m)==2){
unsigned long i,j; long double cc=1;
if(n==0&&m==0)break;
t=m;
if(n-m<m) m=n-m;
for(i=n,j=(unsigned long)1;j<=m;i--&&j++)
{
cc *=(long double)i;
cc /=(long double)j;
}
c=(unsigned long)cc;
printf("%lu things taken %lu at a time is %lu exactly.\n",n,t,c);
}
}
BUT I STILL GOT W.A.
WHY?
I dont know why i am having problems with this problem. I use the same code that i use in problem 530 and here doesnt work (The only change is that i use BigInt instead of long). Do u know some border cases that i should take care of.
My program works this way with this input:
Thanxs ind advance for your help 
My program works this way with this input:
Code: Select all
100 0
100 things taken 0 at a time is 1 exactly.
100 50
100 things taken 50 at a time is 100891344545564193334812497256 exactly.
100 49
100 things taken 49 at a time is 98913082887808032681188722800 exactly.
100 51
100 things taken 51 at a time is 98913082887808032681188722800 exactly.
100 90
100 things taken 90 at a time is 17310309456440 exactly.
100 10
100 things taken 10 at a time is 17310309456440 exactly.
100 100
100 things taken 100 at a time is 1 exactly.
6 0
6 things taken 0 at a time is 1 exactly.
6 1
6 things taken 1 at a time is 6 exactly.
6 2
6 things taken 2 at a time is 15 exactly.
6 3
6 things taken 3 at a time is 20 exactly.
6 4
6 things taken 4 at a time is 15 exactly.
6 5
6 things taken 5 at a time is 6 exactly.
6 6
6 things taken 6 at a time is 1 exactly.
0 0

I got accepted.
I change my code to use long instead of BigInt thiws way it works. I compare the answer of my two programs and they are exacly the same when the answer fits in long but obviously the result is incorrect when not.
From this i can deduce that the input contains a C(n, k) that doesnt fit in long because that way my program with BigInteger would be correct. So the judge is accepting pragrams that give incorrect answers to the problem and reject the programs who give CORRECT answer to all cases. I dont see the logig behind of this, anybody can explain me?
To the people that is trying this problem. When you are asked the
C(100, 50) you should answer 183430866638381299 instead of the CORRECT answer that it is 100891344545564193334812497256
I change my code to use long instead of BigInt thiws way it works. I compare the answer of my two programs and they are exacly the same when the answer fits in long but obviously the result is incorrect when not.
From this i can deduce that the input contains a C(n, k) that doesnt fit in long because that way my program with BigInteger would be correct. So the judge is accepting pragrams that give incorrect answers to the problem and reject the programs who give CORRECT answer to all cases. I dont see the logig behind of this, anybody can explain me?
To the people that is trying this problem. When you are asked the
C(100, 50) you should answer 183430866638381299 instead of the CORRECT answer that it is 100891344545564193334812497256
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
Can anybody find a mistake in this source? I can't but it gets WA.
[c]// Combinations
#include <iostream.h>
#include <math.h>
int n, k;
int ilprim;
int prim[25];
int ilp[25];
int testno=0;
void gen_smart()
{
int pri, i, j;
prim[0]=2;
prim[1]=3;
ilprim=2;
i=5;
while (i<100)
{
pri=1;
j=0;
while (j<ilprim && (prim[j]<=int(sqrt(i))) && pri)
{
if (i%prim[j] == 0) pri=0;
j++;
}
if (pri)
{
prim[ilprim]=i;
ilprim++;
}
i+=2;
}
}
void addprim(int from, int to, int what, int w)
{
int left=from, right=to, s;
int found=0;
do
{
s = (left+right)/2;
if (prim[s]==what) found=1;
else if (prim[s] < what) left = s+1;
else if (prim[s] > what) right = s-1;
} while (left <= right && !found);
if (found)
ilp[s]+=w;
}
void add(int begin, int end, int change)
{
int i, j, l, pri;
for (i=begin; i<=end; i++)
{
j=0;
pri=1;
while (pri && (prim[j]<=int(sqrt(i)))) // Check if it's prime
{
if (i%prim[j] == 0)
pri=0;
j++;
}
if (!pri) // It's not prime so add it prime divisors
{
j=0;
l=i;
while (l>1 && prim[j]<=i/2)
{
while (l%prim[j] == 0)
{
l = l/prim[j];
ilp[j] += change;
}
j++;
}
}
else // If prime then add it
addprim(0, ilprim, i, change);
}
}
void calculate()
{
int quant=1;
for (int i=0; i<ilprim; i++)
if (ilp)
quant*=int(pow(prim, ilp));
cout << n << " things taken " << k << " at a time is " << quant << " exactly.";
}
int main()
{
gen_smart();
while (cin >> n >> k && (n || k))
{
if (testno) cout << '\n';
for (int i=0; i<ilprim; i++) ilp=0;
add(n-k+1, n, 1);
add(2, k, -1);
calculate();
testno++;
}
return 0;
}[/c]
[c]// Combinations
#include <iostream.h>
#include <math.h>
int n, k;
int ilprim;
int prim[25];
int ilp[25];
int testno=0;
void gen_smart()
{
int pri, i, j;
prim[0]=2;
prim[1]=3;
ilprim=2;
i=5;
while (i<100)
{
pri=1;
j=0;
while (j<ilprim && (prim[j]<=int(sqrt(i))) && pri)
{
if (i%prim[j] == 0) pri=0;
j++;
}
if (pri)
{
prim[ilprim]=i;
ilprim++;
}
i+=2;
}
}
void addprim(int from, int to, int what, int w)
{
int left=from, right=to, s;
int found=0;
do
{
s = (left+right)/2;
if (prim[s]==what) found=1;
else if (prim[s] < what) left = s+1;
else if (prim[s] > what) right = s-1;
} while (left <= right && !found);
if (found)
ilp[s]+=w;
}
void add(int begin, int end, int change)
{
int i, j, l, pri;
for (i=begin; i<=end; i++)
{
j=0;
pri=1;
while (pri && (prim[j]<=int(sqrt(i)))) // Check if it's prime
{
if (i%prim[j] == 0)
pri=0;
j++;
}
if (!pri) // It's not prime so add it prime divisors
{
j=0;
l=i;
while (l>1 && prim[j]<=i/2)
{
while (l%prim[j] == 0)
{
l = l/prim[j];
ilp[j] += change;
}
j++;
}
}
else // If prime then add it
addprim(0, ilprim, i, change);
}
}
void calculate()
{
int quant=1;
for (int i=0; i<ilprim; i++)
if (ilp)
quant*=int(pow(prim, ilp));
cout << n << " things taken " << k << " at a time is " << quant << " exactly.";
}
int main()
{
gen_smart();
while (cin >> n >> k && (n || k))
{
if (testno) cout << '\n';
for (int i=0; i<ilprim; i++) ilp=0;
add(n-k+1, n, 1);
add(2, k, -1);
calculate();
testno++;
}
return 0;
}[/c]
369-combinations why WA?
why do i get WA?
[pascal]program comb(input,output);
var m,n,i,j:byte;
popis:array[1..100,1..2] of boolean;
umnozak:longint;
begin
repeat
readln(n,m);
if (n=0) and (m=0) then halt;
for i:=m+1 to n do
begin
popis[i,1]:=true;
end;
for i:=1 to n-m do
begin
popis[i,2]:=true;
end;
umnozak:=1;
for i:=m+1 to n do
begin
umnozak:=umnozak*i;
popis[i,1]:=false;
for j:=1 to n-m do
begin
if popis[j,2] then
begin
if (umnozak div j=umnozak/j) and
(umnozak > j) then
begin
umnozak:=umnozak div j;
popis[j,2]:=false;
end;
end;
end;
end;
write(n,' things taken ',m,' at a time is ',umnozak,' exactly.');
until (n=0) and (m=0);
end.[pascal][/pascal][/pascal]

[pascal]program comb(input,output);
var m,n,i,j:byte;
popis:array[1..100,1..2] of boolean;
umnozak:longint;
begin
repeat
readln(n,m);
if (n=0) and (m=0) then halt;
for i:=m+1 to n do
begin
popis[i,1]:=true;
end;
for i:=1 to n-m do
begin
popis[i,2]:=true;
end;
umnozak:=1;
for i:=m+1 to n do
begin
umnozak:=umnozak*i;
popis[i,1]:=false;
for j:=1 to n-m do
begin
if popis[j,2] then
begin
if (umnozak div j=umnozak/j) and
(umnozak > j) then
begin
umnozak:=umnozak div j;
popis[j,2]:=false;
end;
end;
end;
end;
write(n,' things taken ',m,' at a time is ',umnozak,' exactly.');
until (n=0) and (m=0);
end.[pascal][/pascal][/pascal]
-
- New poster
- Posts: 22
- Joined: Fri Jan 17, 2003 8:24 am
369 WA
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <io.h>
#include <fcntl.h>
long arr[100],bagi[100];
int main()
{
long n,m,z,temp,k,i,jlh,j,ada,kd,zz,mm,kri;
unsigned long kk;
while (scanf("%d %d\n",&n,&m)!=EOF){
if (n==0&&m==0)break;
for (i=0;i<100;i++)arr=0;
kd=m;
z=n-m;
if (m>z){
temp=z; z=m; m=temp;
}
i=0;
for (k=z+1;k<=n;k++){
arr[i++]=k;
}
jlh=i;
k=0;
for (i=m;i>=2;i--){
ada=1;
for (j=0;j<jlh;j++){
if (arr[j]%i==0){
arr[j]=arr[j]/i;
ada=0;
break;
}
}
if (ada){
kri=i;
for (zz=2;zz<=kri;zz++){
if (kri%zz==0){
for (mm=0;mm<jlh;mm++){
if (arr[mm]%zz==0){
kri=kri/zz;
arr[mm]=arr[mm]/zz;
--zz;
break;
}
}
}
}
if (kri>1)
bagi[k++]=kri;
}
}
ada=1;
for (i=0;i<k;i++){
ada*=bagi;
}
kk=1;
k=1;
for (i=0;i<jlh;i++){
kk=k*=arr;
if (kk>=2147483648){
printf("Detected Error ");
break;
}
}
printf("%d things taken %d at a time is %ld exactly.\n",n,kd,(long)(k/ada));
}
return 0;
}
//@END_OF_SOURCE_CODE
What is my Error ?
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <io.h>
#include <fcntl.h>
long arr[100],bagi[100];
int main()
{
long n,m,z,temp,k,i,jlh,j,ada,kd,zz,mm,kri;
unsigned long kk;
while (scanf("%d %d\n",&n,&m)!=EOF){
if (n==0&&m==0)break;
for (i=0;i<100;i++)arr=0;
kd=m;
z=n-m;
if (m>z){
temp=z; z=m; m=temp;
}
i=0;
for (k=z+1;k<=n;k++){
arr[i++]=k;
}
jlh=i;
k=0;
for (i=m;i>=2;i--){
ada=1;
for (j=0;j<jlh;j++){
if (arr[j]%i==0){
arr[j]=arr[j]/i;
ada=0;
break;
}
}
if (ada){
kri=i;
for (zz=2;zz<=kri;zz++){
if (kri%zz==0){
for (mm=0;mm<jlh;mm++){
if (arr[mm]%zz==0){
kri=kri/zz;
arr[mm]=arr[mm]/zz;
--zz;
break;
}
}
}
}
if (kri>1)
bagi[k++]=kri;
}
}
ada=1;
for (i=0;i<k;i++){
ada*=bagi;
}
kk=1;
k=1;
for (i=0;i<jlh;i++){
kk=k*=arr;
if (kk>=2147483648){
printf("Detected Error ");
break;
}
}
printf("%d things taken %d at a time is %ld exactly.\n",n,kd,(long)(k/ada));
}
return 0;
}
//@END_OF_SOURCE_CODE
What is my Error ?