10722 - Super Lucky Numbers

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

kathmolla
New poster
Posts: 6
Joined: Tue Nov 30, 2004 2:27 am

how to precalculate

Post by kathmolla » Wed Dec 15, 2004 5:35 pm

How can I precalculate it . I have used string manipulation( big int ) but it takes too much time. The data I think should require big int . Is there any big int implementation that takes less time. or is there any built in data type that can be used.
hey why doing this

User avatar
Mostafiz
New poster
Posts: 3
Joined: Sat Aug 21, 2004 9:49 am
Location: Bangladesh
Contact:

10722 problem

Post by Mostafiz » Thu Mar 31, 2005 9:06 pm

hello boss
i have some problems in 10722

plz help me

the BigNum code need more time. Do u have any berrer solutions:

i send the code:

Code: Select all

#include<iostream>
#include<string>
#include<stdlib.h>
#define BASE 10
#define MAX_DIGIT 231

class BigNum
{

public:
	int digit[MAX_DIGIT];
	void operator =(int);
        void operator =(BigNum &);
	void operator +=(BigNum &);
	void operator +=(int);
	void operator -=(BigNum &);
	void operator -=(int);
	void operator *=(BigNum &);
	void operator *=(int);
	void print(void);
};
void BigNum::operator =(int c)
{
	memset(digit,0,sizeof(digit));
	if(c<BASE)
		digit[0]=c;
        else
	{
            int i=0;
            int temp=c;
            while(temp)
            {
                    digit[i++]=temp%BASE;
                    temp/=BASE;
            }
	}	

}

void BigNum::operator =(BigNum &num)
{

    memcpy(digit,num.digit,sizeof(digit));

}

void BigNum::operator +=(BigNum &num)
{
	int i,carry=0;
	for(i=0;i<MAX_DIGIT;i++)
        {
            carry+=digit[i]+num.digit[i];
            digit[i]=carry%BASE;
            carry/=BASE;
	
	}

}
	
void BigNum::operator +=(int num)
{
	BigNum temp;
	temp=num;
	*this +=temp;
}

void BigNum::operator -=(BigNum &num)
{
	int temp,j;
	BigNum numTemp=num;
	for(int i=0;i<MAX_DIGIT;i++)
        {
            temp=digit[i]-numTemp.digit[i];
            if(temp<0)
            {
                digit[i]=temp+BASE;
                j=i+1;
                temp=1;
                while(temp)
                {
                        temp+=numTemp.digit[j];
                        numTemp.digit[j++]=temp%BASE;
                        temp/=BASE;
                                                
                }
            }
            else
		digit[i]=temp;
		
	}
}

void BigNum::operator -=(int num)
{
    BigNum temp;
    temp=num;
    *this -=temp;
}

void BigNum::operator *=(BigNum &num)
{
	BigNum  mul,sum;
	int i,j,k,carry;
	memset(sum.digit,0,sizeof(sum.digit));
	for(i=0;i<MAX_DIGIT;i++)
        {
            if(!num.digit[i])
		continue;
		
            carry=0;
            k=i;
            memset(mul.digit,0,sizeof(mul.digit));
            for(j=0;j<MAX_DIGIT && k<MAX_DIGIT;j++,k++)
            {
                carry+=(num.digit[i]*digit[j]);
		mul.digit[k]=carry%BASE;
		carry/=BASE;
            }
            
            sum+=mul;
	}
	*this=sum;
}
	
void BigNum::operator *=(int num)
{

    BigNum temp;
    temp=num;
    *this *=temp;

}
	
void BigNum::print(void)
{
    int i,flag=1;
    for(i=MAX_DIGIT-1;i>=0;i--)
    {
        while(digit[i]==0 && flag) i--;
        
        flag=0;
        printf("%d",digit[i]);
    }
    printf("\n");
}

BigNum _pow(int i,int j)
{
    BigNum ret;
    int k;
    ret=1;
    
    for(k=1;k<=j;k++)
            ret*=i;
    
    return ret;

}

int main()
{
    int b,d;
    BigNum t,t1;
//    freopen("In.in","r",stdin);
//    freopen("out.out","w+",stdout);

    while(scanf("%d%d",&b,&d)==2 && b)
    {
        t=_pow(b,d);
        t-=_pow(b,d-1);
        if(d>2)
        {
            t-=_pow(b,d-2);
            t1=_pow(b,d-2);
            t1-=_pow(b,d-3);
            t1*=(d-2);
            t-=t1;
        }
        else
                t-=d-1;
        
        t.print();
    }


return 0;

}

yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

Post by yaro » Fri Apr 01, 2005 11:41 pm

It is not about a big number but the proper solution for this problem (for example some DP...), if you find it, using the big number won't cause TLE.

User avatar
Mostafiz
New poster
Posts: 3
Joined: Sat Aug 21, 2004 9:49 am
Location: Bangladesh
Contact:

Post by Mostafiz » Mon Apr 04, 2005 10:01 am

So the
Big Number is well enough.

but the solution is worng
but it gives Compiler Error.


help

yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

Post by yaro » Tue Apr 05, 2005 6:30 pm

The bug is here:

Code: Select all

void BigNum::operator =(BigNum &num)
{

    memcpy(digit,num.digit,sizeof(digit));

}
Your operator '=' doesn't return a reference to itself - it's useless. My G++ compiler also reports compilation error.


This is the proper use of that operator:

Code: Select all

BigNum& BigNum::operator =(BigNum &num)
{
    memcpy(digit,num.digit,sizeof(digit));
    return *this;
}

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

10722 WA

Post by sunnycare » Fri Jun 03, 2005 5:18 am

http://morse.inf.unideb.hu/~noszaly/xxx ... _10722.tgz
i have check the input/output above..
my prog works right... but judge five me a WA..

Code: Select all

//10722 Super Lucky Numbers
#include <cstdio>
using namespace std;
///////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
#define MAXNUM 999999999
#define BASE 1000000000
#define MAXBIT 30
struct bignum
{
	long val[MAXBIT];
	long len;

};

void add(bignum &a,bignum &b,bignum &sum)
{
	long tmp;
	long n=0;
	if(a.len>b.len)
		tmp=b.len;
	else
		tmp=a.len;
	long i;
	long carry=0;
	for(i=0;i<tmp;i++)
	{
		sum.val[i]=a.val[i]+b.val[i]+carry;
		if(sum.val[i]>MAXNUM)
		{
			sum.val[i]-=MAXNUM+1;
			carry=1;
		}
		else
			carry=0;
	}
	n=tmp;
	for(;i<a.len;i++)
	{
		sum.val[i]=a.val[i]+carry;
		if(sum.val[i]>MAXNUM)
		{
			sum.val[i]-=MAXNUM+1;
			carry=1;
		}
		else
		{
			carry=0;
		}
		n++;
	}
	for(;i<b.len;i++)
	{
		sum.val[i]=b.val[i]+carry;
		if(sum.val[i]>MAXNUM)
		{
			sum.val[i]-=MAXNUM+1;
			carry=1;
		}
		else
		{
			carry=0;
		}
		n++;
	}
	if(carry==1)
	{
		sum.val[i]=1;
		n++;
	}
	sum.len=n;

}
///////////////////////////////////////////
//            assume a>b
//////////////////////////////////////////
void sub(bignum &a,bignum &b,bignum &sub)
{
	long tmp;
	long n=0;
	if(a.len>b.len)
		tmp=b.len;
	else
		tmp=a.len;
	long i;
	long carry=0;
	for(i=0;i<tmp;i++)
	{
		sub.val[i]=a.val[i]-b.val[i]-carry;
		if(sub.val[i]<0)
		{
			sub.val[i]+=BASE;
			carry=1;
		}
		else
			carry=0;
	}
	n=tmp;
	for(;i<a.len;i++)
	{
		sub.val[i]=a.val[i]-carry;
		if(sub.val[i]<0)
		{
			sub.val[i]+=BASE;
			carry=1;
		}
		else
		{
			carry=0;
		}
		n++;
	}
	for(;i<b.len;i++)
	{
		sub.val[i]=b.val[i]-carry;
		if(sub.val[i]<0)
		{
			sub.val[i]+=BASE;
			carry=1;
		}
		else
		{
			carry=0;
		}
		n++;
	}
	if(carry==1)
	{
		sub.val[i]=1;
		n++;
	}
	sub.len=n;

}
///////////////////////////////////////
void mul(bignum &a,bignum &b,bignum &r)
{
	long an=a.len;
	long bn=b.len;
	long i,j;
	long m_carry,a_carry;
	long long tmp;
	for(i=0;i<MAXBIT;i++)
		r.val[i]=0;
	for(i=0;i<an;i++)
	{
		m_carry=0;
		a_carry=0;
		for(j=0;j<bn;j++)
		{
			tmp=(long long)(a.val[i])*(long long)(b.val[j])+m_carry;
			r.val[i+j]+=tmp%BASE+a_carry;
			if(r.val[i+j]>=BASE)
			{
				r.val[i+j]-=BASE;
				a_carry=1;
			}
			else
			{
				a_carry=0;
			}
			m_carry=tmp/BASE;
		}
		r.val[i+j]+=m_carry+a_carry;
	}
	for(i=MAXBIT-1;i>=0;i--)
		if(r.val[i]!=0)
			break;
	if(i>=0)
		r.len=i+1;
	else
		r.len=1;
}

void printNum(bignum &n)
{
	long i=n.len-1;
	printf("%d",n.val[i]);
	for(--i;i>=0;i--)
		printf("%09d",n.val[i]);
}

void convert(char *s,long len,bignum &r)
{
	long tab[10]={1,10,100,1000,10000,100000,1000000,
		10000000,100000000,1000000000};
	long i,j,k;
	long tmp;
	r.len=(len-1)/9+1;
	for(i=0;i<r.len;i++)
	{
		tmp=0;
		for(j=len-i*9-1,k=0;j>len-1-(i+1)*9&&j>=0;j--,k++)
		{
			
			tmp+=tab[k]*(s[j]-'0');
		}
		r.val[i]=tmp;
		
		
	}
			
}
long compare(bignum &a,bignum &b)
{
	//a==b return 0;
	//a>b return 1;
	//a<b return -1;
	long i;
	if(a.len>b.len)
		return 1;
	else
	{
		if(a.len<b.len)
			return -1;
		else
		{
			for(i=a.len-1;i>=0;i--)
			{
				if(a.val[i]>b.val[i])
					return 1;
				else
					if(a.val[i]<b.val[i])
						return -1;
			}
			return 0;
		}
	}

}

void setVal(bignum &a,long v)
{
    a.val[0]=v;
    a.len=1;
}    

bignum r[129][101];
bignum s[129][101];
int main(int argc,char *argv[])
{
    
    bignum t1,t2;
    int b,n;
    for(b=3;b<=128;b++)
    {
        
  	    setVal(r[b][1],b);
  	    setVal(r[b][2],b*(b-1)-1);
  	    setVal(s[b][1],b);
  	    setVal(s[b][2],b*b-1);
  	}
  	
  	for(b=3;b<=128;b++)
  	{
  	    
  	    for(n=3;n<=100;n++)
  	    {
  	        setVal(t1,b-1);
  	        mul(t1,s[b][n-1],t2);
  	        sub(t2,s[b][n-2],r[b][n]);
  	        add(s[b][n-1],r[b][n],s[b][n]);
  	        
  	    }
    }
    
    scanf("%d %d",&b,&n);
    while(n!=0)
    {
        if(n==1)
        	printf("%d",b-1);
       	else
        	printNum(r[b][n]);
        printf("\n");
        scanf("%d %d",&b,&n);
    }
}               
    

thaks

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Fri Jun 03, 2005 10:49 am

I ran a full search on your outputs, and you fail to strip a leading zero from one of your bignums before you print it.

input:

Code: Select all

5 53
0 0
Otherwise all your outputs look ok.

sunnycare
Learning poster
Posts: 74
Joined: Tue Mar 08, 2005 2:35 am
Location: China , Shanghai

Post by sunnycare » Sat Jun 04, 2005 10:32 am

thank you very much
now i got accepted

how can you find that?!

i have solved some problems with that bignum struct..

i think i should rewrite it ...
may be it has other mistakes..

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

Re: 10722 - Super Lucky Numbers

Post by shakil » Fri Feb 12, 2010 6:54 pm

Why WA!!!!!!!! I have checked all the input & output of the board but still WA. Please give me some sample input & output to make my solution AC. Thanks

Code: Select all

#include<stdio.h>
#include<string.h>
char result[509],output[509];
char A[109][3][509];

void mul(char h1[509], long h2)
{

long l,i,hate;

l = strlen(h1);     
 
hate = 0;
for(i=0;i<l;i++)
{
hate += (h1[i] - '0') * h2;
result[i]=hate%10+'0';
hate=hate/10;
}    

while(hate!=0)
{
result[l] = hate%10+'0';
hate=hate/10;
l++;              
}
result[l]=0;     
}

void sum(char h1[509], char h2[509])
{
long l1,l2,l,i,hate;

l1 = strlen(h1);
l2 = strlen(h2);

l = l1;
if(l>l2)
l = l2;

hate=0;
for(i=0;i<l;i++)
{
hate = hate + h1[i] - '0' + h2[i] - '0';
result[i] = hate % 10 + '0';
hate = hate / 10;                
}

for(i=l;i<l1;i++)
{
hate = hate + h1[i] - '0';
result[i] = hate % 10 + '0';
hate = hate / 10;                
}

for(i=l;i<l2;i++)
{
hate = hate + h2[i] - '0';
result[i] = hate % 10 + '0';
hate = hate / 10;                
}

l = l1;
if(l<l2)
l = l2;

while(hate!=0)
{
result[l]=hate%10+'0';
l++;
hate=hate/10;              
}
result[l]=0;
}

int main()
{
long N,B,i,j,k,n;

while(1)    
{    
scanf("%ld %ld",&B,&N);

if(B==0&&N==0)
break;

for(i=0;i<N;i++)
for(j=0;j<2;j++)
strcpy(A[i][j],"0");

strcpy(A[0][1],"1");
output[0]=0;
sprintf(output,"%ld",B-2);
strcpy(A[0][0],output);

/*
if(N==1)
{
sum(A[0][0],"1");
strcpy(A[0][0],result);
}
*/

for(i=0;i<N-1;i++)
{
sum(A[i+1][1],A[i][0]);
strcpy(A[i+1][1],result);              
sum(A[i+1][1],A[i][1]);
strcpy(A[i+1][1],result);
mul(A[i][0],B-1);
strcpy(output,result);
sum(A[i+1][0],output);
strcpy(A[i+1][0],result);
mul(A[i][1],B-2);
strcpy(output,result);
sum(A[i+1][0],output);
strcpy(A[i+1][0],result);
}

strcpy(output,"0");

for(i=0;i<2;i++)
{
sum(output,A[N-1][i]);
strcpy(output,result);                
}

n = strlen(output);

for(i=n-1;i>=0;i--)
printf("%c",output[i]);
printf("\n");    
}    
return 0;    
}
SHAKIL

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10722 - Super Lucky Numbers

Post by plamplam » Fri Dec 16, 2011 9:41 am

Your program produced incorrect output for both these inputs:

Code: Select all

100 100
128 100
0 0
Correct Output:

Code: Select all

9802449187172393445684320037312434586197322829928031
154573622788994506666403435308121275605063788856396567109
341214204216189281001106446450619006029982302442616751647
3555092104882480660536651662255001

518759487775524490960750882557821468268050993870488599029
098922607877598749083976631215968407956986977362467267139
118006611528416193457986219966410354206354583176278015618
0153274878732489659040159075574879443201
Note that I added a blank line in between the two outputs, easier to read :) The judge doesn't require blank lines, don't get confused
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

brainless_the_swiss
New poster
Posts: 5
Joined: Sat Feb 16, 2013 2:19 am

Re: 10722 - Super Lucky Numbers

Post by brainless_the_swiss » Tue Feb 26, 2013 12:09 pm

Dear all,

I would use your help for a very similar challenge :

http://uva.onlinejudge.org/index.php?op ... oblem=3191

I read a few posts before :
You are counting some occurences of 13 more than once
if you say, AB contains 13, and CD are any digit, then CD can also have 13.
Later you calculate again this occurence of 13 at CD !!!

By the way, there is an easy dp recurrence with which you can fill the whole table in O(maxb * maxn * #digits of biggest number)
Hint: you only want to know if at previous position a 1 was used or not. If there was no 1, you can chose any digit at current position.
Can somebody give more details ?

Thanks in advance.

PS: Here is the original post :
http://online-judge.uva.es/board/viewto ... 55&t=72150

Post Reply

Return to “Volume 107 (10700-10799)”