Rezolvare completă PbInfo #2457 bazaf

În matematică factorialul unui număr natural nenul K este notat cu K! și este egal cu produsul numerelor naturale nenule mai mici sau egale cu K.
Exemple:
1! = 1
2! = 1•2 = 2
3! = 1•2•3 = 6
…
K! = 1•2•3•...•K.
Orice număr natural N poate fi descompus cu ajutorul numerelor factoriale astfel:
N = 1! • f[1] + 2! • f[2] + 3! • f[3] + ... + m! • f[m]
unde coeficienții f[i], cu 1 ≤ i ≤ m sunt numere naturale și în plus f[m] ≠ 0.
Exemple:
20 = 1!•20;
20 = 1!•6 + 2!•4 + 3!•1;
20 = 1!•0 + 2!•1+ 3!•3;
Dintre toate aceste descompuneri posibile există o singură descompunere, numită descompunere în bază factorială care respectă suplimentar condițiile 0 ≤ f[i] ≤ i, cu 1 ≤ i < m și 0 < f[m] ≤ m.
Exemple:
6 = 1!•0 + 2!•0 + 3!•1;
17 = 1!•1+ 2!•2 + 3!•2;
119 = 1!•1+ 2!•2 + 3!•3+ 4!•4;

Cerința

1. Să se determine descompunerea în bază factorială a unui număr natural X dat.
2. Cunoscând o descompunere oarecare a unui număr natural Y să se determine descompunerea în bază factorială a acestuia.

Date de intrare

Fișierul de intrare este bazaf.in. Acesta conţine pe primul rând un număr natural V care poate avea doar valorile 1 sau 2 cu următoarea semnificație:
- dacă valoarea lui V este 1, pe a doua linie a fișierului de intrare se găsește un număr natural X cu semnificația de mai sus;
- dacă valoarea lui V este 2, pe a doua linie a fișierului de intrare se găsește o descompunere a unui număr Y sub forma unui șir de valori naturale în care primul termen este m, urmat de m valori f[i], care respectă condițiile f[i] ≥ 0 , cu 1 ≤ i < m și f[m] ≠ 0, despărțite prin câte un spațiu, cu semnificația de mai sus.

Date de ieșire

Fișierul de ieșire este bazaf.out. Dacă valoarea V este 1 atunci fișierul de ieșire va conţine descompunerea în baza factorială a numărului X iar dacă valoarea V este 2 atunci fișierul de ieșire va conține descompunerea în baza factorială
a numărului Y.Descompunerea în bază factorială presupune scrierea în fișierul de ieșire a unei singure linii sub forma unui șir de valori naturale în care primul termen este m,urmat de m valori f[i], care respectă condițiile 0 ≤ f[i] ≤ i, cu 1 ≤ i < m și 0 < f[m] ≤ m, despărțite prin câte un spațiu, având semnificația de mai sus.

Restricții și precizări

  • 2 ≤ X ≤ 1015
  • 1 < m ≤ 100 000
  • 0 ≤ f[i] ≤ 109
  • Pentru rezolvarea corectă a primei cerință se va acorda 30% din punctaj, iar pentru cea de-a doua cerință se va acorda 70% din punctaj.

Exemplul 1:

bazaf.in

1
17

bazaf.out

3 1 2 2

Explicație

V = 1, deci se rezolvă doar prima cerință. X = 17. Descompunerea numărului X = 17 în bază factorială conține trei termeni și este formată din coeficienții 1, 2, 2 (17 = 1!•1+2!•2+3!•2);

Exemplul 2:

bazaf.in

2
2 10 5

bazaf.out

3 0 1 3

Explicație

V = 2, deci se rezolvă doar a doua cerință Descompunerea 2 10 5 este o descompunere cu 2 termeni având coeficienții 10, 5 și corespunde numărului Y = 20. Descompunerea în bază factorială a numărului Y = 20 va fi 3 0 1 3 (20 = 1!•0+2!•1+3!•3).

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema bazaf:

// student Posdarascu Daniel

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cassert>
using namespace std;

#define NMAX 100005

long long n;
int v[NMAX], p;

void findBazaFactoriala(long long n) {
    long long fact = 1, k;
    for(k = 1; ; k++) {
        if(fact * (k + 1) > n)
            break;
        fact *= (k + 1);
    }
    vector<int> answer;
    for(; k >= 1; k--) {
        answer.push_back(n / fact); 
        n %= fact;
        fact /= k;
    }
    
    int lim = answer.size();
    printf("%d ", lim);
    for(int i = lim - 1; i >= 0; i--)
        printf("%d ", answer[i]);
    printf("\n");
}

void solve1() {
    scanf("%lld",&n);
    assert(1 <= n && n <= 1LL * 1000000000000000);
    findBazaFactoriala(n);  
}

void solve2() {
    scanf("%lld",&n);
    assert(1 <= n && n <= 100000);
    for(int i = 1; i <= n; i++) {
        assert(0 <= v[i] && v[i] <= 1000000000);
        scanf("%d",&v[i]);
    }
    
    for(long long i = 1; i <= n || v[i] > 0; i++) {
        v[i + 1] += v[i] / (i + 1);
        v[i] %= (i + 1);
        n = max(n, i);
    }
    
    printf("%lld ", n);
    for(int i = 1; i <= n; i++) {
        printf("%d ", v[i]);
    }
    printf("\n");
}

int main () {

    freopen("bazaf.in","r",stdin);
    freopen("bazaf.out","w",stdout);
    
    scanf("%d", &p);
    assert(1 <= p && p <= 2);
    if(p == 1) {
        solve1();
    }
    else {
        solve2();
    }   
    
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2457 bazaf

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2457 bazaf de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!