0971 - Max

Cerinţa

În zorii zilei, harnicele albinuţe se pregătesc să zboare la cules de nectar. În apropierea stupului, se află o grădină fermecată cu N flori, numerotate 1, 2,… N. Pentru fiecare floare se cunoaște numărul de petale.

Anumite flori din grădină pot fi flori capcană. O astfel de floare are un număr prim de petale. Dacă o albină s-ar aşeza pe corola florii capcană, atunci floarea i-ar fura o cantitate de nectar egală cu numărul ei de petale.

Alte flori pot fi florile abundenţei. Numărul de petale ale florii abundenţei are un număr impar de divizori. Dacă o albină s-ar aşeza pe corola unei astfel de flori, atunci ea i-ar dărui albinuţei o cantitate de nectar egală cu triplul numărului ei de petale.

Celelalte flori pot fi flori obişnuite. Dacă o albină s-ar aşeza pe corola unei flori obişnuite, atunci floarea i-ar dărui albinuţei o cantitate de nectar egală cu numărul ei de petale.

Regina stupului, le-a poruncit albinuţelor să adune cea mai mare cantitate de nectar care se poate culege din grădină, altfel … vor fi alungate din stup.Scrieţi un program care să citească numerele naturale N și numărul de petale ale fiecărei flori şi care să determine cantitatea maximă C de nectar pe care albinuţele o pot aduna din grădina fermecată.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând numărul de petale ale fiecărei flori.

Date de ieşire

Programul va afișa pe ecran numărul C.

Restricții și precizări

• 1 ≤ n ≤ 100 000
• fiecare floare are cel mult 10 000 petale
• nectarul unei flori poate fi cules de o singură albină
• cantitatea maximă C de nectar culeasă este un număr natural, C ≤ 2 000 000 000

Exemplu

Intrare

8

25 13 10 7 1 12 31 102

Ieșire

202

Explicație

Cantitatea maximă de nectar se obţine din florile 1, 3, 5, 6 şi 8. C=3x25+10+3x1+12+102=202

Rezolvare

<syntaxhighlight lang="python" line> def is_prime(n):

   if n < 2:
       return False
   for i in range(2, int(math.sqrt(n))+1):
       if n % i == 0:
           return False
   return True

def num_divisors(n):

   count = 0
   for i in range(1, int(math.sqrt(n))+1):
       if n % i == 0:
           count += 2
           if i * i == n:
               count -= 1
   return count

def get_nectar(flower):

   if is_prime(flower):
       return -flower
   elif num_divisors(flower) % 2 == 1:
       return 3 * flower
   else:
       return flower

def validare_date(n, flowers):

   if not (1 <= n <= 100000):
       return False
   if any(not (1 <= f <= 10000) for f in flowers):
       return False
   return True

if __name__ == '__main__':

   n = int(input())
   flowers = [int(x) for x in input().split()]
   
   if validare_date(n, flowers):
       C = sum(get_nectar(f) for f in flowers)
       print(C)
   else:
       print("Datele de intrare nu corespund restricțiilor impuse.")

</syntaxhighlight>

Explicație rezolvare

Acest program calculează suma unor numere, în funcție de proprietățile numerelor respective.

Mai întâi, sunt definite trei funcții:

• is_prime(n): returnează True dacă numărul n este prim și False în caz contrar.
• num_divisors(n): returnează numărul de divizori ai numărului n.
• get_nectar(flower): returnează un număr în funcție de proprietățile florii. Dacă floarea are un număr prim de petale, se returnează negativul numărului de petale. Dacă floarea are un număr impar de divizori, se returnează triplul numărului de petale. În celelalte cazuri, se returnează numărul de petale.

Apoi, este definită funcția validare_date(n, flowers), care primește ca parametri numărul n de flori și lista flowers cu numărul de petale al fiecărei flori. Această funcție verifică dacă valorile introduse respectă restricțiile impuse în enunțul problemei.

În funcția principală (__main__), se citesc valorile de intrare și se verifică dacă acestea sunt valide folosind funcția validare_date(). Dacă datele sunt valide, se calculează suma numerelor obținute prin aplicarea funcției get_nectar() pe fiecare element din lista flowers, și se afișează valoarea calculată. În caz contrar, se afișează un mesaj de eroare.