Page 1 of 1

10329 - Combinatorial Expression

Posted: Fri Jul 26, 2002 12:06 am
I can't find bug in my solution . Could somebody send me some tests ?

Posted: Fri Jul 26, 2002 2:45 am
0 0
1 0
100 50
2 1
30 10
20 10
10 5
1 0
5000 2500
Output:
1
100891344545564193334812497256
22027765045
-1

Posted: Fri Jul 26, 2002 10:01 am
My program wrote correct answer. Here is my code :
[c]
#include <string.h>
#include <math.h>
#include <stdio.h>

#define MAX(a,b)(a<b ? b: a)
#define MIN(a,b)(a<b ? a: b)

#define MAXLC 100
int l1[MAXLC],l3[MAXLC];

char c[]={128,64,32,16,8,4,2,1};

char br[5001]={0};
int rr[5001][80]={{0}};
int ir[5001]={0};

int primes[800],ip;
int count[800];

char t[626]={0};

void gen(char *t){
int p=2,k;
while (p<=5001) {
k=2*p;
while (k<=5001) { t[k/8] |=c[k%8]; k+=p; }
++p;
while (p<=5001 && (t[p/8] & c[p%8])) ++p;
}

}

void sol( int b, int n, int p){
int i,k,ii,j;
for (i=p; i<=n; ++i){
if (br==1) {
if (b==0)
for (k=0; k<ir; ++k)
++count[rr[k]];
else
for (k=0; k<ir; ++k)
--count[rr[k]];
continue;
}
ii=i;
for (j=0; j<ip && ii>1; ++j)
while (ii>1 && !(ii%primes[j])) {
ii/=primes[j];
if (b==0)
++count[j];
else
--count[j];
rr[ir++]=j;
}
br=1;

}
}

int mul(int *l1, int l2, int *l3){
int i,p,s;
memset(l3,0,sizeof(int)*MAXLC);
i=MAXLC-1;
p=0;
while (i>-1){
s = l1*l2+p;
l3=s%10;
p=s/10;
--i;
}
return p>0 ? 1 : 0;
}

void out(int *l){
int i=0;
while (i<MAXLC && !l[i]) ++i;
while (i<MAXLC){
printf("%d",l[i]);
++i;
}
printf("\n");
}

int main(){
int i,n,m,j,a,b,cd;
gen(t);
ip=0;
for (i=2; i<=5000;++i)
if (!(t[i/8] &c[i%8]) ){ primes[ip++]=i;
}
while (scanf("%d %d",&n,&m)!=EOF){
cd=1;
memset(count,0,ip *sizeof(int));
for (i=0;i<n;++i){
scanf("%d %d",&a,&b);
sol(0,a,MAX(a-b,b)+1);
sol(1,MIN(b,a-b),2);
}

for (i=0;i<m;++i){
scanf("%d %d",&a,&b);
sol(1,a,MAX(a-b,b)+1);
sol(0,MIN(b,a-b),2);
}
memset(l1,0,sizeof(int)*MAXLC);
l1[MAXLC-1]=1;
for (i=0;i<ip && cd ; ++i){
if (count[i]<0) {
printf("0\n");
cd=0;
}
for (j=0; j<count[i] && cd ;++j) {
if (mul(l1,primes[i],l3)){
printf("-1\n");
cd=0;
}
if (cd)
memcpy(l1,l3,sizeof(int)*MAXLC);
}
}
if (cd)
out(l1);
}
return 0;
}

[/c]

Posted: Fri Jul 26, 2002 5:40 pm
Fixed. Thank you Adrian for quick help .

WAAAAAAAAAAAAAAAAAA

Posted: Fri Sep 16, 2005 6:13 pm
i amm getting WA(i checked the above once... okk)
so i need some MORE
thanks

Posted: Wed Sep 21, 2005 12:50 pm
here is my wa soln.

Code: Select all

``````#include <stdio.h>
#include <math.h>
#include <string.h>

#define Max_2(a,b) ( ((a)>(b))?(a):(b) )
#define Max_3(a,b,c) Max_2(a, Max_2(b,c) )

const int LIMIT = 5005, SIZE = 700, MAX = 500*10;
int primes[SIZE], prime_num;

int left[SIZE];
bool is_prime[LIMIT];
char a[MAX/10], b[MAX],p[MAX], result[MAX];

void reverse_int(int n, int index){
if(n){
reverse_int(n/10, index+1);
a[index] = (n%10) + '0';
}
else
a[index] = 0;
}

void seive2(int limit)
{
int i, j, k, loop;
memset( is_prime, 1, sizeof(is_prime) );is_prime[0] = 0;

//Assign '0' for all composite numbers.
for(i = 3, loop = (int)sqrt(limit); i <= loop; i += 2)
{
if (is_prime[(i - 1) >> 1]){
for(j = i, k = limit / i; j <= k; j += 2)
if ( is_prime[(i * j - 1)>>1] ) is_prime[(i * j - 1)>>1] = 0;
}
}

//Collect the primes.
primes[0] = 2;
for(i = 3, prime_num = 1; i <= limit; i += 2){
if ( is_prime[(i - 1)>>1] ) primes[prime_num++] = i;
}
}

void calc_plus(int n){
int i,j, k;
for(i = 0; primes[i]<=n; i++){
j = n; k = 0;
while( j ){
k += (j/=primes[i]);
}
left[ i ] += k;
}
}

void calc_minus(int n){
int i,j,k;
for(i = 0; primes[i]<=n; i++){
j = n; k = 0;
while( j ){
k += (j/=primes[i]);
}
left[ i ] -= k;
}
}

#define swap(a,b) (a)^=(b)^=(a)^=(b)
void strrev( char str[],int j){
int i = 0;
for( ;j-i>i; ){
swap(str[i], str[j-i] );
i++;
}
}

void sum(char s1[], char s2[]){
int i=0, sum, carry=0;
while( s1[i] && s2[i] ){
sum = carry + (s1[i]-'0') + (s2[i]-'0') ;
s1[i] = (sum%10) + '0';
carry = sum/10;
i++;
}
if(s1[i] ){
while( s1[i] ){
sum = carry + (s1[i]-'0');
s1[i] = (sum%10) + '0';
carry = sum/10;
i++;
}
}
else{
while( s2[i] ){
sum = carry + (s2[i]-'0');
s1[i] = (sum%10) + '0';
carry = sum/10;
i++;
}
}
while( carry ){
s1[i++ ] = (carry%10)+'0';
carry /= 10;
}
/*
if( carry )
s1[i++] = carry+'0';
*/
s1[i] = 0;
}

void multiply(char res[], char b[], int r, int with){
int i, sum, carry;
for(carry = i = 0; b[i]; i++){
sum = carry + (b[i]-'0')*with ;
res[i+r] = (sum%10) + '0';
carry = sum/10;
}
while( carry ){
res[i++ + r ] = (carry%10)+'0';
carry /= 10;
}
res[i+r] = 0;
}

char aux[MAX];

int Mul(char p[], char a[]){
int i;
multiply( aux,p, 0, a[0]-'0');
result[0] = '0';
for(i = 1; a[i]; i++){
multiply( result,p, i, a[i]-'0');
sum( aux, result );
/* for the next line */
result[i] = '0';
}
//strcpy(p,aux);
for(i = 0; aux[i]; i++)p[i] = aux[i]; p[i] = 0;
return i-1;
}

int len;
void pow_(int expo){
if( expo ^ 1 ){
if( expo&1 ){
pow_( expo-1 );
(len<100)? (len = Mul(p,a)) : 0;
}
else{
pow_( expo>>1 );
(len<100)? (len = Mul(p,p) ) : 0;
}
}
else
strcpy(p,a);
}

void mul_operation(int max){
int i;
len = 0; b[0] = '1';b[1] = 0;

for(i = 0; primes[i]<=max; i++){

if( left[i] ){
if( left[i]<0 ){
puts("0");
return ;
}
else if( len > 99 ){
puts("-1");
return ;
}
reverse_int(primes[i], 0);

p[0] = '1';
pow_( left[i] );

if( len > 99 ){
puts("-1");
return ;
}
len = Mul(b,p);
}
}
strrev( b, strlen(b)-1 );
puts(b);
}

void main(void){
//freopen("d:\\a\\10329.txt","rb",stdin);

int M,N, i, n,r, max;

seive2(LIMIT-1);

while( 2 == scanf("%d %d", &M,&N) ){
max = 0;
for(i = 0; i<M; i++){
scanf("%d %d", &n,&r);
/* n!/r!*(n-r)! */
calc_plus(n); calc_minus(r); calc_minus(n-r);

max = Max_3(max,n,r);
}
for(i = 0; i<N; i++){
scanf("%d %d", &n,&r);
/* r!*(n-r)!/n! */
calc_plus(r); calc_plus(n-r); calc_minus(n);

max = Max_3(max,n,r);
}

mul_operation(max);

memset(left,0,sizeof(int)*(max+1) );
}
}
``````

Posted: Thu Mar 09, 2006 11:01 am
Can anybody post some testcases? I got WA and I don't know why. This problem should be a very easy but ...
come on...

Posted: Sun Mar 12, 2006 1:02 am
No problem. I did a very bad mistake. I got it!

Posted: Fri Feb 23, 2007 2:49 pm
I'm always getting WA..... >_< My BigInteger operation looks okay, so.....

Input:
1 2
1 1
2 2
3 3
1 2
5 5
1 1
2 1
1 1
340 170
2 2
1 1
336 168
4 4
Output:
1
0
-1
6088717586293958420919965582862840857932876070583068946752913884253601825766708971967140661846856600

Posted: Fri Feb 23, 2007 4:21 pm
I get the same output as you.

Posted: Fri Feb 23, 2007 5:15 pm
Thank you.

I've just got accepted. My mistake was not reading the problem statement properly. :p

Re: 10329 - Combinatorial Expression

Posted: Wed Sep 09, 2009 5:07 am
Somebody please help! I took nearly two hours to code the solution to this problem. It gives WA
I would greatly appreciate anybody who can give me some inputs!!!

Code: Select all

``````#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;
int main()
{
bool flags[5005],flag;
int i,j,prime[675],k=-1,temp,primefact[5005][15],num,den,pc[5005],n,r,len1,len2,val,carry;
char ans[120],str2[120],str1[7];
memset(flags,1,5005);

for(i=2;i<5002;++i)
if(flags[i])
{
prime[++k]=i;
if(i<75)
for(j=i*i;j<5005;flags[j]=0,j+=i);
}

for(i=2;i<5002;++i)
{
for(temp=i,j=k=0;temp!=1;++j)
if(temp%prime[j]==0)
{
primefact[i][k++]=prime[j];
temp/=prime[j--];
}
primefact[i][k]=0;
}

while(scanf("%d%d",&num,&den)==2)
{
for(i=0;i<669;pc[prime[i]]=0,++i);

for(i=0;i<num;++i)
{
scanf("%d%d",&n,&r);
if(r>(n<<1))
r=n-r;
for(j=0;j<r;++j,--n)
for(k=0;primefact[n][k];++pc[primefact[n][k]],++k);
for(j=2;j<=r;++j)
for(k=0;primefact[j][k];--pc[primefact[j][k]],++k);
}
for(i=0;i<den;++i)
{
scanf("%d%d",&n,&r);
if(r>(n<<1))
r=n-r;
for(j=0;j<r;++j,--n)
for(k=0;primefact[n][k];--pc[primefact[n][k]],++k);
for(j=2;j<=r;++j)
for(k=0;primefact[j][k];++pc[primefact[j][k]],++k);
}

for(i=0;i<699&&pc[i]>=0;++i);
if(i!=699)
{
cout<<"0\n";
continue;
}

for(flag=1,ans[0]='1',ans[j=1]='\0',i=0;flag&&i<669;++i)
if(pc[prime[i]])
{
for(temp=prime[i],len1=-1;temp;temp/=10)
str1[++len1]=temp%10+'0';
str1[++len1]='\0';

for(j=0;j<len1-1;str2[j]='0',++j);
for(k=0;ans[k];++k)
str2[j++]=ans[k];
len2=j;

for(j=0;j<len1-1;str2[len2+j]='0',++j);
str2[len2=(len2+j)]='\0';

for(carry=0,j=0;j<=len2-len1;++j)
{
for(val=carry,k=0;k<len1;++k)
val+=((str2[j+k]-'0')*(str1[len1-1-k]-'0'));
ans[j]=val%10+'0';
if(j==100)
{
flag=0;
break;
}
carry=val/10;
}

while(flag&&carry)
{
ans[j++]=carry%10+'0';
if(j>=101)
{
flag=0;
break;
}
carry/=10;
}
ans[j]='\0';
--pc[prime[i]],--i;
}
if(!flag||j>100)
cout<<"-1\n";
else
{
for(--j;j>=0;putchar(ans[j]),--j);
putchar('\n');
}
}
return 0;
}
``````