10329 - Combinatorial Expression

[prom]

I can't find bug in my solution . Could somebody send me some tests ?

[Adrian Kuegel]

0 0
1 0
100 50
2 1
30 10
20 10
10 5
1 0
5000 2500
Output:
1
100891344545564193334812497256
22027765045
-1

[prom]

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]

[prom]

Fixed. Thank you Adrian for quick help .

[I LIKE GN]

i amm getting WA(i checked the above once... okk)
so i need some MORE
please helppppppp
thanks

[I LIKE GN]

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) );
	}
}

thanks in advannce...

[Moha]

Can anybody post some testcases? I got WA and I don't know why. This problem should be a very easy but ...
come on...

[Moha]

No problem. I did a very bad mistake. I got it!

[Observer]

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

Is that correct? Please help...

[mf]

I get the same output as you.

[Observer]

Thank you.

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

[abhiramn]

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;
}