Se consideră un şir de cifre zecimale (de la 0 la 9). În acest şir trebuie să inserăm virgule, separând astfel cifrele în scopul de a forma numere.

Cerința

Scrieţi un program care să insereze virgule în şirul de cifre astfel încât să se obţină o secvenţă de numere strict crescătoare, iar ultimul număr din secvenţă să fie minim.

Date de intrare

Fișierul de intrare virgule.in conține pe prima linie o secvenţă de cifre.

Date de ieșire

Fișierul de ieșire virgule.out va conține o singură linie pe care va fi scrisă secvenţa strict crescătoare de numere, obţinută prin inserarea virgulelor în şirul cifrelor, secvenţă în care ultimul număr este minim.

Restricții și precizări

0 < Lungimea secvenţei de cifre din fişierul de intrare < 95.
Numerele din secvenţa de numere obţinută pot începe cu cifra 0.
Dacă există mai multe soluţii în care ultimul număr din secvenţă este minim, se alege secvenţa în care primul număr este maxim. Dacă şi în acest caz există mai multe soluţii, se alege soluţia în care al doilea număr este maxim, ş.a.m.d.
Fişierul de intrare şi fişierul de ieşire nu vor conţine spaţii.
Pentru teste valorând 50% din punctajul acordat pe teste fişierul de intrare nu conţine cifra 0.

Exemplul 1

virgule.in

virgule.out

68,79

Exemplul 2

virgule.in

1000001010102

virgule.out

100,000101,0102

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Virgule:

#include <fstream>
#include <cstring>
#define LGMAX 100
using namespace std;

ifstream fin("virgule.in");
ofstream fout("virgule.out");
char s[LGMAX];
int sol[LGMAX], solmin[LGMAX];
int nrmin, lg;

void afisare();
void bkt(int k);
void copiaza(int k);
int Compar(int inc1, int sf1, int inc2, int sf2);

int main()
{int i;
 fin>>(s+1);
 lg=strlen(s+1);
 for (i=lg-1; i>=1; i--)
        {
          sol[1]=i;
          bkt(2);
        }
 afisare();
 return 0;
}

void bkt(int k)
{int rez, i;
 rez=Compar(sol[k-1]+1,lg, sol[k-2]+1,sol[k-1]);
 if (rez<=0) return ;
 rez=Compar(solmin[nrmin]+1, lg, sol[k-1]+1, lg);
 if (rez>0) copiaza(k);
     else
     if (rez==0)
         {
          i=1;
          while (i<k-1 && sol[i]==solmin[i]) i++;
          if (Compar(sol[i-1]+1, sol[i], solmin[i-1]+1, solmin[i])>0) copiaza(k);
         }
 //incerc sa mai pun o virgula dupa cifra de pe pozitia i
 for (i=lg-1; i>sol[k-1]; i--)
        {
          rez=Compar(sol[k-2]+1, sol[k-1], sol[k-1]+1,i);
          if (rez>=0) break;
          sol[k]=i;
          bkt(k+1);
        }
}

void afisare()
{int i, k;
 k=1;
 for (i=1; i<=lg; i++)
     {fout<<s[i];
      if (i==solmin[k]) {fout<<','; k++;}
     }
  fout<<'\n';
}

void copiaza(int k)
{ int i;
  nrmin=k-1;
  for (i=1; i<k; i++) solmin[i]=sol[i];
}

int Compar(int inc1, int sf1, int inc2, int sf2)
{int i, j;
 while (inc1<sf1 && s[inc1]=='0') inc1++;
 while (inc2<sf2 && s[inc2]=='0') inc2++;
 if (sf1-inc1+1>sf2-inc2+1) return  1;
 if (sf1-inc1+1<sf2-inc2+1) return -1;
 //au aceeasi lungime
 for (i=inc1, j=inc2; i<=sf1 && s[i]==s[j]; i++, j++);
 if (i>sf1) return 0;
 if (s[i]<s[j]) return -1;
 return 1;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1502 Virgule

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1502 Virgule de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1502 Virgule