Cod sursa(job #586315)

Utilizator DraStiKDragos Oprica DraStiK Data 30 aprilie 2011 14:28:37
Problema NumMst Scor 22
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 2.41 kb
#include <algorithm>
#include <cstring>
#include <vector>
#include <cstdio>
#include <bitset>
#include <cmath>
using namespace std;

#define MAX 10000005
#define DIM 4005


int prim[DIM],cnt[DIM],ant[DIM];
double bst[DIM],lg2[DIM];
bitset <MAX> viz;
int N,M,P;

void read ()
{
    int i,j;

    scanf ("%d",&N);

    M=N;
    if (!(N&1))
        N=2;

    prim[++P]=2;
    for (i=3; i<=N; i+=2)
        if (!viz[i])
        {
            if (!(N%i))
                N=i;

            prim[++P]=i;
            for (j=3*i; j<=N; j+=(i<<1))
                viz[j]=1;
        }
}

void solve ()
{
    int i,j,val,start,newstart;
    double max_val;

    for (i=2; i<=N; ++i)
        lg2[i]=log (i);

    val=0; cnt[0]=1;
    for (i=1; i<=N; ++i)
        for (j=val; j>=0; --j)
            if (cnt[j] && j+prim[i]<=N)
            {
                if (bst[j]+lg2[prim[i]]>bst[j+prim[i]])
                {
                    bst[j+prim[i]]=bst[j]+lg2[prim[i]];
                    cnt[j+prim[i]]=cnt[j]+1;
                    ant[j+prim[i]]=prim[i];
                }

                val=max (val,j+prim[i]);
            }

    max_val=0; start=0;
    for (i=1; i<=N; ++i)
        if (cnt[i]>2)
            if (bst[i]>max_val)
            {
                max_val=bst[i];
                start=i;
            }

    if (start!=N)
    {
        max_val=0; newstart=0;
        for (i=1; i<=N; ++i)
            if (cnt[i]>1)
                if (bst[i]>max_val)
                {
                    max_val=bst[i];
                    newstart=i;
                }
        if (newstart!=N)
        {
            printf ("%d ",(N-newstart)*(M/N));
            for (val=newstart; val; val-=ant[val])
                printf ("%d ",ant[val]*(M/N));
        }
        else
        {
            printf ("%d ",(N-start)*(M/N));
            for (val=start; val; val-=ant[val])
                printf ("%d ",ant[val]*(M/N));
        }
    }
    else
    {
        for (val=start; val; val-=ant[val])
            printf ("%d ",ant[val]*(M/N));
    }
}

int main ()
{
    freopen ("nummst.in","r",stdin);
    freopen ("nummst.out","w",stdout);

    read ();

    if (!(N%2))
    {
        printf ("%d %d",M/2,M/2);
        return 0;
    }

    if (!(N%3))
    {
        printf ("%d %d",M/3,2*M/3);
        return 0;
    }

    solve ();

    return 0;
}