| Fişierul intrare/ieşire: | bazaf.in, bazaf.out | Sursă | ONI 2018, clasa a 9-a, ziua 1 |
| Autor | Ciprian Chesca | Adăugată de |  Serban Cercelescu •oldatlantian |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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! * f1 + 2! * f2 + 3! * f3 + ... + m! * fm
unde coeficienţii fi, cu 1 ≤ i ≤ m sunt numere naturale şi în plus fm ≠ 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 ≤ fi ≤ i, cu 1 ≤ i < m şi 0 < fm ≤ 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
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.
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:
- 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 fi , care respectă condiţiile fi ≥0 , cu 1≤i<m şi fm ≠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 fi , care respectă condiţiile 0 ≤ fi ≤ i, cu 1 ≤ i < m şi 0 < fm ≤ m, despărţite prin câte un spaţiu, având semnificaţia de mai sus.
Restricţii
- 2 ≤ X ≤ 1.000.000.000.000.000
- 1 ≤ m ≤ 100.000
- 0 ≤ fi ≤ 1.000.000.000
Exemplu
| 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) |
