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
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()