11533 - Special Number

[SerailHydra]

I got WA for times.
Can anyone tell me that in which case the answer should be 'No solution'? Or give some test?

[altertain]

Leading zeroes are allowed.

[SerailHydra]

Thanks, I got AC, and I just neglect this input:

2 0 0

the answer is 0, not 'No solution'.

[Chimed]

Yes it can be such test.
I assume that in N-base number, maximum length of the special number is N^2.
So i loop at most N^2 times and checks it can be generated if not prints out "I give up "

[H_Hima]

Hi
All of the previews bug + some other one had been considered in the contest but I got Run Time Error.

may any one help me to solve this problem.

thanks a lot.

Code: Select all

#include<iostream>
#include<fstream>
#include<string>
using namespace std;

#define MAXSIZE 40100

class BigInt {
public:
	char *data;
	int size;
	bool sign;
	BigInt()	{	data=NULL;	size=0;	sign=true;	}
	BigInt(long long);
	BigInt(char *);
	BigInt(BigInt &);
	BigInt& operator=(BigInt &);
	BigInt& operator=(char*);
	BigInt& operator=(long long);
	~BigInt();
};

BigInt::BigInt(long long num) {
	if(num==0) {
		size=0;
		data=NULL;
		sign=true;
		return;
	}
	char temp[MAXSIZE];
	int i=0;
	sign=true;
	if(num<0) {
		sign=false;
		num*=-1;
	}
	for(i=0;num;i++) {
		temp[i]=num%10+48;
		num/=10;
	}
	temp[i]=0;
	size=i;
	data=new char[i+1];
	for(i=0;i<=size;i++)
		data[i]=temp[i];
}

BigInt::BigInt(char *num) {
	int i=0,j;
	sign=true;
	if(num[0]=='-') {
		sign=false;
		i=1;
	}
	while(num[i]=='0')	i++;
	if(num[i]==0) {
		size=0;
		data=NULL;
		sign=true;
		return;
	}
	for(size=0,j=i;num[j];size++,j++);
	data=new char[size+1];
	for(j=1;j<=size;i++,j++)
		data[size-j]=num[i];
	data[size]=0;
}

BigInt::BigInt(BigInt &other) {
	sign=other.sign;
	size=other.size;
	if(other.data==NULL) {
		data=NULL;
		return;
	}
	data=new char[other.size+1];
	int i;
	for(i=0;other.data[i];i++)
		data[i]=other.data[i];
	data[i]=0;
}

BigInt::~BigInt() {
	if(data)
		delete[] data;
}

BigInt& BigInt::operator=(BigInt &other) {
	if(data)
		delete[] data;
	sign=other.sign;
	size=other.size;
	if(other.data==NULL) {
		data=NULL;
		return (*this);
	}
	data=new char[other.size+1];
	int i;
	for(i=0;other.data[i];i++)
		data[i]=other.data[i];
	data[i]=0;
	return (*this);
}

BigInt& BigInt::operator=(long long num) {
	if(data)
		delete[] data;
	if(num==0) {
		size=0;
		data=NULL;
		sign=true;
		return *this;
	}
	char temp[MAXSIZE];
	int i=0;
	sign=true;
	if(num<0) {
		sign=false;
		num*=-1;
	}
	for(i=0;num;i++) {
		temp[i]=num%10+48;
		num/=10;
	}
	temp[i]=0;
	size=i;
	data=new char[i+1];
	for(i=0;i<=size;i++)
		data[i]=temp[i];
	return *this;
}

BigInt& BigInt::operator=(char* num) {
	if(data)
		delete[] data;
	int i=0,j;
	sign=true;
	if(num[0]=='-') {
		sign=false;
		i=1;
	}
	while(num[i]=='0')	i++;
	if(num[i]==0) {
		size=0;
		data=NULL;
		sign=true;
		return *this;
	}
	for(size=0,j=i;num[j];size++,j++);
	data=new char[size+1];
	for(j=1;j<=size;i++,j++)
		data[size-j]=num[i];
	data[size]=0;
	return *this;
}

/////////////////////////////////////////////////////////////////////////////////////////
bool operator<(BigInt &,BigInt &);
bool operator>(BigInt &,BigInt &);
bool operator==(BigInt &,BigInt &);
void BigAdd(BigInt &,BigInt &,BigInt &);
void BigSub(BigInt &,BigInt &,BigInt &);
void BigMul(BigInt,BigInt,BigInt &);
long long BigDiv(BigInt ,long long,BigInt &);
int BigRem(BigInt &,long long);
/////////////////////////////////////////////////////////////////////////////////////////

bool operator<(BigInt &a,BigInt &b) {
	if(a.sign!=b.sign) {
		if(b.sign)
			return true;
		return false;
	}
	if(a.size!=b.size) {
		if((b.size>a.size)&&a.sign)
			return true;
		if((b.size<a.size)&&a.sign==false)
			return true;
		return false;
	}
	int i;
	for(i=a.size-1;i>=0;i--) {
		if(a.data[i]!=b.data[i]) {
			if((b.data[i]>a.data[i])&&a.sign)
				return true;
			if((b.data[i]<a.data[i])&&!a.sign)
				return true;
			return false;
		}
	}
	return false;
}

bool operator>(BigInt &a,BigInt &b) {
	return (b<a);
}

bool operator==(BigInt &a,BigInt &b) {
	if(a.sign!=b.sign||a.size!=b.size)
		return false;
	int i;
	for(i=0;i<a.size;i++)
		if(a.data[i]!=b.data[i])
			return false;
	return true;
}

void BigAdd(BigInt &a,BigInt &b,BigInt &Res) {
	if(a.size==0) {
		Res=b;
		return;
	}
	if(b.size==0) {
		Res=a;
		return;
	}
	int i,pos,max=a.size,carry=0;
	if(a.sign==b.sign) {
		if(b.size>a.size)	max=b.size;
		char res[MAXSIZE];
		res[max+2]=0;
		for(i=0,pos=max+1;i<max;i++,pos--) {
			res[pos]=carry;
			if(i<a.size)
				res[pos]+=a.data[i]-48;
			if(i<b.size)
				res[pos]+=b.data[i]-48;
			carry=res[pos]/10;
			res[pos]%=10;
			res[pos]+=48;
		}
		if(carry) {	
			res[pos]='1';
			--pos;
		}
		if(!a.sign) {
			res[pos]='-';
			--pos;
		}
		Res=(res+pos+1);
		return;
	}
	b.sign=a.sign;
	BigSub(a,b,Res);
}

void BigSub(BigInt &a,BigInt &b,BigInt &Res) {
	if(b.size==0) {
		Res=a;
		return;
	}
	if(a.size==0) {
		b.sign=!b.sign;
		Res=b;
		return;
	}
	BigInt *A=&a,*B=&b;
	bool si;
	int i,carry=0,pos;
	if(a.sign==b.sign) {
		char res[MAXSIZE];
		si=a.sign;
		a.sign=b.sign=true;
		if(a<b) {
			si=!si;
			A=&b;
			B=&a;
		}
		res[A->size+1]=0;
		for(i=0,pos=A->size;i<A->size;i++,pos--) {
			res[pos]=(A->data[i]-48);
			res[pos]+=carry;
			if(i<B->size)	res[pos]-=(B->data[i]-48);
			if(res[pos]<0) {
				carry=-1;
				res[pos]+=10;
			}
			else
				carry=0;
			res[pos]+=48;
		}
		++pos;
		while(pos<=A->size&&res[pos]=='0')	++pos;
		if(res[pos]==0)
			Res="";
		if(!si) {
			--pos;
			res[pos]='-';
		}
		Res=(res+pos);
		return;
	}
	b.sign=a.sign;
	BigAdd(a,b,Res);
}

void BigMul(BigInt a,BigInt b,BigInt &Res) {
	if(a.size==0||b.size==0) {
		Res="";
		return;
	}
	bool si=(a.sign==b.sign);
	if(a.size==1&&a.data[0]=='1') {
		b.sign=si;
		Res=b;
		return;
	}
	if(b.size==1&&b.data[0]=='1') {
		a.sign=si;
		Res=a;
		return;
	}
	char res[MAXSIZE];
	int i,j,carry,pos,len=a.size+b.size+1;
	for(j=0,i=len;j<a.size;j++,i--) {
		res[i]=0;
		a.data[j]-=48;
	}
	for(j=0;j<b.size;i--,j++) {
		res[i]=0;
		b.data[j]-=48;
	}
	for(i=0,pos=len-1;i<a.size;i++,pos--) {
		carry=0;
		for(j=0;j<b.size;j++) {
			res[pos-j]+=a.data[i]*b.data[j]+carry;
			carry=res[pos-j]/10;
			res[pos-j]%=10;
		}
		if(carry)
			res[pos-j]=carry;
	}
	if(carry==0)
		pos++;
	for(i=pos-j+1;i<len;i++)
		res[i]+=48;
	if(!si) {
		res[pos-j]='-';
		pos--;
	}
    Res=(res+pos-j+1);
}

long long BigDiv(BigInt a,long long b,BigInt &Res) {
	if(b==0)
        return -1;
    long long num=0;
	int i,pos=0;
	char res[MAXSIZE];
	for(i=a.size-1;num<b&&i>=0;i--) {
		num*=10;
		num+=a.data[i]-48;
	}
	while(num>=b) {
		res[pos]=num/b+48;
		num%=b;
		pos++;
		for(;num<b&&i>=0;i--) {
			num*=10;
			num+=a.data[i]-48;
			if(num<b) {
				res[pos]='0';
				pos++;
			}
		}
	}
	res[pos]=0;
	Res=res;
	return num;
}

int BigRem(BigInt &a,int b) {
	int num=0,i,pos=0;
	for(i=a.size-1;num<b&&i>=0;i--) {
		num*=10;
		num+=a.data[i]-48;
	}
	while(num>=b) {
		num%=b;
		pos++;
		for(;num<b&&i>=0;i--) {
			num*=10;
			num+=a.data[i]-48;
			if(num<b)
				pos++;
		}
	}
	return num;
}

void print(BigInt &num,long long b,int si) {
	int rem;
	int zz=0;
	BigInt tt,z;
	z=zz;
	int temp[1000],i=0;
	while(!(num==z)) {
		rem=BigDiv(num,b,tt);
		num=tt;
		temp[i++]=rem;
	}
	rem=i;
	while(rem<=si) {
		cout<<" 0";
		rem++;
	}
	while(i--) {
		cout<<" "<<temp[i];
	}
	cout<<endl;
}

int main() {
	BigInt A,B,C,P,temp,X,Y,N,T2,P2;
	int i,j,k,l,t=1;
	int x,y,n,T,mx;
	while(cin>>n>>x>>y) {
		T=y*n-1;
		P2=n;
		P=1;

		X=x;
		Y=y;
		N=n;
		T2=x*y;
		
		mx=10*n;

		cout<<"Case "<<t++<<":";

		if(y==0) {
			if(x==0) {
				cout<<" 0"<<endl;
				continue;
			}
		}

		if(x>=n||x<=0||y<=0) {
			i=mx+1;
			goto end;
		}

		for(i=0;i<=mx;i++) {
			BigMul(P,X,A);
			if(A<T2)
				goto next;
			BigSub(A,T2,A);
			if(BigDiv(A,T,A)==0) {
				BigMul(A,N,A);
				BigAdd(A,X,A);
				print(A,n,i);
				break;
			}
next:
			temp=P;
			BigMul(temp,P2,P);
		}
end:
		if(i>mx)
			cout<<" No solution"<<endl;
	}
}

[lena]

How to print "No solution".

printf("No solution\n");

or

printf("Case %d: No solution\n",id);
printf("Case %d:No solution\n",id);

[saiful_sust]

JUST print like that
printf("Case %d: No solution\n",id);

• IMPOSSIBLE MEANS I M POSSIBLE

[pepp2]

Hi,
I always get Runtime Error with this code:

Code: Select all

#include <iostream>
#include <cstdlib>

#define MAXLEN 100000

using namespace std;

int t;

int num[MAXLEN];
int carry[MAXLEN];

int X,Y,N;
void solve(int caseno);


int main(){
    
    
    cin>>t;
    
    int i;
    for(i = 0; i<t; i++)
          solve(i+1);
    
    
   // system("PAUSE");
    return 0;
}


void solve(int caseno){
     
     
     cin>>N>>X>>Y;
     
     
     int i,j;
     for(i = 0; i<N*N+65; i++)
        carry[i] = num[i] = 0;
     
     
     num[0] = X;
     carry[1] = 0;
     
     long long int result  = 0;
     long long int car = 0;
     long long int carSaved = 0;
     
     lldiv_t d;
     
     for(i = 1; i<= N*N; i++){
      
        result = num[i-1] * Y + carry[i];
        d = div(result,(long long int) N);
        
        num[i] = d.rem;             
        
        car =  d.quot;
        carSaved = car;
       
        j = i+1; 
        
        while(car != 0){
                  
            d = div(car,(long long int)N);      
            carry[j] += d.rem;
            car = d.quot;
            j++;           
        }
        
        //cout<<"num["<<i<<"]: "<<num[i]<<" Carry[i+1]: "<<carry[i+1]<<endl;
        
        if(num[i] == X && carSaved ==0)
           break;    
     } 
     
     if(num[i] != X || carry[i+1] != 0){
          cout<<"Case "<<caseno<<": No solution"<<endl;
          return;      
     }
     
     cout<<"Case "<<caseno<<": ";
     for(j = i-1; j>=0; j--)
        cout<<num[j]<<" ";
     cout<<endl;
     
}

even if i tested it at home with thousands test case without error. Could you help me?
The program is very simple an I can't get any clue of the possible error. Do you know what are the limits of the number in the input?
Y can be assumed to be a 32-bits integer?

[pepp2]

No one can help me??