Probleme rezolvate

Problema partit

Fie PN = numărul de partiții ale lui N.

Dacă setăm valoarea primului element din partiție ca fiind:

• 1 => Numărul partițiilor rămase este PN-1
• 2 => Numărul partițiilor rămase este PN-2
• …
• K => Numărul partițiilor rămase este PN-K

Deci, avem:

• PN = PN-1 + PN-2 + ... + P1 + P0

Dar:

• PN-1 = PN-2 + PN-3 + ... + P1 + P0

Deci:

• PN = 2 * PN-1

Deci:

• PN = 2N-1 * P1 => PN = 2N-1

Se poate observa că în problemă nu ne interesează partiția N = N, deci PN = 2N-1 - 1.

Soluție #1 (programare dinamică)

Ne vom construi o tabelă:

• dp[i] = numărul de partiționări ale numărului i

Pentru a reconstrui soluția ne vom plimba prin valorile tabelei, similar ca la multe alte probleme discutate anterior.

Soluție #2 (directă)

Subpunctul #1

Avem 2N-1 partiții ale lui N. Dintre acestea, 2N-2 încep cu 1, iar celelalte încep cu un număr mai mare decât 1.

Deci, ne putem construi o funcție recursivă care:

• Dacă K <= 2N-2, putem afișa 1 și apelăm recursiv pentru N-1.
• Altfel
  • Partiția începe cu 2 dacă se află în prima jumătate din restul partițiilor
  • Partiția începe cu 3 dacă se află în prima jumătate din restul partițiilor (cele care nu încep nici cu 1, nici cu 2)
  • …

Deci funcția va căuta elementul care trebuie pus pe prima poziție, urmând să se apeleze recursiv pentru a extrage rezultatul pentru restul sumei.

Exemplu implementare:

void solve(FILE* fout, int n, int64 k) {
    if (n > 62) {
        fprintf(fout, "1 ");
        solve(fout, n - 1, k);
        return;
    }
    if (n == 0)
        return;
    
    int elem;
    
    elem = 1;
    while (elem < n && k > (1LL << (n - elem - 1))) {
        k -= (1LL << (n - elem - 1));
        ++elem;
    }
    
    fprintf(fout, "%d ", elem);
    solve(fout, n - elem, k);
}

Subpunctul #2

Rezolvarea se bazează pe aceleași observații folosite la primul subpunct.

Exemplu implementare:

        k = 1;
        while (fscanf(fin, "%d", &x) == 1) {
            // 2^(n-2) + 2^(n-3) + ... + 2^(n-x-1)
            // 2^(n-1)-1 - (2^(n-x)-1)
            k += (1LL << (n - 1)) - (1LL << (n - x));
            n -= x;
        }
        
        fprintf(fout, "%lld\n", k);