1694 - Norocos

Sursa: [1]

Cerinţa

Un număr natural nenul m se numește norocos dacă pătratul lui se poate scrie ca sumă de m numere naturale consecutive. Un număr natural m se numește k-norocos, dacă este egal cu produsul a exact k numere prime distincte. Observați că între cele două proprietăți definite nu există nicio legătură.

Dându-se k și N numere naturale, scrieți un program care să determine:

a) Cel mai mic și cel mai mare număr norocos dintre cele N numere citite b) Câte numere k-norocoase sunt în șirul de N numere citite

Date de intrare

Programul conține pe prima linie un număr natural C. Pentru toate testele de intrare, numărul C are una din valorile 1 sau 2. Pe linia a doua a programul se găsesc numerele naturale N și k, cu semnificația din enunț, iar pe a treia linie se găsesc N numere naturale, separate prin câte un spațiu.

Date de ieșire

Dacă C=1, se va rezolva numai punctul a). În acest caz, în program se vor scrie, separate printr-un spațiu, în această ordine, cel mai mic și cel mai mare număr norocos dintre cele N numere citite. Dacă nu există niciun număr norocos se va afișa valoarea 0. Dacă există un singur număr norocos, acesta se va afișa de două ori.

Dacă C=2, se va rezolva numai punctul b). În acest caz, program se va scrie un singur număr reprezentând numărul de numere k-norocoase citite.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează cerintele de mai sus.

În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."

Restricţii şi precizări

1 ≤ N ≤ 1000 2 ≤ k ≤ 30 1 ≤ numerele citite de pe a treia linie a programul ≤ 2 000 000 000

Pentru rezolvarea corectă a primei cerinţe se acordă 40 de puncte, pentru rezolvarea corectă a celei de-a doua cerințe se acordă 60 de puncte.

Exemplul 1

Datele de intrare

1

9 3

165 12 33 30 5 18 105 15 4

Datele de ieșire

Datele sunt introduse corect.

5 165

Exemplul 2

Datele de intrare

2

5 3

165 31 165 105 44

Datele de ieșire

Datele sunt introduse corect.

3

Rezolvare

<syntaxhighlight lang="python" line>

1. 1694

import math

def is_lucky_number(n):

   square = n ** 2
   for i in range(1, math.isqrt(square) + 1):
       j = i + 1
       while True:
           sum = ((i + j) * (j - i + 1)) // 2
           if sum == square:
               return True
           elif sum > square:
               break
           j += 1
   return False

def is_k_lucky_number(n, k):

   primes = []
   for i in range(2, n + 1):
       while n % i == 0:
           primes.append(i)
           n //= i
       if n == 1:
           break
   return len(set(primes)) == k

def validate_input(c, n, k, numbers):

   # check restrictions for c
   if c not in [1, 2]:
       return False
   # check restrictions for n and k
   if not 1 <= n <= 1000 or not 2 <= k <= 30:
       return False
   # check restrictions for numbers
   for number in numbers:
       if not 1 <= number <= 2000000000:
           return False
   return True

if __name__ == '__main__':

   # read input values
   c = int(input())
   n, k = map(int, input().split())
   numbers = list(map(int, input().split()))

   # validate input values
   if not validate_input(c, n, k, numbers):
       print("Datele nu corespund restricțiilor impuse.")
   else:

       # process input values based on the command type
       if c == 1:

           lucky_numbers = [number for number in numbers if is_lucky_number(number)]
           if not lucky_numbers:

               print(0)
           else:
               print("Datele sunt introduse corect.")
               print(min(lucky_numbers), max(lucky_numbers))
       elif c == 2:
           k_lucky_numbers = [number for number in numbers if is_k_lucky_number(number, k)]

           print(len(k_lucky_numbers))

</syntaxhighlight>

Explicatie cod:

Acest cod implementează o soluție pentru o problemă ce necesită validarea și procesarea unor date de intrare.

Funcția is_lucky_number(n) primește un număr întreg n și verifică dacă n^2 este un număr norocos (un număr norocos este un număr care poate fi scris ca suma a două numere consecutive începând cu 1, de exemplu 30 este un număr norocos deoarece 30=1+2+3+4+5+6+7).

Funcția is_k_lucky_number(n, k) primește un număr întreg n și un număr întreg k, și verifică dacă n are exact k factori primi.

Funcția validate_input(c, n, k, numbers) primește 4 parametri și verifică dacă aceștia respectă restricțiile impuse de problema respectivă.

În funcția principală if __name__ == '__main__':, se citesc valorile de intrare și se validează prin apelarea funcției validate_input(). Dacă valorile nu respectă restricțiile, se afișează un mesaj corespunzător, altfel se procesează datele de intrare în funcție de tipul comenzii primite (c == 1 sau c == 2).

Dacă c == 1, se construiește o listă cu toate numerele norocoase din lista numbers, iar dacă lista este goală, se afișează 0, altfel se afișează cel mai mic și cel mai mare număr norocos găsit.

Dacă c == 2, se construiește o listă cu toate numerele din lista numbers care au exact k factori primi, iar apoi se afișează lungimea acestei liste.

În acest fel, codul verifică dacă datele de intrare sunt valide și le procesează corespunzător în funcție de comanda primită, în conformitate cu cerințele problemei.