Cod sursa(job #586534)

Utilizator MKLOLDragos Ristache MKLOL Data 2 mai 2011 11:57:43
Problema NumMst Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;

char ciur[101000];
int prim[10100],k,x,S;
double best[221][3510];
int rec[221][3510];
int N;
int QWE;
double make(int pr,int sum)
{
if(pr>=200)
    return 0;
  //  printf("%d %d\n",pr,sum);
    if(sum==0)
        {
        return 0;
        }
    if(best[pr][sum])
        return best[pr][sum];
    if(sum==1)
    {
        rec[pr][sum]=1;
        best[pr][sum]=0;
        return 1LL*best[pr][sum];
    }

    if(prim[pr]>sum)
    {
        rec[pr][sum]=sum;
        return 0;
    }
    int put=0;
    if(sum==S)
    {

    for(int i=0;put<sum;++i)
    {
        if(put)
        {
        if(best[pr][sum]<(double)log10((double)put)+make(pr+1,sum-put))
            {
            best[pr][sum]=(double)log10((double)put)+make(pr+1,sum-put);
            rec[pr][sum]=put;
            }
        }
        else
        {
        if(best[pr][sum]<(double)make(pr+1,sum-put))
           {
            rec[pr][sum]=put;
            best[pr][sum]=(double)make(pr+1,sum-put);
           }
        }
        put*=prim[pr];
        if(put==0)
            put=prim[pr];

    }
    }else
    for(int i=0;put<=sum;++i)
    {
        if(put)
        {
        if(best[pr][sum]<(double)log10((double)put)+make(pr+1,sum-put))
            {
            best[pr][sum]=(double)log10((double)put)+make(pr+1,sum-put);
            rec[pr][sum]=put;
            }
        }
        else
        {
        if(best[pr][sum]<(double)make(pr+1,sum-put))
           {
            rec[pr][sum]=put;
            best[pr][sum]=(double)make(pr+1,sum-put);
           }
        }
        put*=prim[pr];
        if(put==0)
            put=prim[pr];

    }
return (double)best[pr][sum];
}
void make2(int x,int y)
{
    //printf("%d %d!!!\n",x,y);
    if(rec[x][y])
    {
    printf("%lld ",1LL*rec[x][y]*N/S);

    }
    if(y)
    {
        make2(x+1,y-rec[x][y]);
    }
    return;
}
int main()
{
freopen("nummst.in","r",stdin);
freopen("nummst.out","w",stdout);
    scanf("%d",&N);
    for(int i=2;i<=4010;++i)
    {
        if(ciur[i]==0)
        {
        prim[++k]=i;
        for(int j=i*2;j<=4010;j=j+i)
        {
            ciur[j]=2;
        }
        }
    }

    for(int i=2;i*i<=N;++i)
    {
    if(N%i==0)
        {
        x=i;
        i=N+1;
        }
    }

    S=x;
    if(x==2)
    {
        printf("%d %d\n",N/x,N/x);
        return 0;
    }
    if(x==3)
    {
        printf("%d %d\n",2*N/x,N/x);
        return 0;
    }
    double a=make(1,S);
    make2(1,S);
   // printf("%lf",a);
    //printf("%d\n",QWE);
  //  printf("%d ",prim[350]);
    return 0;

}