Cod sursa(job #589467)

Utilizator Robert_MarksonTiberiu Popa Robert_Markson Data 12 mai 2011 16:38:39
Problema NumMst Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <stdio.h>
#include <math.h>
#include <assert.h>

int get_best(int n, int gcd)
{
	int i, k, q, r;
	int max_pos;
	double sum, max_sum;

	max_sum = 0;
	max_pos = -1;
	for (k = 1; k <= n; k++) {
		q = n / k;
		r = n % k;
		sum = 0;
		q++;
		for (i = 0; i < k; i++) {
			if (i == r)
				q--;
			sum += log(q);
		}
		sum += k * log(gcd);
		if (sum > max_sum) {
			max_sum = sum;
			max_pos = k;
		}
		//printf("k=%d sum=%lf\n", k, sum);
	}
	//printf("max_pos=%d max_sum=%lf\n", max_pos, max_sum);

	return max_pos;
}

int main()
{
	int n, k, p = -1;
	int q, r;
	int split;

	if (freopen("nummst.in", "rt", stdin) == NULL)
		return 1;

	scanf("%d", &n);

	if ((n & 1) == 0) {
		p = 2;
	} else {
		for (k = 3; k * k <= n; k++)
			if (n % k == 0) {
				p = k;
				break;
			}
	}
	assert(p > 0);
	split = get_best(p, n / p);

	//printf("p=%d split=%d\n", p, split);
	q = p / split;
	r = p % split;
	q++;
	for (k = 0; k < split; k++) {
		if (k == r)
			q--;
		printf("%d ", q * (n / p));
	}
	printf("\n");

	return 0;
}