Cod sursa(job #953608)

Utilizator primulDarie Sergiu primul Data 26 mai 2013 19:34:50
Problema Numere 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include<fstream>
#include<cstring>
 
using namespace std;
ifstream f("numere2.in");
ofstream g("numere2.out");
int i,j,k,n,nr,nr1,put,x[220],a[211],p[220],li[220],ls[220],mij[220];
char s[111];
int compara(int x[],int y[])
{int i;
if(x[0]>y[0])
    return 1;
else
    if(x[0]<y[0])
        return -1;
for(i=x[0];i;--i)
    if(x[i]>y[i])
        return 1;
    else
        if(x[i]<y[i])
            return -1;
return 0;
}
void adunanm(int x[],int y[],int z[])
{int y1,t=0,i;
for(i=1;i<=x[0]||i<=y[0]||t;++i)
{y1=x[i]+y[i]+t;
t=y1/10;
z[i]=y1%10;
}
z[0]=i-1;
}
void aduna(int x[],int n)
{int t=n,i;
for(i=1;i<=x[0]||t;++i)
{x[i]+=t;
t=x[i]/10;
x[i]%=10;
}
x[0]=i-1;
}
void scade1(int x[],int n)
{int t,i;
t=n;
for(i=1;t;++i)
{x[i]+=t;
t=0;
while(x[i]<0)
{--t;x[i]+=10;}
}
while(x[x[0]]==0&&x[0])
    --x[0];
}
void impartire(int x[],int n)
{int t=0,i;
for(i=x[0];i;--i)
{t=t*10+x[i];x[i]=t/n;
t%=n;
}
while(x[x[0]]==0&&x[0]) --x[0];
}
void inmultire2(int a[],int b[],int c[])
{int i,t=0,j,n=a[0]-1+b[0];
//memset(c,0,sizeof(c));
for(i=1;i<=a[0];++i)
    for(j=1;j<=b[0];++j)
        c[i+j-1]+=a[i]*b[j];
for(i=1;i<=n||t;++i)
{c[i]+=t;
t=c[i]/10;
c[i]%=10;
}
c[0]=i-1;
}
void afiseaza(int x[])
{int i=x[0];
for(;i;--i)
    g<<x[i];
}
void copiere(int a[],int b[])
{int i;
for(i=1;i<=b[0]||i<=a[0];++i)
    a[i]=b[i];
a[0]=b[0];
}
 
int main()
{
    f>>(s+1);
    n=strlen(s+1);
    for(i=n;i;--i)
    {
        ++a[0];
        a[a[0]]=s[i]-'0';
    }
    for(put=100;put;--put)
    {
        memset(li,0,sizeof(li));
        memset(ls,0,sizeof(ls));
        nr=a[0]/put;
        if(a[0]%put)
        ++nr;
        ls[0]=nr;
        for(i=1;i<=ls[0];++i)
        ls[i]=9;
        if(nr>2)
        nr1=nr-2;
        else
        nr1=1;
        li[0]=nr1;
        li[nr1]=1;
        while(compara(li,ls)<=0)
        {
            adunanm(li,ls,mij);
            impartire(mij,2);
            p[0]=p[1]=1;
            for(j=1;j<=put;++j)
            {
                memset(x,0,sizeof(x));
                inmultire2(p,mij,x);
                copiere(p,x);
            }
            k=compara(p,a);
            if(k==0)
            {
                afiseaza(mij);
                g<<'\n'<<put<<'\n';
                return 0;
            }
            else
            if(k<0)
            {
                copiere(li,mij);
                aduna(li,1);
            }
            else
            {
                copiere(ls,mij);
                scade1(ls,-1);
            }
        }
    }
    return 0;
}