10527 - Persistent Numbers

[Eric3k]

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?
Thanks for your help.

[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]

I think you need to use some bigint class to solve this, as the number may have 1000 digits...

[Eric3k]

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]

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]

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]

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]

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]

Could anyone kindly post some test cases? Thank you

[Aerodonkey]

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=add_abs(N, M);
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]

[Eric3k]

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]

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!]

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]

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.

[mukeshtiwari]

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]

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)
    public void readInput()
    {
        try
        {
            //pole pro nacteni celeho vstupu naraz
            byte[] b = new byte[System.in.available()];
            
                int r = System.in.read(b);
                if (r == -1) 
                {
                    System.exit(1);
                }
                
                StringTokenizer tok = new StringTokenizer(new String(b));
                
                // pocet radku, standartni delimitery staci
                int radku = tok.countTokens();
                // int pro ulozeni radku
                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
                    in.add(tmp);
                    
                }
                
            
        } 
        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 )
        {
            twoCount = twoCount.add(oneVal);
            processing = processing.divide(twoVal);
        }
        while(processing.remainder(threeVal).intValue() == 0 )
        {
            threeCount = threeCount.add(oneVal);
            processing = processing.divide(threeVal);
        }
        while(processing.remainder(fiveVal).intValue() == 0 )
        {
            fiveCount = fiveCount.add(oneVal);
            processing = processing.divide(fiveVal);
        }
        while(processing.remainder(sevenVal).intValue() == 0 )
        {
            sevenCount = sevenCount.add(oneVal);
            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))
        {
            prev = prev.add(digit_place.multiply(nineVal));
            digit_place= digit_place.multiply(tenVal);
            threeCount = threeCount.subtract(twoVal);
        }
        while(contains(8))
        {
            prev = prev.add(digit_place.multiply(eightVal));
            digit_place= digit_place.multiply(tenVal);
            twoCount = twoCount.subtract(threeVal);
        }
        while(contains(7))
        {
            prev = prev.add(digit_place.multiply(sevenVal));
            digit_place= digit_place.multiply(tenVal);
            sevenCount = sevenCount.subtract(oneVal);
        }
        while(contains(6))
        {
            prev = prev.add(digit_place.multiply(sixVal));
            digit_place= digit_place.multiply(tenVal);
            threeCount = threeCount.subtract(oneVal); 
            twoCount = twoCount.subtract(oneVal);
        }
        while(contains(5))
        {
            prev = prev.add(digit_place.multiply(fiveVal));
            digit_place= digit_place.multiply(tenVal);
            fiveCount = fiveCount.subtract(oneVal);
        }
        while(contains(4))
        {
            prev = prev.add(digit_place.multiply(fourVal));
            digit_place= digit_place.multiply(tenVal);
            twoCount = twoCount.subtract(twoVal);
        }
        while(contains(3))
        {
            prev = prev.add(digit_place.multiply(threeVal));
            digit_place= digit_place.multiply(tenVal);
            threeCount = threeCount.subtract(oneVal);
        }
        while(contains(2))
        {
            prev = prev.add(digit_place.multiply(twoVal));
            digit_place= digit_place.multiply(tenVal);
            twoCount = twoCount.subtract(oneVal);
        }
        
        if (prev.compareTo(tenVal) == -1 ) 
            prev = prev.add(tenVal);
	
        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.readInput();
        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");
    }
    
}