1748 - Cursa
Sursă: [1]
Cerință
Costică este alergător la un maraton. El parcurge un traseu sub forma unei matrice cu n linii şi m coloane linie cu linie şi pe fiecare linie, de la stânga la dreapta. Matricea conţine numere naturale. Dacă Costică întâlneşte un număr prim, el este penalizat, fiind trimis pe linia şi coloana anterioară, iar dacă acesta întâlneşte un număr perfect, poate avansa pe linia şi coloana următoare. Dacă mişcarea pe linie şi pe coloană depăşeşte limitele matricei, atunci se va efectua numai mişcarea care nu trece de aceste limite sau nu se va efectua nici o mişcare. Afişaţi timpul t în care parcurge Costică traseul, ştiind că deplasarea dintr-un element al matricei în oricare altul durează o secundă, iar fiecare penalizare sau avansare durează o secundă. Un număr este perfect dacă suma cifrelor lui este un număr prim. Dacă un număr este şi prim şi perfect, atunci el va fi considerat prim. După penalizare sau avansare, numerele prime sau perfecte îşi pierd proprietățile.
Date de intrare
Programul citește de la tastatură numerele n şi m, iar apoi 'n*m numere naturale, separate prin spații.
Date de ieșire
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.". Programul va afișa pe ecran numărul t, reprezentând timpul în care Costică parcurge traseul. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".
Restricții și precizări
- 1 ≤ n,m ≤ 500
- cele n numere citite vor fi mai mici decât 1.000.000
Exemple
Exemplu 1
- Date de intrare
- 4 5
- 6 9 3 2 1
- 8 3 12 4 0
- 1 1 34 8 7
- 5 3 5 9 8
- Date de ieșire
- 28
Explicatie
2 3 5 7 sunt numere prime, iar 2 3 5 7 12 34 sunt numere perfecte.
Rezolvare
def citire_matrice():
try:
n = int(input("Introduceti numarul de linii: "))
m = int(input("Introduceti numarul de coloane: "))
if 2 <= n <= 500 and 2 <= m <= 500:
print("Datele sunt corecte.")
else:
print("Datele nu sunt conform restrictiilor impuse.")
exit()
except ValueError:
print("Trebuie introduse doar numere intregi.")
exit()
matrice = []
for linie in range(n):
matrice.append([])
for coloana in range(m):
for i in range(3):
try:
valoare = int(input(f"Introduceti un numar pentru linia {linie+1}, coloana {coloana+1}: "))
if 0 <= valoare <= 10**6:
print("Datele sunt corecte.")
matrice[linie].append(valoare)
break
else:
print("Datele nu sunt conform restrictiilor impuse.")
except ValueError:
print("Trebuie introduse doar numere intregi.")
else:
print("Prea multe incercari esuate.")
exit()
return matrice
def este_prim(numar):
if numar < 2:
return False
for i in range(2, int(numar**0.5)+1):
if numar % i == 0:
return False
return True
def este_perfect(numar):
suma_cifre = sum(int(cifra) for cifra in str(numar))
return este_prim(suma_cifre)
def Cursa(matrice):
n = len(matrice)
m = len(matrice[0])
timp = 0
linie = 0
coloana = 0
while True:
if linie < 0 or linie >= n or coloana < 0 or coloana >= m:
break
valoare = matrice[linie][coloana]
if este_prim(valoare) or (este_perfect(valoare) and este_prim(sum(int(cifra) for cifra in str(valoare)))): # adăugare verificare pentru suma cifrelor
timp += 1
if linie == 0 and coloana == 0:
break
else:
linie, coloana = linie - 1, coloana - 1
if linie < 0 or coloana < 0: # adăugare verificare pentru depășirea matricei
break
valoare = matrice[linie][coloana]
este_prim(valoare)
este_perfect(valoare)
else:
timp += 1
if este_perfect(valoare):
linie, coloana = linie + 1, coloana + 1
if linie >= n or coloana >= m: # adăugare verificare pentru depășirea matricei
break
valoare = matrice[linie][coloana]
este_prim(valoare)
este_perfect(valoare)
else:
coloana += 1
return timp
if _name_ == "_main_":
matrice = citire_matrice()
t = Cursa(matrice)
print(f"Costica a parcurs traseul in {t} secunde.")
Explicatie
Acest cod începe prin definirea a trei funcții: citire_matrice(), este_prim(numar) și este_perfect(numar), urmate de funcția Cursa(matrice) care este apelată în if _name_ == "_main_":.
Funcția citire_matrice() citeste numarul de linii și coloane ale matricei de la tastatură, verifică dacă acestea respectă condițiile impuse și apoi citeste elementele matricei de la tastatură. Pentru fiecare element introdus, se verifică dacă îndeplinește condițiile impuse și se reia citirea de la tastatură până când se introduce un număr valid. Matricea este stocată într-o listă de liste și este returnată la sfârșitul funcției. Funcția este_prim(numar) primește un număr întreg și verifică dacă este prim sau nu. Verificarea se face prin împărțirea numărului la toate numerele întregi de la 2 la rădăcina pătrată a numărului. Dacă numărul se divide fără rest la unul dintre aceste numere, atunci nu este prim.
Funcția este_perfect(numar) primește un număr întreg și verifică dacă suma cifrelor sale este un număr prim. În interiorul funcției, mai întâi se calculează suma cifrelor numărului, apoi se verifică dacă aceasta este primă, folosind funcția este_prim(numar).
Funcția Cursa(matrice) primește o matrice și calculează timpul necesar pentru a parcurge traseul descris în enunțul problemei. Se începe de la primul element al primei linii și se deplasează în sus și în stânga, la fiecare pas verificându-se dacă elementul curent îndeplinește condițiile impuse. Dacă da, se incrementează timpul și se deplasează în sus și în stânga, altfel se incrementează timpul și se deplasează în dreapta. Se continuă acest proces până când se ajunge la primul element al primei linii sau se depășește limita matricei. Timpul total este returnat la sfârșitul funcției.
În blocul if _name_ == "_main_":, se citește matricea de la tastatură, se calculează timpul necesar pentru a parcurge traseul folosind funcția Cursa(matrice) și se afișează rezultatul.
