1517 - Clatite
Enunț
Arpsod adoră două lucruri: matematica și clătitele bunicii sale. Într-o zi, aceasta s-a apucat să prepare clătite. Arpsod mănâncă toate clătitele începând de la a N-a clătită preparată, până la a M-a clătită preparată (inclusiv N și M). Pentru că el vrea să mănânce clătite cu diferite umpluturi și-a făcut următoarea regulă:
“Dacă numărul de ordine al clătitei este prim atunci aceasta va fi cu ciocolată. Dacă numărul de ordine este pătrat perfect sau cub perfect aceasta va fi cu gem. Dacă suma divizorilor numărului este egală cu însuși numărul de ordine atunci aceasta va fi cu înghețată. (se iau în considerare toți divizorii în afară de numărul în sine, inclusiv 1).
În cazul în care o clătită îndeplinește simultan mai multe condiții, se respectă prioritatea sortimentelor: ciocolată > gem > înghețată. Dacă niciuna dintre condițiile de mai sus nu este îndeplinită, pentru cele cu numărul de ordine par, clătita va fi cu zahar, iar pentru numărul de ordine impar, clătita va fi simplă.”
Cerinţa
Cunoscându-se N și M, numere naturale, să se determine câte clătite a mâncat Arpsod în total și numărul de clătite din fiecare tip.
Date de intrare
Fișierul clatite.in conține pe prima linie numerele N și M separate printr-un spațiu.
Date de ieșire
Dacă datele sunt introduse corect, în fișier se va afișa: "Datele sunt introduse corect.", apoi prima linie a fişierului de ieşire clatite.out va conține numărul total de clătite mâncate de Arpsod iar a doua linie 5 numere naturale separate printr-un spațiu reprezentând numărul de clătite mâncate, din fiecare tip (ordinea: ciocolata, gem, înghețată, zahăr, simplă).În cazul în care datele nu respectă restricțiile, se va afișa în fișier : "Datele nu corespund restricțiilor impuse.".
Restricții și precizări
- 0 ⩽ N, M ⩽ 300.000
Exemplu
- clatite.in
- 3 11
- clatite.out
- Datele sunt introduse corect.
- 9
- 4 3 1 1 0
Explicație
Arpsod a mâncat 9 clătite dintre care: 4 cu ciocolată ( 3, 5, 7, 11 ) 3 cu gem ( 4, 8, 9 ) 1 cu înghețată ( 6 ) 1 cu zahăr ( 10 ). 0 simple
Rezolvare
import math
def pătrat_perfect(n):
d = int(math.sqrt(n))
ok = 0
if d * d == n:
ok += 1
if ok == 0:
for i in range(1, int(n ** (1 / 3)) + 1):
if i * i * i == n:
ok += 1
if ok:
return True
else:
return False
def suma_divizori(n):
s = 1
for i in range(2, int(math.sqrt(n)) + 1):
if n % i == 0:
s += i + n // i
if i * i == n:
s -= i
if s == n:
return True
else:
return False
def prim(n):
cnt = 1
d = 2
while n > 1:
p = 0
while n % d == 0:
n //= d
p += 1
cnt *= (p + 1)
d += 1
if d * d > n:
d = n
if cnt == 2:
return True
else:
return False
def validare_date(n, m):
if not (1 <= n <= 300000) or not (1 <= m <= 300000):
return False
return True
if __name__ == "__main__":
with open("clatite.in", "r") as f:
n, m = map(int, f.readline().split())
p = 0
line = f.readline().strip()
if line:
p = int(line)
if not validare_date(n, m):
f.write("Datele nu corespund restricțiilor impuse.")
exit()
c = 0
g = 0
ing = 0
z = 0
s = 0
for i in range(n, m + 1):
if prim(i):
c += 1
elif pătrat_perfect(i):
g += 1
elif suma_divizori(i):
ing += 1
elif i % 2 == 0:
z += 1
else:
s += 1
total = c + g + ing + z + s
with open("clatite.out", "w") as f:
f.write("Datele sunt introduse corect.\n")
f.write(str(total) + "\n")
f.write(f"{c} {g} {ing} {z} {s}")
Explicație rezolvare
Funcția pătrat_perfect(n) verifică dacă numărul n este un pătrat perfect sau un cub perfect. Verificarea se face prin calcularea rădăcinii pătrate sau cubice a lui n și compararea cu valoarea întreagă a rădăcinii. Dacă rădăcina este egală cu valoarea întreagă, atunci n este pătrat perfect sau cub perfect și funcția returnează True. Dacă nu, se parcurge un alt interval și se verifică dacă n este cub perfect. Dacă n este cub perfect, funcția returnează True, altfel returnează False.
Funcția suma_divizori(n) calculează suma divizorilor lui n și verifică dacă aceasta este egală cu n. Suma divizorilor se calculează prin parcurgerea tuturor divizorilor lui n, cu excepția lui n și a lui 1, și adăugarea lor la o variabilă s. Dacă s este egală cu n, funcția returnează True, altfel returnează False.
Funcția prim(n) verifică dacă numărul n este prim și calculează numărul său de divizori. Pentru a verifica dacă n este prim, se împarte succesiv la divizorii mai mici sau egali cu rădăcina pătrată a lui n. Dacă n este divizibil cu un divizor, acesta este înmulțit cu un contor cnt și n este împărțit la acel divizor. Dacă n nu mai poate fi împărțit la vreun divizor mai mic sau egal cu rădăcina pătrată a lui n, atunci n este fie prim, fie este egal cu un produs de două numere prime care sunt mai mari decât rădăcina pătrată a lui n. În cazul în care n este prim, numărul de divizori este 2 și funcția returnează True. Dacă n nu este prim, numărul de divizori se calculează din contorul cnt și funcția returnează False.
Funcția validare_date(n, m) verifică dacă valorile n și m sunt cuprinse între 1 și 300000. Dacă nu sunt, funcția returnează False, altfel returnează True
Funcția main citește datele de intrare dintr-un fișier numit "clatite.in", validează dacă acestea respectă restricțiile impuse și apoi efectuează diferite calcule pe intervalele din intervalul [n, m], unde n și m sunt numerele citite inițial din fișierul de intrare.Se inițializează câteva variabile (c, g, ing, z, s) pentru a număra diferite tipuri de numere între n și m. Apoi, pentru fiecare număr între n și m, main verifică dacă numărul este prim, pătrat perfect, are suma divizorilor egală cu numărul, este par sau impar și mărește corespunzător variabila adecvată în funcție de ce tip de număr este.La sfârșit se afișează "Datele sunt introduse corect.", numărul total de numere de diferite tipuri găsite și numărul de numere din fiecare tip. Apoi, aceste informații sunt scrise într-un fișier numit "clatite.out".
