2217 - Map: Diferență între versiuni
(Pagină nouă: 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 map.in 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 map.out se vor afișa pe primul rând n numere naturale, al i-lea n...) |
Fără descriere a modificării |
||
Linia 1: | Linia 1: | ||
Domnul Map vă pune la dispoziție un șir a[1], a[2], …, a[n] de numere naturale. | Domnul Map vă pune la dispoziție un șir '''a[1]''', '''a[2]''', '''…, a[n]''' de numere naturale. | ||
Cerința | ==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 | ==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== | |||
1 1 2 1 2 2 3 | Î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].''' | ||
Explicație | |||
Primul element este 1. Apare o singură dată până acum. | ==Restricții și precizări== | ||
Al doilea element este 9876543210. Și el apare pentru prima dată. | |||
Al treilea element este 1. Apare a doua oară. | *'''1 ≤ n ≤ 200 000''' | ||
Al patrulea element este 3. Apare prima oară. | *'''0 <= a[i] <= 1018''' | ||
Al cincilea element este 3. Apare a doua oară. | |||
Al șaselea element este 9876543210. Apare a doua oară. | ==Exemplul 1:== | ||
Al șaptelea element este 9876543210. Apare a treia oară. | |||
'''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 | from collections import defaultdict | ||
Linia 77: | Linia 101: | ||
file_in.close() | file_in.close() | ||
file_out.close() | file_out.close() | ||
</syntaxhighlight> |
Versiunea curentă din 3 ianuarie 2024 20:31
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()