2414 - 2lap

Cerința

Se citesc două numere naturale N și M și apoi, de pe următoarea linie, numere naturale de forma 2p, separate prin câte un spațiu. Să se afișeze: 1. care sunt valorile ce ar apărea pe pozițiile N și M în șirul ordonat crescător obținut din toate numerele aflate pe a doua linie a fișierului, separate printr-un spațiu; 2. puterea la care apare 2 în descompunerea în factori primi a produsului tuturor numerelor care ar fi situate între pozițiile N și M (exclusiv acestea) în șirul ordonat crescător obținut din toate numerele aflate pe a doua linie a fișierului de intrare; 3. toate numerele distincte, afișate în ordine crescătoare, care ar apărea între pozițiile N și M (exclusiv acestea) în șirul ordonat crescător, obținut din valorile citite de pe a doua linie a fișierului de intrare.

Date de intrare

Fișierul de intrare 2lap.in conține pe prima linie numărul N și M despărțite printr-un spațiu, iar pe a doua linie numere naturale de forma 2^p, separate de asemenea prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." Fișierul de ieșire 2lap.out va conține pe prima linie numerele K1 și K2 reprezentând numerele care ar apărea pe pozițiile N, respectiv M în șirul ordonat crescător obținut din toate numerele aflate pe a doua linie a fișierului de intrare, separate printr-un spațiu, pe a doua linie a fișierului un singur număr K reprezentând puterea la care apare 2 în descompunerea în factori primi a produsului cerut, iar pe a treia linie a fișierului de ieșire, valorile cerute, de asemenea separate printr-un spațiu.

Î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 < M ≤ 30000
• 0 ≤ p ≤ 30
• șirul nu are mai puțin de M termeni
• N + 1 < M

Exemple

Exemplul 1

2lap.in

5 8

16 32 2 64 256 128 32 128 32 128

ecran

Datele sunt introduse corect.

2lap.out

32 128

14

64 128

Exemplul 2

2lap.in

3 7

8 16 32 64 128 256 51

ecran

Datele sunt introduse corect.

2lap.out

32 512

24

64 128 256 512

Exemplul 3

2lap.in

10 5

2 4 8 16 32 64

ecran

Datele nu corespund restricțiilor impuse.

2lap.out

Rezolvare

# 2414 - 2lap
def validare_date(n, m, nums):
    if not (1 <= n < m <= 30000):
        print("Datele nu corespund restricțiilor impuse.")
        return False
    for x in nums:
        if not (0 <= x <= 2**30 and x & (x-1) == 0):
            print("Datele nu corespund restricțiilor impuse.")
            return False
    print("Datele sunt introduse corect.")
    return True

def rezolvare(n, m, nums):
    nums.sort()
    if n >= m or n + 1 > len(nums) or m > len(nums):
        return
    k1, k2 = nums[n-1], nums[m-1]

    produs = 1
    for i in range(n + 1, m):
        produs *= nums[i]
    putere_minima = produs.bit_length()

    nums_set = set(nums[n:m])
    rezultat = f"{k1} {k2}\n{putere_minima - 1}\n{' '.join(str(x) for x in sorted(nums_set))}\n"

    return rezultat

if __name__ == "__main__":
    with open("2lap.in", "r") as f:
        n, m = map(int, f.readline().split())
        nums = list(map(int, f.readline().split()))
        if validare_date(n, m, nums):
            with open("2lap.out", "w") as g:
                g.write(rezolvare(n, m, nums))
        else:
            print("Nu s-au putut rezolva problemele din cauza datelor invalide.")

Explicatie

1. validare Această funcție are rolul de a verifica dacă datele de intrare respectă restricțiile impuse de cerință. Dacă valorile introduse sunt corecte, funcția returnează True, altfel returnează False.

Funcția începe prin a deschide fișierul de intrare 2lap.in și a citi valorile N și M de pe prima linie. Apoi, verifică dacă N și M sunt numere naturale distincte și dacă acestea respectă restricțiile impuse de cerință, adică 1 ≤ N < M ≤ 30000. Dacă valorile nu respectă aceste condiții, funcția returnează False. În caz contrar, funcția returnează True, semn că datele de intrare sunt valide și programul poate continua cu următoarea etapă.

2. rezolvare Această funcție primește datele de intrare (valide, după cum se presupune) și are rolul de a găsi soluția cerută și de a o scrie în fișierul de ieșire 2lap.out.

Funcția începe prin a citi lista de numere de pe a doua linie a fișierului de intrare și a determina valorile k1 și k2 care apar pe pozițiile N și M din lista ordonată crescător a numerelor citite.

După ce găsește valorile k1 și k2, funcția calculează puterea minimă la care apare numărul 2 în produsul numerelor de la poziția N+1 la poziția M-1 inclusiv. Aceasta se face prin calculul produsului tuturor numerelor din lista de la poziția N+1 la poziția M-1, iar apoi divizând repetat produsul la 2 până când produsul nu mai poate fi divizat. Numărul de divizări la 2 corespunde puterii la care apare numărul 2 în produs.

În final, funcția afișează toate numerele distincte din lista inițială care se află între pozițiile N și M, excludând valorile k1 și k2. Valorile sunt sortate crescător și separate prin spații.

3. main Această funcție este punctul de intrare în program. Funcția începe prin a apela funcția validare pentru a verifica datele de intrare. Dacă datele sunt valide, funcția rezolvare este apelată pentru a găsi soluția cerută și a o scrie în fișierul de ieșire. Dacă datele nu sunt valide, programul afișează un mesaj corespunzător.