10527 - Persistent Numbers

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

Moderator: Board moderators

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

10527 - Persistent Numbers

Post by Eric3k » Sun Jul 06, 2003 5:20 am

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. :roll:

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

Post by jpfarias » Sun Jul 06, 2003 5:02 pm

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

Post by Eric3k » Sun Jul 06, 2003 5:20 pm

Ahh I'm an idiot! :oops: 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! :D

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » Sun Jul 06, 2003 5:36 pm

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:

Post by Larry » Sun Jul 06, 2003 7:10 pm

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:

Post by jpfarias » Sun Jul 06, 2003 10:10 pm

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:

Post by Eric3k » Mon Jul 07, 2003 12:20 am

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

Post by tsue » Mon Jul 07, 2003 4:49 am

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.

Post by Aerodonkey » Mon Jul 07, 2003 5:25 am

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]
No Best, Only Better.

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

Post by Eric3k » Mon Jul 07, 2003 5:59 am

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)

Post by rahul » Mon Oct 09, 2006 3:37 pm

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

Post by hi!man! » Sun Jan 21, 2007 11:42 am

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: :)

SOME IO PLEASE...

Post by nymo » Mon Feb 12, 2007 9:43 am

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, :oops: , 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

Post by mukeshtiwari » Tue Jun 12, 2007 8:06 am

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

Post by jumbo » Wed Dec 03, 2008 7:29 pm

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

Post Reply

Return to “Volume 105 (10500-10599)”