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
import math
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 validate_input(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 validate_input(n, flowers):
total_nectar = sum(get_nectar(f) for f in flowers)
print(total_nectar)
else:
print("Datele de intrare nu corespund restricțiilor impuse.")
Explicație rezolvare
Acest cod are ca scop calcularea cantității maxime de nectar care poate fi adunată dintr-o grădină cu flori, fiecare floare având o cantitate de nectar specifică. Anumite flori sunt considerate capcane și fură o cantitate de nectar dacă o albină se așează pe ele, în timp ce alte flori sunt considerate abundente și oferă o cantitate mai mare de nectar decât flori obișnuite. Se utilizează funcțiile is_prime, num_divisors și get_nectar pentru a determina tipul de floare și cantitatea de nectar corespunzătoare. De asemenea, se utilizează o funcție de validare a datelor de intrare pentru a verifica dacă acestea corespund restricțiilor impuse.