Pracsiu Dan (dnprx) Î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 ≤ 10151 < m ≤ 100 0000 ≤ f[i] ≤ 109- Pentru rezolvarea corectă a primei cerință se va acorda
30%din punctaj, iar pentru cea de-a doua cerință se va acorda70%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).