Sari la conținut

Autor: Ștefan-Cosmin Dăscălescu

Cunoștințe necesare

Soluția problemei partit (OJI 2020, clasele XI-XII)#

Link problemă

Această problemă poate fi accesată aici.

Pentru a rezolva această problemă, va trebui să observăm mai întâi faptul că pentru un număr dat \(n\), există \(2^{n-1} - 1\) partiții cu suma \(n\), lucru ce se poate demonstra destul de ușor folosind inducție, ideea de bază fiind că dacă știm numărul de partiții pentru \(1, 2, \dots, n-1\), vom putea extinde partiția cu diferența dintre \(n\) și acea sumă.

Pentru a afla cea de-a \(k\)-a partiție în ordine lexicografică, vom putea merge din aproape în aproape să vedem câte partiții încep cu fiecare număr de la \(1\) la \(n\) (acest lucru se poate face fie folosind formule matematice, fie folosind o recurență foarte simplă), iar implementarea se poate face fără probleme recursiv.

Pentru a afla numărul de ordine al unei partiții, vom proceda similar, ținând cont de numărul de partiții care încep cu un anumit număr și au o anumită sumă. Din nou, se poate proceda din aproape în aproape, iar deoarece valorile pentru \(n\) și numerele de ordine ale partițiilor sunt destul de mici, complexitatea va fi una foarte bună, permițând chiar și unor soluții mai incete să ruleze în timp bun.

Mai jos puteți găsi o soluție neoficială care ia punctajul maxim.

#include <fstream>

std::ifstream cin("partit.in");
std::ofstream cout("partit.out");

int c, n, v[10002];
long long k, dp[10002];

void solve(int n, long long k) {
    if (n == 0) {
        return;
    }
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        if (sum + dp[n - i] < k) {
            sum = sum + dp[n - i];
        } 
        else {
            cout << i << " ";
            solve(n - i, k - sum);
            break;
        }
    }
}
int main() {
    cin >> c >> n;
    dp[0] = 1;
    for (int i = 1; i <= 10000; ++i) {
        if (i >= 61) {
            dp[i] = (1LL << 60);
        } 
        else {
            dp[i] = (1LL << (i - 1));
        }
    }
    if (c == 1) {
        cin >> k;
        solve(n, k);
    } 
    else {
        int x = 0;
        int n2 = n;
        while (n2) {
            int nr;
            cin >> nr;
            v[++x] = nr;
            n2 = n2 - nr;
        }
        long long ord = 1;
        for (int i = 1; i <= x; ++i) {
            for (int j = 1; j < v[i]; ++j) {
                ord = ord + dp[n - j];
            }
            n -= v[i];
        }
        cout << ord << '\n';
    }
    return 0;
}