#include <algorithm>
#include <iostream>
#include <iterator>
#include <locale>
#include <string>
#include <vector>
#include <ctime>
#include <map>
 
using namespace std;
 
struct JobsElement {
  unsigned int Num;
  unsigned int Duration;
  unsigned int Penalty;
  JobsElement(unsigned int iNum, unsigned int iDuration, unsigned int iPenalty):
    Num(iNum), Duration(iDuration), Penalty(iPenalty) {}
  bool operator<(const JobsElement& rhs) const {
    return (Num < rhs.Num);
  }
};
 
typedef vector<JobsElement> JobsType;
typedef map<unsigned int, double> RatioType;
 
// Распечатка вектора
void PrintVector(JobsType& iJobs, string iStr, string iEnd) {
  if (iStr.length())
    cout << iStr << endl;
  for (size_t i = 0; i < iJobs.size(); i++) {
    cout << iJobs[i].Num << ": {" << iJobs[i].Duration << "," << iJobs[i].Penalty << "}";
    cout << ((i < iJobs.size() - 1) ? ", " : "");
  }
  if (iEnd.length())
    cout << " " << iEnd;
  cout << endl;
}
 
// Вычисление суммарного штрафа для последовательности работ
auto Penalty(JobsType& iJobs) {
  int Ret = 0;
  for (size_t i = 0; i < iJobs.size(); i++)
    for (size_t j = i + 1; j < iJobs.size(); j++)
      Ret += iJobs[i].Duration * iJobs[j].Penalty;
  return Ret;
}
 
// Вычисление "взвешенных" штрафных коэфициентов
auto CountingRatio(JobsType& iJobs) {
  RatioType Ratio;
  for (unsigned int i = 0; i < iJobs.size(); i++) {
    int sum_r = 0;
    int sum_j = 0;
    for (unsigned int j = 0; j < iJobs.size(); j++) {
      if (i != j) {
        sum_j += iJobs[j].Duration;
        sum_r += iJobs[j].Penalty;
      }
    }
    double k1 = (iJobs[i].Penalty) / (double) sum_r;
    double k2 = (iJobs[i].Duration) / (double) sum_j;
    Ratio[i] = k1 / (double)k2;
  }
  JobsType Ret;
  std::copy(iJobs.begin(), iJobs.end(), std::back_inserter(Ret));
  std::sort(Ret.begin(), Ret.end(), [&](const JobsElement & iA, const JobsElement & iB)->auto {
    return !(Ratio[iA.Num] < Ratio[iB.Num]);
  });
  return Ret;
}
 
// Перебор и оценка вариантов
auto CountingBruteforce(JobsType& iJobs) {
  vector<pair<unsigned int, JobsType>> Tmp;
  do {
    int Pen = Penalty(iJobs);
    Tmp.push_back({Pen, iJobs});
  } while (std::next_permutation(iJobs.begin(), iJobs.end()));
  sort(Tmp.begin(), Tmp.end(), [&](const pair<unsigned int, JobsType>& iA, const pair<unsigned int, JobsType>& iB)->auto {
    return iA.first < iB.first;
  });
  for (auto&& i : Tmp)
    PrintVector(i.second, "", to_string(i.first));
}
 
// Подготовка нового вектора
void PrepareVector(JobsType& iJobs, const size_t iLen) {
  iJobs.clear();
  for (unsigned int i = 0; i < iLen; i++)
    iJobs.push_back(JobsElement(i, 1 + std::rand() % 9, 1 + std::rand() % 9));
}
 
// запуск теста
void RunTest(JobsType& iJobs, const size_t iNum) {
  PrintVector(iJobs, "Test #" + to_string(iNum) + ":\n------------------------------------------------------", "");
  auto Res = CountingRatio(iJobs);
  PrintVector(Res, "Result vector:", "");
  cout << "Result penalty: " << Penalty(Res) << endl;
  CountingBruteforce(iJobs);
  cout << endl;
}
 
int main() {
  std::srand(unsigned(std::time(0)));
  // Тест 1: ручное задание параметров и числа работ
  JobsType Jobs = {{0, 1, 1}, {1, 2, 3}, {2, 3, 2}};
  RunTest(Jobs, 1);
  // Тест 2
  PrepareVector(Jobs, 4);
  RunTest(Jobs, 2);
  // Тест 3
  PrepareVector(Jobs, 5);
  RunTest(Jobs, 3);
  // Тест 4
  PrepareVector(Jobs, 6);
  RunTest(Jobs, 4);
  return 0;
}