Numar

[•alexandru92]

Problema  2  –  numere   100 puncte


Gigel, pregătindu-se pentru olimpiada de informatică, a descoperit o problemă foarte interesantă. Se dau n numere naturale A1,A2,...,An, toate repetându-se de un număr de ori divizibil cu k, cu excepţia unuia.

Cerinţă
Ajutaţi-l pe Gigel să rezolve problema şi să găsească numărul respectiv.

Date de intrare
Fişierul numere.in conţine pe prima linie numerele n şi k despărţite printr-un spaţiu, iar pe următoarele n linii numerele A1,A2,...,An.

Date de ieşire
Fişierul numere.out va conţine pe prima linie un singur număr şi anume numărul ce nu se repetă de un număr de ori divizibil cu k.

Restricţii şi precizări
•   1 <= n <= 1.000.000 
•   2 <= k <= 1.000.000
•   0 <= Ai <= 1.000.000.000,  cu 1 <= i <= n
•   pentru 30% din teste, Ai <= 10.000
Problema  e destul de usoara, dar  ma dau gata  limitele. Cu vectorii clar nu pot lucra, cel putin nu alocati static. Ar fi buna o iimplementare cu liste simplu inlanuite  ?
Compilatorul folosit, este cel de la oli  , Broland 3.1

[•wefgef]

Si aceasta problema este "imprumutata". Ea a fost propusa pentru prima data de Daniel Dumitran (cred ca la Info-Oltenia, s-ar putea sa ma insel).

Hint1: Daca numerele ar fi cuprinse intre 0 si 9 ai sti sa rezolvi problema?
Hint2: Afla pe rand cifrele rezultatele

[•alexandru92]

Pai intre  0 si 9 as lua  un vector  cu semnificatia v[ i ]= nr de aparitii a elementului.
Apoi pur si simplu cand v[ i ]%k!=0 break; si afisez  i.
Cred  k  m-am prins putin dar  vreau sa incerc pe mai multe numere, ai cumva testele?

[•wefgef]

Bun, pai foloseste-te de hint-ul 2. Poti afla ultima cifra a rezultatului? Dar penultima?

[•alexandru92]

Cred ca am gasit o implementare.
Intr-o matrice de 9x9 retin elementele astfel:
v[ i ][j]= numarul de aparitii a cifrei i ,  care apare ca  unitate, zeci,sute...etc
Apoi parcurg matricea pe coloane si determin daca v[ i ][j]%k!=0  atunci  cat timp  v[ i ][j]%k!=0, intrun alt vector, sa zic nr, memorez i si scazi din    v[ i ][j].
Asa se rezolva?.....
Multumesc pt ajutor
Ce s-ar intampla daca modificam  putin enuntul, adica:
Sa nu mai avem k si cerinta sa fie: Sa se gaseasca un  numarul cel mai mare care se repeta de cel putin n/2+1 ori. Daca nu, se va afisa  "NU".  a.......am uitat  si n <= 100 000
(problem se numeste Alegeri)
Rezolvarea asta n-ar fi  buna.

[•CezarMocan]

Problema asta este clasica (problema majoritatii votului) si e destul de diferita fata de cea anterioara. Aici (http://infoarena.ro/blog/problema-majoritatii) sunt prezentate diverse metode pentru a o rezolva. Spor

[•alexandru92]

Eu  m-am gandit sa o fac  tot cu o matrice, dar de data asta de 19*19. Si asemanator cu sus,dar  nu mai impart nr in cifre.