Vizualizare sursă pentru „2217 - Map”

Domnul Map vă pune la dispoziție un șir '''a[1]''', '''a[2]''', '''…, a[n]''' de numere naturale.

==Cerința==

Pentru fiecare '''a[i] (i=1..n)''' trebuie să spuneți de câte ori apare acest element în secvența '''a[1], a[2], …, a[i].'''

==Date de intrare==

Fișierul de intrare '''mapin.txt''' conține pe prima linie numărul '''n'''. Pe linia a doua, separate prin câte un spațiu, sunt elementele șirului.

==Date de ieșire==

În fișierul de ieșire '''mapout.txt''' se vor afișa pe primul rând '''n''' numere naturale, al '''i'''-lea număr reprezentând numărul de apariții ale lui '''a[i]''' în secvența '''a[1], a[2], …, a[i].'''

==Restricții și precizări==

*'''1 ≤ n ≤ 200 000'''
*'''0 <= a[i] <= 1018'''

==Exemplul 1:==

'''mapin.txt'''

 7
 1 9876543210 1 3 3 9876543210 9876543210

'''mapout.txt'''

 Datele de intrare corespund restrictiilor impuse
 1 1 2 1 2 2 3

==Exemplul 2:==

'''mapin.txt'''

 map

'''mapout.txt'''

 Datele de intrare nu corespund restrictiilor impuse

==Explicație==

Primul element este '''1'''. Apare o singură dată până acum.
Al doilea element este '''9876543210'''. Și el apare pentru prima dată.
Al treilea element este '''1'''. Apare a doua oară.
Al patrulea element este '''3'''. Apare prima oară.
Al cincilea element este '''3'''. Apare a doua oară.
Al șaselea element este '''9876543210'''. Apare a doua oară.
Al șaptelea element este '''9876543210'''. Apare a treia oară.

==Rezolvare==

<syntaxhighlight lang="python" line="1" start="1">

from collections import defaultdict


def validare(nr_n, string, fisier_out):           # functia de validare a datelor de intrare
    if not (1 <= nr_n <= 200000):
        raise ValueError("n nu este in intervalul [1, 200000]")

    for numar in string:
        if not (0 <= numar <= 10**18):    # fiecare numar trebuie sa fie intre 0 si 10^18
            raise ValueError("Un numar din sir nu este in intervalul [0, 10^18]")

    fisier_out.write("Datele de intrare corespund restrictiilor impuse\n")


def rezolvare(string, fisier_out):                     # functia de rezolvare
    aparitii = defaultdict(int)
    for numar in string:
        aparitii[numar] += 1
        fisier_out.write(str(aparitii[numar]) + " ")


if __name__ == '__main__':
    file_in = open("mapin.txt", "r")         # declararea fisierelor
    file_out = open("mapout.txt", "w")       # fisierul out trebuie declarat cu optiunea "w" (write)

    try:
        n_str = file_in.readline().strip()  # citirea numarului ca sir de caractere
        try:
            n = int(n_str)  # incercam sa convertim sirul de caractere in numar intreg
        except ValueError:
            file_out.write("Datele de intrare nu corespund restrictiilor impuse\n")
            file_in.close()
            file_out.close()
            exit(0)  # iesim din program daca conversia esueaza

        sir = list(map(int, file_in.readline().split()))

        validare(n, sir, file_out)  # apelul functiei de validare
        rezolvare(sir, file_out)  # apelul functiei de rezolvare

    except ValueError as ve:
        file_out.write(str(ve))
    except IndexError:
        file_out.write("Datele de intrare nu corespund restrictiilor impuse")

    file_in.close()
    file_out.close()

</syntaxhighlight>