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>