10527 - Persistent Numbers

Moderator: Board moderators

Eric3k
New poster
Posts: 29
Joined: Mon Apr 29, 2002 5:22 pm
Contact:

10527 - Persistent Numbers

Hi,
Could anyone please point me to the error I might have in the code. I can't seem to find it. It looks like it works for every case I've tried but get WA in systests.
Maybe I'm using the wrong algorithm?
Here's how it tries to solve it:
1. Loops from i = 2 to 9 and if it's possible to divide the number n by i, then one possibility is i appended to findmin(n/i). Ex, for findmin(18), it would be "2" + findmin(18/2) = "2" + findmin(9) = "29". The base case is if n is a single digit.
2. If findmin returns "", then it tries the next i in the loop.
Len is up to how many digits to go. It checks up to the amount of digits in n + 3. Perhaps this is the problem?

[cpp]
#include<vector>
#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
using namespace std;

string findmin( int n, int len){
if (len==0)return "";
for (int i=2;i<10;i++){
if (n<10){
string s;
s+=char(n+'0');
return s;
}
if (n%i==0){
string x = findmin(n/i,len-1);
if (x.size()!=0){
return char(i+'0')+x;
}
}
}
return "";
}
int main(){

//ifstream in("in.txt");
int n;
while (cin>>n && n!=-1){
int len=0;
int z=n;
while (z!=0){
z/=10;
len++;
}
string r;
if (n<10){
r="1";
r+=char(n+'0');
}
else {
for (int i=0;i<3;i++){
r= findmin(n,len+i);
if (r.size()!=0)break;
}
}
if (r.size()==0)cout<<"There is no such number.\n";
else cout<<r<<endl;

}

return 0;
}
[/cpp]

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
I think you need to use some bigint class to solve this, as the number may have 1000 digits...

Eric3k
New poster
Posts: 29
Joined: Mon Apr 29, 2002 5:22 pm
Contact:

Thx

Ahh I'm an idiot! I misread the problem. I thought there would be in the input up to 1000 numbers, but it's 1000 digits.
Thanks for pointing that out!

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
Talking about bigint's, do you know where do I get a good and small bigint class, such that I can type it in less than 10 minutes in a real contest?

Thanks!

JP!

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
Well, actually, this one is very specific, so you don't need the entire bigint class, you just need to implement what you need...

And the easiest (for me anyhow) way to do this is to represent it as a string, and do it the slow way... not very efficient, but during a contest, it should suffice..

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:
Yeah, for this specific problem I need at least division and comparison, but we will never know what a problem needs before we see it .

PS: I think I'll implement one bigint class myself, the one I've got is too much buggy... Thanks anyway!

JP!

Eric3k
New poster
Posts: 29
Joined: Mon Apr 29, 2002 5:22 pm
Contact:
I don't have one right now. I'll make it in the upcoming days. Probably using recursion will make very short (able to be typed in a few minutes).
I'm guessing the basic operations for a general would be toString, add, sub, mult, div, mod, and exp.
-Eric

tsue
New poster
Posts: 1
Joined: Mon Jul 07, 2003 4:45 am
Location: Hong Kong
Could anyone kindly post some test cases? Thank you

Aerodonkey
New poster
Posts: 1
Joined: Mon Jul 07, 2003 5:15 am
Location: China
Contact:

I wrote a bigint class myself.

It's a bit long, but includes many operations.
Help me debug and improve.
One bug found: when using stream, it might set the flag of stream incorrectly, especially when the text format is incorrect. How to solve it?
[cpp]
// Written by Han Wentao
#include <algorithm>
#include <cctype>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;
typedef long long int64;
// replace long long with __int64 when using VC++
class bigint : vector<int>
{
public:
bigint();
bigint(int n);
bigint(int64 n);
bigint(const string& s);
int to_int() const;
int64 to_int64() const;
const string to_string() const;
int digits() const;
bool operator !() const;
const bigint& operator +() const;
const bigint operator -() const;
const bigint& operator ++();
const bigint operator ++(int);
const bigint& operator --();
const bigint operator --(int);
friend bigint operator +(const bigint& N, const bigint& M);
friend bigint operator -(const bigint& N, const bigint& M);
friend bigint operator *(const bigint& N, const int n);
friend bigint operator *(const int n, const bigint& N);
friend bigint operator *(const bigint& N, const bigint& M);
friend bigint operator /(const bigint& N, const int n);
friend bigint operator /(const bigint& N, const bigint& M);
friend bigint operator %(const bigint& N, const int n);
friend bigint operator %(const bigint& N, const bigint& M);
friend bigint operator <<(const bigint& N, const int n);
friend bigint operator >>(const bigint& N, const int n);
bigint& operator +=(const bigint& N);
bigint& operator -=(const bigint& N);
bigint& operator *=(const int n);
bigint& operator *=(const bigint& N);
bigint& operator /=(const int n);
bigint& operator /=(const bigint& N);
bigint& operator %=(const int n);
bigint& operator %=(const bigint& N);
bigint& operator <<=(const int n);
bigint& operator >>=(const int n);
friend bool operator ==(const bigint& N, const bigint& M);
friend bool operator !=(const bigint& N, const bigint& M);
friend bool operator <(const bigint& N, const bigint& M);
friend bool operator >(const bigint& N, const bigint& M);
friend bool operator <=(const bigint& N, const bigint& M);
friend bool operator >=(const bigint& N, const bigint& M);
friend const bigint abs(const bigint& N);
friend int compare(const bigint& N, const bigint& M);
friend const bigint divide(const bigint& N, const int n, int& remainder);
friend const bigint divide(const bigint& N, const bigint& M, bigint& remainder);
friend const bigint shift(const bigint& N, const int n);
friend const bigint sqrt(const bigint& N);
friend istream& operator >>(istream& instr, bigint& N);
friend ostream& operator <<(ostream& outstr, const bigint& N);
private:
static const int base=1000000000;
static const int width=9;
bool sign;
void simplify();
friend const bigint add_abs(const bigint& N, const bigint& M);
friend const bigint sub_abs(const bigint& N, const bigint& M);
friend const bigint mul_abs(const bigint& N, const int n, const int offset=0);
friend const bigint div_abs(const bigint& N, const int n, int& remainder);
friend const bigint div_abs(const bigint& N, const bigint& M, bigint& remainder);
};
const bigint pow(const bigint& N, const int n);
const bigint factorial(const int n);
const bigint permutation(const int n, const int m);
const bigint permutation_circle(const int n, const int m);
const bigint permutation_repeat(const int n, const int m);
const bigint combination(const int n, const int m);
const bigint combination_repeat(const int n, const int m);
const bigint gcd(const bigint& N, const bigint& M);
const bigint lcm(const bigint& N, const bigint& M);
void gcd_lcm(const bigint& N, const bigint& M, bigint& GCD, bigint& LCM);
inline bigint::bigint() : sign(false)
{
}
bigint::bigint(int n)
{
if(n<0)
{
sign=true;
n=-n;
}
else
sign=false;
while(n!=0)
{
push_back(n%base);
n/=base;
}
}
inline bigint::bigint(int64 n)
{
if(n<0)
{
sign=true;
n=-n;
}
else
sign=false;
while(n!=0)
{
push_back(n%base);
n/=base;
}
}
inline bigint::bigint(const string& s)
{
istringstream sin(s);
sin>>*this;
}
int bigint::to_int() const
{
int r=0;
for(int i=size()-1; i>=0; i--)
r=r*base+(*this);
if(sign)
r=-r;
return r;
}
int64 bigint::to_int64() const
{
int64 r=0;
for(int i=size()-1; i>=0; i--)
r=r*base+(*this);
if(sign)
r=-r;
return r;
}
inline const string bigint::to_string() const
{
ostringstream sout;
sout<<*this;
return sout.str();
}
int bigint::digits() const
{
if(empty())
return 0;
int r=(size()-1)*width;
int temp=(*this)[size()-1];
while(temp>0)
{
r++;
temp/=10;
}
return r;
}
inline bool bigint::operator !() const
{
return !empty();
}
inline const bigint& bigint::operator +() const
{
return *this;
}
inline const bigint bigint::operator -() const
{
bigint R(*this);
R.sign=!empty() && !R.sign;
return R;
}
inline const bigint& bigint::operator ++()
{
*this=*this+1;
return *this;
}
inline const bigint bigint::operator ++(int)
{
bigint backup(*this);
*this=*this+1;
return backup;
}
inline const bigint& bigint::operator --()
{
*this=*this-1;
return *this;
}
inline const bigint bigint::operator --(int)
{
bigint backup(*this);
*this=*this-1;
return backup;
}
inline bigint operator +(const bigint& N, const bigint& M)
{
bigint R;
if(N.sign^M.sign)
{
if(abs(N)>=abs(M))
{
R=sub_abs(N, M);
R.sign=N.sign;
}
else
{
R=sub_abs(M, N);
R.sign=M.sign;
}
R.simplify();
}
else
{
R.sign=N.sign;
}
return R;
}
inline bigint operator -(const bigint& N, const bigint& M)
{
return N+(-M);
}
inline bigint operator *(const bigint& N, const int n)
{
if(n<=-bigint::base || n>=bigint::base)
return N*bigint(n);
else
{
bigint R;
R=mul_abs(N, abs(n));
R.sign=N.sign^(n<0);
R.simplify();
return R;
}
}
inline bigint operator *(const int n, const bigint& N)
{
return N*n;
}
bigint operator *(const bigint& N, const bigint& M)
{
bigint R;
if(N.size()<M.size())
for(int i=0; i<N.size(); i++)
R+=mul_abs(M, N, i);
else
for(int i=0; i<M.size(); i++)
R+=mul_abs(N, M, i);
R.sign=N.sign^M.sign;
R.simplify();
return R;
}
inline bigint operator /(const bigint& N, const int n)
{
if(n<=-bigint::base || n>=bigint::base)
return N/bigint(n);
else
{
bigint R;
int remainder;
R=div_abs(N, abs(n), remainder);
R.sign=N.sign^(n<0);
return R;
}
}
inline bigint operator /(const bigint& N, const bigint& M)
{
bigint R,remainder;
R=div_abs(N, M, remainder);
R.sign=N.sign^M.sign;
return R;
}
inline bigint operator %(const bigint& N, const int n)
{
if(n<=-bigint::base || n>=bigint::base)
return N%bigint(n);
else
{
bigint R;
int remainder;
R=div_abs(N, abs(n), remainder);
if(N.sign)
remainder=-remainder;
return remainder;
}
}
inline bigint operator %(const bigint& N, const bigint& M)
{
bigint R,remainder;
R=div_abs(N, M, remainder);
remainder.sign=N.sign;
return remainder;
}
inline bigint operator <<(const bigint& N, const int n)
{
return shift(N, n);
}
inline bigint operator >>(const bigint& N, const int n)
{
return shift(N, -n);
}
inline bigint& bigint::operator +=(const bigint& N)
{
*this=*this+N;
return *this;
}
inline bigint& bigint::operator -=(const bigint& N)
{
*this=*this-N;
return *this;
}
inline bigint& bigint::operator *=(const int n)
{
*this=*this*n;
return *this;
}
inline bigint& bigint::operator *=(const bigint& N)
{
*this=*this*N;
return *this;
}
inline bigint& bigint::operator /=(const int n)
{
*this=*this/n;
return *this;
}
inline bigint& bigint::operator /=(const bigint& N)
{
*this=*this/N;
return *this;
}
inline bigint& bigint::operator %=(const int n)
{
*this=*this%n;
return *this;
}
inline bigint& bigint::operator %=(const bigint& N)
{
*this=*this%N;
return *this;
}
inline bigint& bigint::operator <<=(const int n)
{
*this=*this<<n;
return *this;
}
inline bigint& bigint::operator >>=(const int n)
{
*this=*this>>n;
return *this;
}
inline bool operator ==(const bigint& N, const bigint& M)
{
return compare(N, M)==0;
}
inline bool operator !=(const bigint& N, const bigint& M)
{
return compare(N, M)!=0;
}
inline bool operator <(const bigint& N, const bigint& M)
{
return compare(N, M)<0;
}
inline bool operator >(const bigint& N, const bigint& M)
{
return compare(N, M)>0;
}
inline bool operator <=(const bigint& N, const bigint& M)
{
return compare(N, M)<=0;
}
inline bool operator >=(const bigint& N, const bigint& M)
{
return compare(N, M)>=0;
}
inline const bigint abs(const bigint& N)
{
bigint R(N);
R.sign=false;
return R;
}
int compare(const bigint& N, const bigint& M)
{
if(!N.sign && M.sign)
return 1;
else if(N.sign && !M.sign)
return -1;
else
{
int temp;
if(N.size()>M.size())
temp=1;
else if(N.size()<M.size())
temp=-1;
else
{
temp=0;
for(int i=N.size()-1; i>=0 && temp==0; i--)
if(N>M)
temp=1;
else if(N<M)
temp=-1;
}
if(N.sign)
return -temp;
else
return temp;
}
}
inline const bigint divide(const bigint& N, const int n, int& remainder)
{
bigint R;
R=div_abs(N, abs(n), remainder);
R.sign=N.sign^(n<0);
if(N.sign)
remainder=-remainder;
return R;
}
inline const bigint divide(const bigint& N, const bigint& M, bigint& remainder)
{
bigint R;
R=div_abs(N, M, remainder);
R.sign=N.sign^M.sign;
remainder.sign=N.sign;
return R;
}
const bigint shift(const bigint& N, const int n)
{
if(N.empty() || N.digits()+n<=0)
return 0;
bigint R;
int offset=n/bigint::width;
int micro=n%bigint::width;
if(micro>0)
{
micro-=bigint::width;
offset++;
}
micro=-micro;
R.resize(N.size()+offset+1,0);
if(offset>=0)
for(int i=0; i<N.size(); i++)
R[i+offset]=N;
else
for(int i=0; i<N.size()+offset; i++)
R=N[i-offset];
if(micro!=0)
{
int divisor=1;
int i;
for(i=0; i<micro; i++)
divisor*=10;
for(i=0; i<R.size()-1; i++)
R[i]=(R[i+1]*int64(bigint::base)+R[i])/divisor%bigint::base;
R[R.size()-1]=R[R.size()-1]/bigint::base;
}
R.sign=N.sign;
R.simplify();
return R;
}
const bigint sqrt(const bigint& N)
{
if(N.sign)
return -1;
if(N.empty())
return 0;
bigint R,left(N);
R.resize((N.size()+1)/2,0);
int64 temp=N[N.size()-1];
if(N.size()%2==0)
temp=temp*bigint::base+N[N.size()-2];
R[R.size()-1]=int(sqrt(static_cast<long double>(temp)));
left-=R*R;
for(int i=R.size()-2; i>=0; i--)
{
int lower=0,upper=bigint::base;
bigint T;
T.resize(i+1, 0);
while(upper-lower>=2)
{
T[i]=(lower+upper)/2;
if(T*(R+R+T)<left)
lower=T[i];
else
upper=T[i];
}
T[i]=upper;
if(T*(R+R+T)<=left)
T[i]=upper;
else
T[i]=lower;
left-=T*(R+R+T);
R[i]=T[i];
}
return R;
}
istream& operator >>(istream& instr, bigint& N)
{
instr>>ws;
if(!instr)
return instr;
N.clear();
if(instr.peek()=='+' || instr.peek()=='-')
{
N.sign=instr.peek()=='-';
instr.ignore(1);
}
else
N.sign=false;
vector<char> buffer;
while(isdigit(instr.peek()))
buffer.push_back(instr.get());
reverse(buffer.begin(),buffer.end());
while(buffer.size()%bigint::width!=0)
buffer.push_back('0');
for(int i=0; i<buffer.size()/bigint::width; i++)
{
int period=0;
for(int j=bigint::width-1; j>=0; j--)
period=period*10+(buffer[i*bigint::width+j]-'0');
N.push_back(period);
}
N.simplify();
return instr;
}
ostream& operator <<(ostream& outstr, const bigint& N)
{
if(N.empty())
outstr<<0;
else
{
if(N.sign)
outstr<<'-';
outstr<<N[N.size()-1];
for(int i=N.size()-2; i>=0; i--)
{
outstr.width(bigint::width);
outstr.fill('0');
outstr<<N[i];
}
}
return outstr;
}
void bigint::simplify()
{
while(!empty() && back()==0)
pop_back();
if(empty())
sign=false;
}
const bigint add_abs(const bigint& N, const bigint& M)
{
bigint R;
int bound=max(N.size(), M.size());
R.resize(bound+1,0);
for(int i=0; i<bound; i++)
{
if(i<N.size())
R[i]+=N[i];
if(i<M.size())
R[i]+=M[i];
if(R[i]>=bigint::base)
{
R[i+1]++;
R[i]-=bigint::base;
}
}
R.simplify();
return R;
}
const bigint sub_abs(const bigint& N, const bigint& M)
{
bigint R;
int bound=N.size();
R.resize(bound,0);
for(int i=0; i<bound; i++)
{
R[i]+=N[i];
if(i<M.size())
R[i]-=M[i];
if(R[i]<0)
{
R[i+1]--;
R[i]+=bigint::base;
}
}
R.simplify();
return R;
}
const bigint mul_abs(const bigint& N, const int n, const int offset)
{
if(n==0)
return 0;
bigint R;
R.resize(N.size()+1+offset, 0);
for(int i=0; i<N.size(); i++)
{
int64 temp=int64(n)*N[i]+R[i+offset];
R[i+offset]=temp%bigint::base;
R[i+offset+1]+=temp/bigint::base;
}
R.simplify();
return R;
}
const bigint div_abs(const bigint& N, const int n, int& remainder)
{
bigint R;
R.resize(N.size(), 0);
int64 temp=0;
for(int i=N.size()-1; i>=0; i--)
{
temp=temp*bigint::base+N[i];
R[i]=temp/n;
temp%=n;
}
remainder=temp;
R.simplify();
return R;
}
const bigint div_abs(const bigint& N, const bigint& M, bigint& remainder)
{
if(N.size()<M.size())
{
remainder=N;
return 0;
}
bigint R;
R.resize(N.size());
remainder=0;
for(int i=N.size()-1; i>=0; i--)
{
remainder=mul_abs(remainder, 1, 1)+N[i];
int lower=0,upper=bigint::base;
while(upper-lower>=2)
{
R[i]=(lower+upper)/2;
if(abs(M)*R[i]<remainder)
lower=R[i];
else
upper=R[i];
}
if(abs(M)*upper<=remainder)
R[i]=upper;
else
R[i]=lower;
remainder-=abs(M)*R[i];
}
R.simplify();
return R;
}
const bigint pow(const bigint& N, const int n)
{
if(N==0)
return 0;
bigint T(N),R(1);
for(int i=1; i<=n && i>0; i<<=1)
{
if(i&n)
R*=T;
T*=T;
}
return R;
}
const bigint factorial(const int n)
{
bigint R(1);
for(int i=2; i<=n; i++)
R*=i;
return R;
}
const bigint permutation(const int n, const int m)
{
if(n<0 || m<0 || m>n)
return 0;
bigint R(1);
for(int i=n-m+1; i<=n; i++)
R*=i;
return R;
}
inline const bigint permutation_circle(const int n, const int m)
{
if(n<0 || m<0 || m>n)
return 0;
return permutation(n, m)/m;
}
inline const bigint permutation_repeat(const int n, const int m)
{
if(n<0 || m<0 || m>n)
return 0;
return pow(bigint(n), m);
}
const bigint combination(const int n, const int m)
{
if(n<0 || m<0 || m>n)
return 0;
bigint R(1);
int i;
for(i=n-m+1; i<=n; i++)
R*=i;
for(i=2; i<=m; i++)
R/=i;
return R;
}
inline const bigint combination_repeat(const int n, const int m)
{
if(n<0 || m<0 || m>n)
return 0;
return combination(n+m-1, m);
}
const bigint euclid(const bigint& N, const bigint& M)
{
bigint A(N), B(M);
while(!B)
{
bigint T(B);
B=A%B;
A=T;
}
return A;
}
inline const bigint gcd(const bigint& N, const bigint& M)
{
if(abs(N)>abs(M))
return euclid(abs(N), abs(M));
else
return euclid(abs(M), abs(N));
}
inline const bigint lcm(const bigint& N, const bigint& M)
{
return abs(N*M/gcd(N, M));
}
inline void gcd_lcm(const bigint& N, const bigint& M, bigint& GCD, bigint& LCM)
{
GCD=gcd(N, M);
LCM=abs(N*M/GCD);
}
[/cpp]
No Best, Only Better.

Eric3k
New poster
Posts: 29
Joined: Mon Apr 29, 2002 5:22 pm
Contact:
Hi,
Try changing istream& operator >>(istream& instr, bigint& N) to this instead:
[cpp]while(isdigit(instr.peek()))
buffer.push_back(instr.get());
if (instr.peek()!='\n'){
instr.setstate(instr.failbit);
instr.setstate(instr.eofbit); //Maybe this one too
}[/cpp]

If it still do not work, I'll look at it tomorrow in more details.

rahul
New poster
Posts: 2
Joined: Mon Oct 09, 2006 3:20 pm

10527 help(Persistent Numbers)

i am pasting my code which is giving right answer for given test case but giving wrong answer after submitting the code please find where i am wrong.
if possible can u give me some test cases.

Code: Select all

``````#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
class acm
{
public:
vector<long long> result;
int xxx()
{
long long n;
vector<int> v,cnt,ans;
cin>>n;
while(n!=-1)
{
long long count=0,co2=0,co3=0,co5=0,co7=0,mx,mx1,final=0;
if(n>=0 && n<10)
{
result.push_back(n+10);
}
if(n>=10)
{
while(n!=1)
{count=0;
if(n%2==0)
{
v.push_back(2);
n=n/2;
}
if(n%2!=0)
count++;
if(n%3==0)
{
v.push_back(3);
n=n/3;
}
if(n%3!=0)
count++;
if(n%5==0)
{
v.push_back(5);
n=n/5;
}
if(n%5!=0)
count++;
if(n%7==0)
{
v.push_back(7);
n=n/7;
}
if(n%7!=0)
count++;
if(count==4 && n!=1)
{
v.clear();
break;
}
else
count=0;
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++)
{
if(v[i]==2)
co2++;
if(v[i]==5)
co5++;
if(v[i]==3)
co3++;
if(v[i]==7)
co7++;
}
if(co3>=2)
{
mx=co3/2;
co3=co3%2;
for(int i=0;i<mx;i++)
ans.push_back(9);
mx=0;
}
if(co2>=3)
{
mx=co2/3;
co2=co2%3;
for(int i=0;i<mx;i++)
ans.push_back(8);
}
if(co7>0)
{
for(int i=0;i<co7;i++)
ans.push_back(7);
co7=0;
}
if(co3!=0 && co2!=0)
{
ans.push_back(6);
co2=co2-1;
co3=0;
}
if(co5>0)
{
for(int i=0;i<co5;i++)
ans.push_back(5);
co5=0;
}
if(co2>1)
{
ans.push_back(4);
co2=0;
}
if(co3!=0 && co2==0)
{
ans.push_back(3);
co3=0;
}
if(co2>0)
ans.push_back(2);
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
{
final=10*final+ans[i];
}
result.push_back(final);
ans.clear();
v.clear();
cnt.clear();
}
cin>>n;
}
return 0;
}
int display()
{
for(int k=0;k<result.size();k++)
{
if(result[k]==0)
{
cout<<"There is no such number."<<endl;
}
else
cout<<result[k]<<"\n";
}
return 0;
}
};
int main()
{
class acm x;
x.xxx();
x.display();
return 0;
}``````

hi!man!
New poster
Posts: 48
Joined: Fri Dec 29, 2006 1:26 pm
input can up to 1000 digits
so you will get wrong answer.

Btw, do not create a new thread if there is already one.

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Somebody please post some IO. I 've tried some and my code gives correct ans. on them; still WA. Is it possible to have leading 0s?

[EDIT] I 've found my error, , I wasn't assigning null to the string representing the number correctly after division.
regards,
nymo

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
Runtime Error (Signal 11)...
hello everybody . i am try to solve this problem but getting RTE , don't know why.
plz help me ..here is my code .kindly tell me why RTE.

Code: Select all

``````#include<cstdio>
#include<cstring>
int div(char *a ,char *b,char *c)
{

int m,n,i,t,v,d,j,flag=1;
unsigned long k,u;
m=strlen(a);
n=strlen(b);
k=0;
u=0;
for(i=0;i<m;i++)
a[i]=a[i]-'0';
for(i=0;i<n;i++)
{
k=k*10+a[i];
u=u*10+b[i];
}
if(k<u)
{
k=k*10+a[i];
i++;
}
//  printf("k=%d u=%d ",k,u);
t=i-1;
v=0;
//  printf("t=%d i=%d ",t,i);
if(n==m)
{
c[v]=(k/u)+'0';
d=k%u;
//    printf("%d",c[v]);
//    printf("%d",d);
}
while(i!=m)
{
c[v]=(k/u)+'0';
//    printf("c[%d]=%d ",v,c[v]);
d=k%u;
//     printf("d=%d ",d);
//if(n==m)
// break;
if(d<u && i!=m)
{
d=d*10+a[i];
//  printf("d=%d ",d);
i++;
t++;
//printf("i=%d t=%d",i,t);
}
//  printf("d=%d u=%d a[%d]=%d ", d,u,i,a[i]);
if(d==0)
{
while( d<u && a[i]<u && i!=m)
{
v++;
// printf("v=%d ",v);
c[v]=0+'0';
//  printf("c[%d]=%d ",v,c[v]);
d=d*10+a[i];
//  printf("d=%d ",d);
t++;
i++;
//   flag=0;
// printf("t=%d i=%d ",t,i);
}
}
//  printf("d=%d u=%d a[%d]=%d ", d,u,i,a[i]);

while(d<u && i!=m)
{
d=d*10+a[i];
//  printf("d=%d ",d);
i++;
t++;
v++;
//  printf("i=%d t=%d v=%d ",i,t,v);
c[v]=0+'0';
//   printf("c[%d]=%d ",v,c[v]);
}
k=d;
v++;
//  printf("k=%d d=%d v=%d ",k,d,v);
}

c[v]=(k/u) + '0';
d=k%u;

/*for(j=0;j<=v;j++)
printf("%d",c[j]-'0');
printf("\n%d\n",d);*/

return(d);
}
void init(int *count)
{
for(int i=0;i<4;i++)
count[i]=0;
}
void inttochar(char *a)
{
int n=strlen(a);
for(int i=0;i<n;i++)
a[i]=a[i]+'0';
}
void callfun(int *count)
{
int u=0,min,temp1,temp2,i,j;
char temp[2009];
for(i=0;i<count[1]/2;i++)
{
temp[u]=9;
u++;
}
for(i=0;i<count[0]/3;i++)
{
temp[u]=8;
u++;
}
for(j=0;j<count[3];j++)
{
temp[u]=7;
u++;
}
temp1=count[0]%3;
temp2=count[1]%2;
if(temp1>temp2)
min=temp2;
else
min=temp1;
temp1=temp1-min;
temp2=temp2-min;
for(j=0;j<min;j++)
{
temp[u]=6;
u++;
}
for(j=0;j<count[2];j++)
{
temp[u]=5;
u++;
}
for(j=0;j<temp1/2;j++)
{
temp[u]=4;
u++;
}
for(j=0;j<temp2;j++)
{
temp[u]=3;
u++;
}
for(j=0;j<temp1%2;j++)
{
temp[u]=2;
u++;
}

for(j=u-1;j>=0;j--)
printf("%d",temp[j]);
printf("\n");
}

int main()
{
char  a[2009],c[2009],prime[4][2];
int   count[4],i,n,d,flag;
memset(prime,0,sizeof(prime));
prime[0][0]=2;
prime[1][0]=3;
prime[2][0]=5;
prime[3][0]=7;
memset(a,0,sizeof(a));
memset(c,0,sizeof(c));
while(scanf("%s",a) && (a[0]!='-' || a[1]!='1'))
{

if(a[0]>='0' && a[0]<='9' && a[1]=='\0')
printf("%d\n",10+a[0]-'0');
else
{
init(count);
flag=1;
for(i=0;i<4;i++)
{

do
{

if((a[0]=='1' || a[0]=='0')&& a[1]=='\0')
{
flag=0;
break;
}

d=div(a,prime[i],c);
if(d==0)
{
strcpy(a,c);
count[i]++;
}

memset(c,0,sizeof(c));
}while(d==0);

if(!flag)
break;
inttochar(a);
}
/*for(i=0;i<4;i++)
printf("count[%d]=%d\n",i,count[i]);*/

if(d!=0)
printf("There is no such number.\n");
else
callfun(count);
}
}
}

``````

jumbo
New poster
Posts: 4
Joined: Fri Oct 31, 2008 1:48 am

Re: 10527 - Persistent Numbers

Hello,

I'd like to ask if I can use BigInteger class from package java.math.BigInteger in Java. I'm not getting any compilation error or runtime error, I am getting WA, so I assume that it is ok to use it, but just for assure.

So can you look at my code and help me:

Code: Select all

``````import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

// processing number
private BigInteger processing;

// all the input
private ArrayList<BigInteger> in;

// static BigInteger representation of some numbers
private static final BigInteger twoVal = new BigInteger("2");
private static final BigInteger threeVal = new BigInteger("3");
private static final BigInteger fiveVal = new BigInteger("5");
private static final BigInteger sevenVal = new BigInteger("7");
private static final BigInteger oneVal = new BigInteger("1");
private static final BigInteger fourVal = new BigInteger("4");
private static final BigInteger sixVal = new BigInteger("6");
private static final BigInteger eightVal = new BigInteger("8");
private static final BigInteger nineVal = new BigInteger("9");
private static final BigInteger tenVal = new BigInteger("10");

// counts of the one digit primes in the prcessing NUM
private BigInteger twoCount = new BigInteger("0");
private BigInteger threeCount = new BigInteger("0");
private BigInteger fiveCount = new BigInteger("0");
private BigInteger sevenCount = new BigInteger("0");

public Main()
{
in = new ArrayList<BigInteger>();
}

// reads all the avialable bytes from System.in (as far as -1)
{
try
{
//pole pro nacteni celeho vstupu naraz
byte[] b = new byte[System.in.available()];

if (r == -1)
{
System.exit(1);
}

StringTokenizer tok = new StringTokenizer(new String(b));

// pocet radku, standartni delimitery staci
BigInteger tmp;
for (int i = 0; i < radku; i++)
{
// dostanu jeden radek jako string a udelam z nej int
tmp = new BigInteger(tok.nextToken());
// pri nule je konec, davaji za nulu jeste dalsi cisla...
if( tmp.intValue() == -1 ) break;
// pridam do arraylistu

}

}
catch (IOException ex)
{
System.out.println("chyba");
System.exit(1);
}
}

// just sets the field
public void setNum(BigInteger n)
{
processing = n;
}

// divides the number by one digit primes (2, 3, 5, 7) and counts how many times NUM was
// divided by each of the prime
public void getParts()
{
if(processing.intValue() == 0)
return;

BigInteger tmp = processing;

while(processing.remainder(twoVal).intValue() == 0 )
{
processing = processing.divide(twoVal);
}
while(processing.remainder(threeVal).intValue() == 0 )
{
processing = processing.divide(threeVal);
}
while(processing.remainder(fiveVal).intValue() == 0 )
{
processing = processing.divide(fiveVal);
}
while(processing.remainder(sevenVal).intValue() == 0 )
{
processing = processing.divide(sevenVal);
}

processing = tmp;
}

// check if all of the parts we got multiplied give the original number
public boolean check()
{
BigInteger  chck = new BigInteger("0");

BigInteger tmp1 = sevenVal.pow(sevenCount.intValue());
BigInteger tmp2 = fiveVal.pow(fiveCount.intValue());
BigInteger tmp3 = threeVal.pow(threeCount.intValue());
BigInteger tmp4 = twoVal.pow(twoCount.intValue());

chck = tmp1.multiply(tmp2.multiply(tmp3.multiply(tmp4)));

if ( chck.equals(processing) )
return true;

return false;
}

// method that builds the smallest number from the parts
public BigInteger createPrevious()
{
BigInteger prev = new BigInteger("0");
BigInteger digit_place = new BigInteger("1");

if (processing.intValue() == 1)
return new BigInteger("11");

while(contains(9))
{
digit_place= digit_place.multiply(tenVal);
threeCount = threeCount.subtract(twoVal);
}
while(contains(8))
{
digit_place= digit_place.multiply(tenVal);
twoCount = twoCount.subtract(threeVal);
}
while(contains(7))
{
digit_place= digit_place.multiply(tenVal);
sevenCount = sevenCount.subtract(oneVal);
}
while(contains(6))
{
digit_place= digit_place.multiply(tenVal);
threeCount = threeCount.subtract(oneVal);
twoCount = twoCount.subtract(oneVal);
}
while(contains(5))
{
digit_place= digit_place.multiply(tenVal);
fiveCount = fiveCount.subtract(oneVal);
}
while(contains(4))
{
digit_place= digit_place.multiply(tenVal);
twoCount = twoCount.subtract(twoVal);
}
while(contains(3))
{
digit_place= digit_place.multiply(tenVal);
threeCount = threeCount.subtract(oneVal);
}
while(contains(2))
{
digit_place= digit_place.multiply(tenVal);
twoCount = twoCount.subtract(oneVal);
}

if (prev.compareTo(tenVal) == -1 )

return prev;
}

// can we get NUMBER from the parts we have right now?
boolean contains(int number)
{
switch (number)
{
case 9:
if (threeCount.compareTo(twoVal) == -1)
return false;
return true;
case 8:
if (twoCount.compareTo(threeVal) == -1)
return false;
return true;
case 7:
if (sevenCount.compareTo(oneVal) == -1)
return false;
return true;
case 6:
if (twoCount.compareTo(oneVal) == -1 || threeCount.compareTo(oneVal) == -1)
return false;
return true;
case 5:
if (fiveCount.compareTo(oneVal) == -1)
return false;
return true;
case 4:
if (twoCount.compareTo(twoVal) == -1)
return false;
return true;
case 3:
if (threeCount.compareTo(oneVal) == -1)
return false;
return true;
case 2:
if (twoCount.compareTo(oneVal) == -1)
return false;
return true;
default:
return false;
}
}

// sets the working NUM, gets all the parts,
// check if the parts gives the original number and than prints a result
public void processANumber(BigInteger n)
{
setNum(n);
getParts();
if(check() || processing.compareTo(BigInteger.valueOf(10)) == -1 )
System.out.println(createPrevious());
else
System.out.println("There is no such number.");// ("+num.toString()+")");
}

// launch a process for every number we've got in the input (resets counts after each)
public void run()
{
int s = in.size();
for (int i = 0; i < s; i++)
{
init();
processANumber(in.get(i));
}
}

// just creates an instance, reads a data and launches the program
public static void main(String[] args)
{
Main m = new Main();

m.run();

System.exit(0);
}

// resets the counters
private void init()
{
twoCount = new BigInteger("0");
threeCount = new BigInteger("0");
fiveCount = new BigInteger("0");
sevenCount = new BigInteger("0");
}

}
``````