Cod sursa(job #586014)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 30 aprilie 2011 13:15:33
Problema NumMst Scor 0
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.25 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

int N;
int c1, c2;
vector <int> b, sol;

int CMMDC( int x, int y ) {

    int r;

    do {

        r = x % y;
        x = y;
        y = r;
    }
    while( r );

    return x;
}

void Back( int cnt ) {

    int i, mn, div, prod;

    if( cnt == 0 && b.size() >= 2 ) {

        div = CMMDC( b[0], b[1] );
        prod = b[0] * b[1];
        for( i = 3; i < (int)b.size(); ++i ) {

            div = CMMDC( div, b[i] );
            prod *= b[i];
        }
        if( div > c1 ) {

            c1 = div;
            c2 = prod / div;
            sol = b;
        }
        else if( div == c1 && prod / div > c2 ) {

            c2 = prod / div;
            sol = b;
        }
    }

    if( b.empty() )
        mn = 1;
    else
        mn = b.back();
    for( i = mn; i <= cnt; ++i ) {

        b.push_back( i );
        Back( cnt - i );
        b.pop_back();
    }
}

int main() {

    ifstream fin( "nummst.in" );
    ofstream fout( "nummst.out" );

    int i;

    fin >> N;

    Back( N );

    for( i = 0; i < (int)sol.size(); ++i )
        fout << sol[i] << " ";

    fin.close();
    fout.close();

    return 0;
}