0819 - Generare 1
De la Universitas MediaWiki
Cerința
Se consideră următoarele operații, care se aplică numerelor naturale:
op 1
– se adaugă la număr cifra4
– din13
se obține134
op 2
– se adaugă la număr cifra0
– din13
se obține130
op 3
– dacă numărul este par, se împarte la2
– din20
se obține10
Dându-se un număr natural n
, să se determine un șir de operații dintre cele de mai sus prin care, pornind de la valoarea 4
, se ajunge la n
.
Date de intrare
Programul citește de la tastatură numărul n
.
Date de ieșire
Programul va afișa pe ecran un șir de valori din mulțimea {1,2,3}
, astfel încât, aplicând în ordine operațiile corespunzătoare se ajunge de la valoarea 4
la valoarea n
.
Restricții și precizări
1 ≤ n ≤ 100.000
Exemplul 1
Input:
5
Output:
3 3 2 3
Explicație:
Pornim de la 4
. Se aplica op 3
și se obține 2
; se aplică op 3
și se obține 1
; se aplică op 2
și se obține 10
; se aplică op 3
și se obține 5
.
Exemplul 2
Input:
9999999999999
Output:
Constrangeri neindeplinite
Rezolvare
def ver(n):
if not(1<=n<=100000):
print("Constrangeri neindeplinite")
exit()
v = [0] * 10000
op = [0] * 10000
nv = 0
# 1 -> se adauga 4
# 2 -> se adauga 0
# 3 -> se imparte la 2, daca este par
n = int(input())
ver(n)
gata = False
nv += 1
v[nv] = n
while not gata:
if n == 4:
gata = True
else:
if n % 10 == 4:
nv += 1
op[nv] = 1
n //= 10
elif n % 10 == 0:
nv += 1
op[nv] = 2
n //= 10
else:
nv += 1
op[nv] = 3
n *= 2
v[nv] = n
for i in range(nv, 1, -1):
print(op[i], end=" ")