== include(page="template/taskheader" task_id="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$}.
De exemplu: $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$;
De exemplu: $20 = 1! * 20 = 1! * 6 + 2! * 4 + 3! * 1 = 1! * 0 + 2! * 1 + 3! * 3$
Între 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$.
De exemplu: $6 = 1! * 0 + 2! * 0 + 3! * 1; 17 = 1! * 1 + 2! * 2 + 3! * 2; 119 = 1! * 1 + 2! * 2 + 3! * 3 + 4! * 4$
În matematicăfactorialulunuinumăr natural nenulKeste notat cuK!şi este egal cu produsul numerelor naturale nenule mai mici sau egale cuK. Exemple:1! = 1;2! = 1·2 = 2;3! = 1·2·3 = 6,....,K! = 1·2·3·...·K.Orice număr natural Npoate fi descompus cu ajutorul numerelor factoriale astfel:mN1!f2!f3!f...m!f=⋅1+⋅2+⋅3++unde coeficienţii fi, cu 1≤ i≤ msunt numere naturale şi în plusfm≠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ţiile0 ≤ fi≤ i, cu 1≤ i<mşi0 < fm≤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;
h2. Cerinţe
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 baza factorială a acestuia.
1.Să se determinedescompunereaînbazăfactorialăa unui număr natural Xdat.
2.Cunoscând o descompunere oarecare a unui număr natural Ysăse determine descompunerea în bazăfactorialăa acestuia.
h2. Date de intrare
Fişierul de intrare este $bazaf.in$.
Acesta conţinepe primul rând un număr natural V care poate avea doar valorile 1 sau 2 cu următoarea semnificaţie:
Fişierul de intrare este bazaf.inAcesta conţinepe 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.
* 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 <tex> f_i </tex>, care respectă condiţiilefi≥0 , cu 1≤ i <mşifm≠0, despărţite princâte un spaţiu,cu semnificaţia de mai sus.
h2. 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.
În fişierul de ieşire $bazaf.out$ ...
h2. Restricţii
* $2 ≤ X ≤ 1.000.000.000.000.000$
* $1 ≤ m ≤ 100.000$
* $0 ≤ f{~i~} ≤ 1.000.000.000$
* <tex> 2 \leq X \leq 10^{15} </tex>
* <tex> 1 \leq m \leq 100000 </tex>
* <tex> 0 \leq f_i \leq 10^9 </tex>
h2. Exemplu
table(example). |_. bazaf.in |_. bazaf.out |_. Explicatie |
| 1
17
| 3 1 2 2
| V = 1, deci se rezolvă doar prima cerinţă.
X = 17 Descompunerea numărului X= 17 în bază factorială conţine 3 termeni şi
este formată din coeficienţii 1,2,2 (17 = 1!*1+2!*2+3!*2) |
| 2
2 10 5
| 3 0 1 3
| V= 2, deci se rezolvă doar a douacerinţă.
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 13 (20=1!*0+2!*1+3!*3)
|
table(example). |_. bazaf.in |_. bazaf.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="bazaf") ==
