Cod sursa(job #3135942)

Utilizator tudor.pistolPistol Tudor tudor.pistol Data 4 iunie 2023 19:17:55
Problema Planeta Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

ifstream fin("planeta.in");
ofstream fout("planeta.out");
int n, k;
vector <int> noduri;

bool esteABCPreord(int stanga, int dreapta, vector <int> v)
{
    //am ajuns la frunza => termin recursia
    if(stanga >= dreapta)
        return true;
    else
    {
        int i = stanga;
        //caut pana la gasirea unui element mai mare (adica parcurg subarborele stang)
        while(v[i] <= v[stanga] && i <= dreapta)
            i++;
        //de la elementul mai mare incolo incepe subarborele drept => fiecare element trebuie sa fie mai mare decat radacina
        for(int j = i; j <= dreapta; j++)
            if(v[j] < v[stanga])
                return false;
        //testez recursiv pentru fiecare nod
        return esteABCPreord(stanga+1, i-1, v) && esteABCPreord(i, dreapta, v);
    }
}
int main()
{
    fin >> n >> k;
    for(int i = 1; i <= n; i++)
        noduri.push_back(i);
    
//generez toate permutarile posibile in ordine lexicografica si verific daca sunt abc in preordine
    int i = 0;
    do
    {
        if(esteABCPreord(0, n-1, noduri))
        {
            i++;
            if(i == k)
            {
                for(int i = 0; i < n; i++)
                    fout << noduri[i] << " ";
                break;
            }
        }
    } while(next_permutation(noduri.begin(), noduri.end()));
    return 0;
}