Problema simulare BAC 2014

[manxten]

Salut! Cum pot sa rezolv problema urmatoare eficient in C++? Sau macar sa imi dati o idee. Am incercat cu 3 variabile, dar nu imi iese deloc

Se consider? un ?ir ai c?rui termeni sunt numere naturale nenule, de o singur? cifr?.

Numim num?r asociat al acestui ?ir un num?r natural format cu termenii ?irului, în ordinea

în care ace?tia apar în ?ir.

Exemplu: num?rul asociat ?irului 1, 2, 5, 3, 2 este 12532.

Fi?ierul text bac.txt con?ine un ?ir de cel pu?in trei ?i cel mult 80 de termeni, numere

naturale nenule, de o singur? cifr?, separate prin câte un spa?iu.

Se cere determinarea unui ?ir ob?inut prin eliminarea a doi termeni situa?i pe pozi?ii

consecutive în ?irul aflat în fi?ier, astfel încât num?rul asociat ?irului ob?inut s? fie maxim.

Termenii ?irului ob?inut se afi?eaz? pe ecran, separa?i prin câte un spa?iu.

Se utilizeaz? un algoritm eficient din punctul de vedere al memoriei utilizate ?i al timpului

de executare.

Exemplu: dac? fi?ierul bac.txt con?ine ?irul

9 8 5 7 6 2 3 4

atunci, pentru c? numerele asociate ?irurilor care se pot ob?ine sunt 576234, 976234,

986234, 985234, 985734, 985764, 985762, pe ecran se afi?eaz? ?irul:

9 8 6 2 3 4

[black_death_c4t]

Salut! Cum pot sa rezolv problema urmatoare eficient in C++? Sau macar sa imi dati o idee. Am incercat cu 3 variabile, dar nu imi iese deloc

Se consider? un ?ir ai c?rui termeni sunt numere naturale nenule, de o singur? cifr?.

Numim num?r asociat al acestui ?ir un num?r natural format cu termenii ?irului, în ordinea

în care ace?tia apar în ?ir.

Exemplu: num?rul asociat ?irului 1, 2, 5, 3, 2 este 12532.

Fi?ierul text bac.txt con?ine un ?ir de cel pu?in trei ?i cel mult 80 de termeni, numere

naturale nenule, de o singur? cifr?, separate prin câte un spa?iu.

Se cere determinarea unui ?ir ob?inut prin eliminarea a doi termeni situa?i pe pozi?ii

consecutive în ?irul aflat în fi?ier, astfel încât num?rul asociat ?irului ob?inut s? fie maxim.

Termenii ?irului ob?inut se afi?eaz? pe ecran, separa?i prin câte un spa?iu.

Se utilizeaz? un algoritm eficient din punctul de vedere al memoriei utilizate ?i al timpului

de executare.

Exemplu: dac? fi?ierul bac.txt con?ine ?irul

9 8 5 7 6 2 3 4

atunci, pentru c? numerele asociate ?irurilor care se pot ob?ine sunt 576234, 976234,

986234, 985234, 985734, 985764, 985762, pe ecran se afi?eaz? ?irul:

9 8 6 2 3 4

Pentru bac, eficienta la o problema de genul ar fi sa nu salvezi numele obtinute intr-un vector, ci sa folosesti 2 variabile, un max si o alta variabila pentru a itera posibilele numere, that's it, nu e cine stie ce solutia lui peste.

Nu irosesti memorie salvand toate valorile posibile, nici timp de executie parcurgand ulterior vectorul pentru a afisa maximul

Legat de rezolvare, iti poti face o functie la care sa trimiti ca parametru numarul ( intreg, cu toate cifrele ) si 2 pozitii care le elimini. in functie incepi sa compui numarul de la coada la cap

( 15356 = 6 * 1 + 5 * 10 + 3 * 100 .. ) sarind compunerea pentru pozitiile care trebuie eliminate. Functia iti va returna numarul la finalul executiei si va fi apelata din main() folosind o structura repetiva ( for () { functia_pacii ( NUMAR , Poz1 , Poz2 ); ceva conditie sa modifici poz1 si poz2 ; }) . Fiecare rezultat returnat de functia respectiva compari cu un maxim si aia e.

LE: Din fisier le citesti ca si stringuri salvandu-le in ceva variabila locala dupa care aplici o functie de conversie to int pe ele, gen atoi.

Edited June 21, 2014 by black_death_c4t

[Ganav]

E simplu: creezi intai numarul:

long long nr = 0;

char n;
char temp[80];

while ((n = fgetc(f)) != EOF) {
    if(!isspace(n))
         strcat(temp, n);

}

acum avem un string cu cifrele in ordinea in care apare in fisier. Il sortam descrescator(foloseste bubblesort) pentru a avea cifrele mari la inceput. Acum trebuie sa facem un minim dintre toate perechile consecutive.

int min = MAX_INT; // sau pune un nr. foarte mare gen 0xFFFFFFFF
int index = 0; // indexul primului nr.(pe al doilea il stim ca este consecutiv)

for(int i = 0; i < strlen(temp) - 1; i++) {
    if(temp[i] + temp[i+1] < min) {
      min = temp[i] + temp[i+1];
      index = i; // acum stim si unde sa gasim perechea
   }
}

Acum avem tot. Trebuie doar sa scapam de acea pereche:

strcpy(temp+index, temp+index+2);

Gata. Transformam numarul in long(int e prea mic);

nr = atol(temp);
printf("Basta %ld\n", nr);

Pentru eficienta ai putea folosi quicksort in loc de bubble sort insa este mai dificil de implementat.

Edited June 21, 2014 by Ganav

[manxten]

Am reusit sa o rezolv mult mai usor. Mersi oricum

[black_death_c4t]

Am reusit sa o rezolv mult mai usor. Mersi oricum

posteaza pt altii

[manxten]

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("bac.txt");
int x, y, z, ok=0;
int main()
{
    f>>x>>y;
    while(f>>z)

        if(x>z || ok==1) // gaseste x>z sau daca a intrat prin else odata nu trebuie sa mai intre in else 
         {
             cout<<x<<' ';
             x=y;
             y=z;
         }
        else if(ok==0)
          {
              x=z;  //sare peste doua numere: x si y
              f>>y;
              ok=1;
          }
    cout<<x<<' '<<y; // afiseaza valorile ramse in x si y atunci cand se termina sirul
}