Cod sursa(job #3254350)

Utilizator KRISTY06Mateiu Ianis Cristian Vasile KRISTY06 Data 7 noiembrie 2024 12:16:05
Problema Farfurii Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

int n, k, fr[100001];

vector<int> minAns(100000, 100001);

bool isValid(vector<int> ans, int currentK) {
    int counter = 0;
    for (int i = 0; i < ans.size() - 1; ++i) {
        for (int j = i + 1; j < ans.size(); ++j) {
            if (ans[i] > ans[j]) {
                ++counter;
            }
        }
    }
    return counter == currentK;
}

void gen(vector<int> ans, int currentK) {
    if (ans.size() == n) {
        if (isValid(ans, currentK) == 1) {
            minAns = min(minAns, ans);
        }
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (fr[i] == 0) {
            fr[i] = 1;
            ans.push_back(i);
            gen(ans, currentK);
            ans.pop_back();
            fr[i] = 0;
        }
    }
}

int main() {
    fin >> n >> k;
  //  for (int i = 1; i <= (n - 1) * n / 2; ++i) {
       // minAns.assign(n, 100000);
        gen({}, k);
     //   cout << i << ": ";
        for (int i = 0; i < minAns.size(); ++i) {
            fout << minAns[i] << ' ';
        }
        fout << '\n';
   // }
    return 0;
}