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$.

Spre exemplu:

• $1! = 1$;
• $2! = 1 \cdot 2 = 2$;
• $3! = 1 \cdot 2 \cdot 3 = 6$;
• $K! = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot K$.

Orice număr natural $N$ poate fi descompus cu ajutorul numerelor factoriale astfel:
$N = 1! f_1 + 2! f_2 + 3! f_3 + \ldots + m! f_m$,
unde coeficienții $f_i$, cu $1 \leq i \leq m$ sunt numere naturale și în plus $f_m \neq 0$.

Spre exemplu:

• $20 = 1! \cdot 20$;
• $20 = 1! \cdot 6 + 2! \cdot 4 + 3! \cdot 1$;
• $20 = 1! \cdot 0 + 2! \cdot 1 + 3! \cdot 3$.

Dintre toate aceste descompuneri posibile există o singură descompunere, numită descompunere în bază factorială care respectă suplimentar condițiile $0 \leq f_i \leq i$, cu $1 \leq i < m$ și $0 < f_m \leq m$.

Spre exemplu:

• $6 = 1! \cdot 0 + 2! \cdot 0 + 3! \cdot 1$;
• $17 = 1! \cdot 1 + 2! \cdot 2 + 3! \cdot 2$;
• $119 = 1! \cdot 1 + 2! \cdot 2 + 3! \cdot 3+ 4! \cdot 4$.

Cerinţă

Scrieți un program care rezolvă următoarele 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 bază factorială a acestuia.

Date de intrare

Fişierul de intrare este bazaf.in.

Acesta conţine pe prima linie 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 \geq 0$, cu $1 \leq i < m$ și $f_m \neq 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 lui $V$ este $1$ atunci fișierul de ieșire va conţine descompunerea în bază factorială a numărului $X$, iar dacă valoarea lui $V$ este $2$ atunci fișierul de ieșire va conține descompunerea în bază 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 \leq f_i \leq i$, cu $1 \leq i < m$ și $0 < f_m \leq m$, despărțite prin câte un spațiu, având semnificația de mai sus.

Restricții și precizări

• $2 \leq X \leq {10}^{15}$
• $1 < m \leq 100\ 000$
• $0 \leq f_i \leq {10}^9$
• 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 $3$ termeni și este formată din coeficienții $1$, $2$, $2$ ($17 = 1! \cdot 1 + 2! \cdot 2 + 3! \cdot 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! \cdot 0 + 2! \cdot 1 + 3! \cdot 3$).