1773 - Happy

Sursa: [1]

Cerinţa

Lui Ionci ii place foarte mult matematica si informatica, asa ca s-a gandit sa creeze o operatie. Aceasta a numit-o "Happy", notata cu semnul ☺. Operatia se aplica doar numerelor naturale si dau ca rezultat tot un numar natural, conform exemplelor de mai jos:

2010 ☺ 2005 = 5 78 ☺ 54 = 6 999 ☺ 543 = 3 4 ☺ 9 = 1 5 ☺ 6 = 1 32 ☺ 24 = 8 10 ☺ 2 = 2

Profesorul de matematica, Vasy, i-a promis nota 10 pe invenție dacă pentru mai multe perechi de numere naturale veți determina cel mai mic număr rezultat cu număr par de divizori al operației Happy aplicată perechilor date și cel mai mare număr rezultat al operației Happy cu număr impar de divizori.

Date de intrare

Programul citește un număr natural N și N perechi de numere naturale a b.

Date de ieșire

Programul va afișa cel mai mic și cel mai mare rezultat obținut prin operația de mai sus, cu număr par, respectiv impar de divizori, separate printr-un spațiu.

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează cel mai mic număr rezultat cu număr par de divizori al operației Happy aplicată perechilor date și cel mai mare număr rezultat al operației Happy cu număr impar de divizori.

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

Restricţii şi precizări

1 ≤ N ≤ 20 cele 2 * N numere citite vor fi nenule și mai mici decât 1.000.000.

Exemplul 1

Datele de intrare

2

87 87

1 1

Datele de ieșire

Datele sunt introduse corect.

87 1

Rezolvare

#1773
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:
        print("Datele sunt introduse corect.")
        # 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(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))

Explicatie cod:

Acest cod începe prin a importa biblioteca math, care va fi utilizată în mai multe funcții din program.

Funcția validate_input primește două argumente: N și numbers. Dacă N nu se află între 1 și 20 sau lungimea listei numbers nu este de două ori N, funcția returnează False. De asemenea, dacă orice număr din listă nu se află între 0 și 1000000, funcția va returna False. În caz contrar, funcția va returna True.

Următoarea secțiune verifică dacă programul este rulat ca un script (adică nu este importat în alt script). Dacă este, programul va citi două valori de la tastatură: N și numbers. N reprezintă numărul de perechi de numere pe care trebuie să le lucreze programul, iar numbers este lista de numere în sine.

Dacă input-ul nu este valid, se va afișa mesajul "Input values do not meet the requirements." În caz contrar, se va continua cu operațiile principale.

Următoarea funcție, numar_divizori, primește un număr n și returnează numărul de divizori ai acelui număr. Funcția utilizează un set pentru a ține evidența divizorilor și iterază prin numerele între 1 și radicalul pătrat din numărul n (deoarece divizorii între radicalul pătrat și numărul n pot fi obținuți prin împărțirea la divizorii din intervalul 1-radicalul pătrat și, de asemenea, divizorii între 1 și radicalul pătrat sunt perechi, deci doar unul dintre ei trebuie adăugat în set). Dacă n este divizibil cu i, atunci i și n/i sunt adăugați la set. Funcția returnează numărul de elemente din set, care reprezintă numărul de divizori.

Următoarea funcție, happy, primește două numere, a și b, și aplică operația "Happy" pe ele. Operația "Happy" este definită astfel: dacă a > b, a este înlocuit cu a - b, în caz contrar b este înlocuit cu b - a. Aceasta se repetă până când a = b, moment în care funcția returnează a.

Programul continuă prin a crea o listă de perechi de numere (numită perechi) din lista numbers.

Ulterior, sunt inițializate două variabile, min_par și max_impar, cu valorile inf și -inf, respectiv. Acestea vor fi utilizate pentru a găsi cel mai mic număr cu număr par de divizori și cel mai mare număr cu număr impar de divizori.