1902 - DouaMii17
Cerința
Primele 2017 numere naturale, având fiecare exact 2017 divizori naturali, s-au gândit la început de nou an să-şi pună divizorii împreună, în ordine crescătoare, astfel se vor amesteca şi vor mai socializa şi ei în mod democratic. Marele conducător KWI s-a gândit să bage zâzanie între ei şi a început să le pună n întrebări de genul “-Domnule x, faci cumva parte din societatea secretă a divizorilor celor 2017 numere cu câte 2017 divizori?”. Să sperăm că până în anul 2017 va primi toate răspunsurile şi toată lumea va fi fericită.
Date de intrare
Fișierul de intrare douamii17.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații, pentru care trebuie să verificăm dacă se află în şirul divizorilor primelor 2017 numere naturale care au exact 2017 divizori fiecare.
Date de ieșire
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul de ieșire douamii17.out va conține pe linia i, pentru fiecare i de la 1 la n, 1 dacă al i-lea număr de pe linia a doua a fişierului de intrare se află în şirul divizorilor şi 0 altfel.
În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".
Restricţii şi precizări
- 1 ≤ n ≤ 1.000.000
- numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 500.000.000
Exemple
Exemplul 1
- douamii17.in
- 5
- 1 2 18 23 9
- ecran
- Datele sunt introduse corect.
- douamii17.out
- 1
- 1
- 0
- 1
- 1
Exemplul 2
- douamii17.in
- 5
- 10 20 30 40 50
- ecran
- Datele sunt introduse corect.
- douamii17.out
- 0
- 0
- 0
- 0
- 0
Exemplul 3
- douamii17.in
- 3
- -5 1000000000 2000000000
- ecran
- Datele nu corespund restricțiilor impuse.
- douamii17.out
Rezolvare
<syntaxhighlight lang="python" line="1">
- 1902 - DouaMii17
import math
def is_valid(n, nums):
if n < 1 or n > 1000000:
return False
for num in nums:
if num < 1 or num >= 500000000:
return False
return True
def calculate_divisors():
b = [0] * 20001
p = []
a = [0] * (500000001)
nr = 0
i = 2
while nr < 2017:
if b[i] == 0:
nr += 1
p.append(i)
j = i * i
while j < 20000:
b[j] = 1
j = j + i
i += 1
a[1] = 1
for i in range(2017):
j = p[i]
while j < 500000000:
a[j] = 1
j = j * p[i]
return a
if __name__ == "__main__":
with open("douamii17.in") as fin:
n = int(fin.readline().strip())
nums = list(map(int, fin.readline().strip().split()))
if not is_valid(n, nums):
print("Datele nu corespund restricțiilor impuse.")
exit(0)
divisors = calculate_divisors()
print("Datele sunt introduse corect.")
with open("douamii17.out", "w") as fout:
for num in nums:
fout.write(str(divisors[num]) + "\n")
</syntaxhighlight>
Explicatie
is_valid(n, nums): Această funcție primește doi parametri, n și nums. Verifică dacă numărul de elemente din lista nums este cel puțin 1 și cel mult 1.000.000 și dacă fiecare element din listă este mai mare decât 0 și mai mic decât 500.000.000. În cazul în care aceste condiții sunt îndeplinite, funcția returnează True, în caz contrar returnează False.
calculate_divisors(): Această funcție calculează șirul de divizori pentru primele 2017 numere naturale care au exact 2017 divizori.
Folosește două liste, b și p, pentru a marca numerele prime și numerele prime anterioare din șirul de divizori. După ce lista p este completată cu primele 2017 numere prime, funcția calculează divizorii pentru fiecare număr prim, înmulțindu-l cu el însuși, apoi cu fiecare număr prim anterioară din șir, până când ajunge la 500.000.000.
Rezultatul este returnat sub formă de listă, unde fiecare element are valoarea 1 dacă se află în șirul de divizori, sau 0 altfel.
main(): Această funcție este punctul de intrare în program.
Verifică dacă datele de intrare sunt valide, apoi apelează funcția calculate_divisors() pentru a obține șirul de divizori. Rezultatul este scris în fișierul douamii17.out și afișat pe ecran.