Fişierul intrare/ieşire:colectie1.in, colectie1.outSursăOlimpiada pe scoala 2016 clasa a 10-a
AutorEduard ConstantinescuAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test5 secLimită de memorie6144 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Colectie 1 (clasa a 10-a)

Notă: această problemă a fost modificată pentru a reflecta ideea ei originală: aceea de a folosi memoria în mod eficient. Modificările sunt:

  • Memoria a fost micşorată de la 16MB la 6MB
  • Anumite teste conţin acum numere în toată plaja 1..9 milioane
  • Timpul a fost mărit la 5s pentru acele teste

 
 
Dudu este un colecţionar înrăit de vederi. În decursul anilor, a reuşit să colecţioneze un număr n de vederi. Pentru a-i fi mai uşor să le identifice, el a atribuit fiecărei vederi câte un număr (de la 1 la n).

Într-o zi, Dudu a constatat faptul că prin colecţia sa se află vederi care se repetă (sunt marcate cu acelaşi număr). Fiind, un colecţionar care se respectă, el doreşte să păstreze doar acele vederi care sunt unice în colecţia sa (prin „unic” înţelegem o vedere cu proprietatea că nicio altă vedere nu are asociat acelaşi număr).

„Ajută-mă, te rog!”, spune Dudu. El vă cere să aflaţi care este numărul de vederi unice din colecţia sa.

Date de intrare

Fişierul de intrare colectie1.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

În fişierul de ieşire colectie1.out se va afişa un singur număr, k, reprezentând numărul de vederi care sunt unice în colecţia lui Dudu.

Restricţii

  • 1 ≤ n ≤ 9 000 000
  • numerele de pe a doua linie a fişierului de intrare vor fi mai mici decât 9.000.000
  • pentru 60% din teste se garanetează că n ≤ 1.000.000
  • Dudu vă mulţumeşte din suflet pentru ajutorul oferit!

Exemplu

colectie1.incolectie1.out
10
4 3 8 9 3 8 4 2 1 1
2

Explicaţie

În colecţia lui Dudu se află vederi marcate cu numerele 1, 2, 3, 4, 8 şi 9. Dintre aceste vederi, cele marcate cu 2 şi 9 sunt unice.

Trebuie sa te autentifici pentru a trimite solutii. Click aici