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 iesire

Fișierul clatite.out conține pe prima line numărul total de clătite mâncate de Arpsod iar pe 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ă).

Restricții și precizări

• 0 ⩽ N, M ⩽ 300.000

Exemplu

clatite.in

3 11

clatite.out

Datele introduse corespund restricțiilor impuse.

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

<syntaxhighlight lang="python" line> import math

def pp(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 sd(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

def main():

   with open("clatite.in", "r") as f:
       n, m = map(int, f.readline().split())
       p = int(f.readline())

   if not validare_date(n, m):
       print("Datele de intrare 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 pp(i):
           g += 1
       elif sd(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(str(total) + "\n")
       f.write(f"{c} {g} {ing} {z} {s}")

if __name__ == "__main__":

   main()

</syntaxhighlight>