Cod sursa(job #2588339)

Utilizator levladiatorDragutoiu Vlad-Ioan levladiator Data 24 martie 2020 17:45:47
Problema NumMst Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <cmath>

using namespace std;

ifstream cin ("nummst.in");
ofstream cout ("nummst.out");

const int NMAX = 450;
const int PMAX = 3190;

int n, m, d;

int prime[1 + NMAX];
double dp[2][1 + PMAX];
int poz[1 + NMAX][1 + PMAX];
int sol[1 + PMAX];

int main() {
  cin >> n;
  d = 2;
  while(n % d)
    d++;
  for(int i = 2; i < d; i++) {
    int j = 2;
    while(j <= i / 2 && i % j)
      j++;
    if(j == i / 2 + 1)
      prime[++m] = i;
  }
  for(int i = 1; i <= m; i++) {
    for(int j = 1; j <= d; j++)
      dp[i % 2][j] = dp[(i - 1) % 2][j];
    for(int j = prime[i]; j <= d; j *= prime[i]) {
      double tmp = log(j);
      for(int k = j; k <= d; k++) {
        if(dp[i % 2][k] < dp[(i - 1) % 2][k - j] + tmp) {
          dp[i % 2][k] = dp[(i - 1) % 2][k - j] + tmp;
          poz[i][k] = j;
        }
      }
    }
  }
  int nr = d;
  for(int i = m; i >= 1; i--) {
    if(poz[i][nr]) {
      sol[++sol[0]] = poz[i][nr];
      nr -= poz[i][nr];
    }
  }
  for(int i = 1; i <= nr; i++)
    sol[++sol[0]] = 1;
  d = n / d;
  for(int i = 1; i <= sol[0]; i++)
    cout << sol[i] * d << " ";
  return 0;
}