2032 - Mmult

Cerința

Alexandru, mare informatician, a decis să își impresioneze prietenii cu următoarea problemă: Dându-se un vector cu N numere naturale nenule, se întreabă care este numărul minim de mulțimi cu numere consecutive de forma {1...K} în care acesta poate fi împărțit. Spre exemplu vectorul A = {1, 3, 2, 2, 1, 4} poate fi împărțit în număr minim de partiții astfel {1, 2, 3, 4}, {1, 2}. Cum această problemă a fost prea dificilă pentru prietenii săi, Alexandru te roagă pe tine să o rezolvi.

Date de intrare

Fișierul de intrare mmult.in conține pe prima linie numărul N, iar pe a doua linie N numere naturale separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse Fișierul de ieșire mmult.out va conține pe prima linie numărul S, reprezentând răspunsul problemei date de Alex.

Î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 ≤ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000
• dacă problema nu are soluție, se va afișa -1

Exemple

Exemplul 1

mmult.in

6

1 3 2 2 1 4

ecran

Datele sunt introduse corect.

mmult.out

2

Exemplul 2

mmult.in

5

2 3 1 1 2

ecran

Datele sunt introduse corect.

mmult.out

2

Exemplul 3

mmult.in

0

ecran

Datele nu corespund restricțiilor impuse.

mmult.out

Rezolvare

# 2032 - Mmult
import sys


def validate_input(n, nums):
    """
    Validates input data for the problem
    """
    if n < 1 or n > 100000:
        return False

    for num in nums:
        if num >= 1000000:
            return False

    return True


def solve(n, nums):
    """
    Solves the problem and returns the answer as an integer
    """
    f = [0] * 100001
    m = 0

    for x in nums:
        m = max(m, x)
        f[x] += 1

    for i in range(2, m + 1):
        if f[i] > f[i - 1]:
            return -1

    return f[1]


if __name__ == '__main__':
    # Read input
    with open('mmult.in', 'r') as fin:
        n = int(fin.readline())
        nums = list(map(int, fin.readline().split()))

    # Validate input
    if not validate_input(n, nums):
        print("Datele nu corespund restricțiilor impuse.")
        sys.exit(0)

    # Solve problem
    ans = solve(n, nums)

    # Write output
    with open('mmult.out', 'w') as fout:
        fout.write(str(ans))

    # Print success message
    print(
        "Datele sunt introduse corect.")

Explicatie

Funcția validate_input(n, nums): Această funcție primește ca argumente un număr întreg n și o listă de numere întregi nums. Funcția verifică dacă acestea respectă restricțiile impuse de problemă și returnează True în caz afirmativ sau False în caz contrar. Mai precis, funcția verifică următoarele condiții:

n trebuie să fie între 1 și 100000, inclusiv toate numerele din lista nums trebuie să fie mai mici decât 1000000. Dacă datele introduse respectă aceste restricții, funcția returnează True, altfel returnează False.

Funcția solve(n, nums): Această funcție primește ca argumente un număr întreg n și o listă de numere întregi nums. Funcția rezolvă problema descrisă în enunțul problemei și returnează răspunsul ca un număr întreg. Mai precis, funcția efectuează următoarele operații:

inițializează un vector f cu 100001 elemente cu valoarea 0 găsește numărul maxim m din lista nums pentru fiecare număr x din lista nums, incrementează valoarea elementului f[x] parcurge elementele vectorului f de la 2 la m și verifică dacă f[i] este mai mare decât f[i-1]. Dacă da, înseamnă că problema nu are soluție și funcția returnează -1. dacă toate elementele vectorului f respectă această proprietate, funcția returnează valoarea f[1]. Funcția main(): Această funcție este funcția principală a programului și este responsabilă pentru citirea datelor de intrare din fișierul "mmult.in", validarea lor utilizând funcția validate_input, rezolvarea problemei utilizând funcția solve, scrierea răspunsului în fișierul "mmult.out" și afișarea unui mesaj corespunzător pe ecran. Mai precis, funcția efectuează următoarele operații:

deschide fișierul "mmult.in" în modul de citire și citește valorile pentru n și nums utilizând metoda readline și funcția map validează datele introduse utilizând funcția validate_input. Dacă acestea nu respectă restricțiile, afișează un mesaj corespunzător pe ecran și oprește programul utilizând funcția exit. rezolvă problema utilizând funcția solve și stochează rezultatul în variabila ans deschide fișierul "mmult.out