## 11533 - Special Number

Moderator: Board moderators

SerailHydra
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

### 11533 - Special Number

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

altertain
New poster
Posts: 9
Joined: Sat Jan 13, 2007 10:14 am

### Re: 11533 - Special Number

SerailHydra
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

### Re: 11533 - Special Number

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

2 0 0

the answer is 0, not 'No solution'.

Chimed
New poster
Posts: 12
Joined: Mon Oct 20, 2008 10:37 am

### Re: 11533 - Special Number

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
New poster
Posts: 18
Joined: Mon Sep 25, 2006 10:56 am
Location: Solar System
Contact:

### Re: 11533 - Special Number

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

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);
print(A,n,i);
break;
}
next:
temp=P;
BigMul(temp,P2,P);
}
end:
if(i>mx)
cout<<" No solution"<<endl;
}
}
``````

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

### Re: 11533 - Special Number

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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11533 - Special Number

JUST print like that
printf("Case %d: No solution\n",id);
• IMPOSSIBLE MEANS I M POSSIBLE

pepp2
New poster
Posts: 2
Joined: Thu Apr 01, 2010 11:25 am

### Re: 11533 - Special Number

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
New poster
Posts: 2
Joined: Thu Apr 01, 2010 11:25 am

### Re: 11533 - Special Number

No one can help me??