|
Titlul: Numar Scris de: alexandru din Februarie 20, 2009, 14:48:27 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 :-k ? Compilatorul folosit, este cel de la oli :thumbdown: , Broland 3.1 Titlul: Răspuns: Numar Scris de: Andrei Grigorean din Februarie 20, 2009, 16:53:49 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 ;) Titlul: Răspuns: Numar Scris de: alexandru din Februarie 20, 2009, 17:16:07 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? Titlul: Răspuns: Numar Scris de: Andrei Grigorean din Februarie 20, 2009, 17:31:36 Bun, pai foloseste-te de hint-ul 2. Poti afla ultima cifra a rezultatului? Dar penultima?
Titlul: Răspuns: Numar Scris de: alexandru din Februarie 20, 2009, 17:50:45 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. Titlul: Răspuns: Numar Scris de: Cezar Mocan din Februarie 20, 2009, 18:58:07 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 :)
Titlul: Răspuns: Numar Scris de: alexandru din Februarie 20, 2009, 19:15:46 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.
|