Cod sursa(job #586304)

Utilizator savimSerban Andrei Stan savim Data 30 aprilie 2011 14:26:22
Problema NumMst Scor 24
Compilator cpp Status done
Runda Algoritmiada 2011, Runda Finală, Clasele 10-12 Marime 1.43 kb
#include <stdio.h>
#include <math.h>

#define MAX_N 3500

int cmmdc, n, m;

int vine[MAX_N], prim[MAX_N], maxp[MAX_N];

double c[MAX_N];

void get_primes() {
	for (int i = 2; i <= m; i++) {
    	int ok = 1;

		for (int j = 2; j < i; j++)
			if (i % j == 0) {
            	ok = 0;
				break;
			}

		if (ok) {
			prim[++prim[0]] = i;

			int aux = i;
			for (int j = 1; j <= m; j++) {
				if (aux <= m)
					maxp[i] = j;
				else
					break;

		    	aux = aux * i;
			}
		}
	}
}

void write(int x) {
	if (x == 0) {
    	printf("\n");
		return;
	}

	printf("%d ", (x - vine[x])  * cmmdc);
	write(vine[x]);
}

int main() {

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

	scanf("%d", &n);
	
	for (int i = 2; i <= n; i++)
		if (n % i == 0) {
        	cmmdc = n / i;
            m = i;
			break;
		}

	get_primes();

/*	for (int i = 0; i <= m; i++)
    	vine[i] = i - 1;

	for (int i = 1; i <= prim[0]; i++) {
		int val = prim[i];

		for (int power = 1; power <= maxp[i]; power++) {

			for (int j = m; j >= 1; j--)
				if (val <= j && c[j] < c[j - val] * val && !(j == m && j - val == 0)) {
    				c[j] = c[j - val] * val;        	
                    vine[j] = j - val;
				}


			val = val * prim[i];
		}
	}*/

	if (m == 2)
		vine[2] = 1;
	else {
    	int x = m;
		for (int i = 1; i <= prim[0]; i++) 
			if (x >= prim[i]) {
				vine[x] = x - prim[i];
            	x -= prim[i];
			}
			else
				break;
	}
			

	write(m);

	return 0;
}