Pentru transmiterea unui mesaj format exclusiv din litere mici ale alfabetului englez, se utilizează un aparat electronic care are anumite limitări tehnice. Astfel, el poate transmite mesaje formate doar din litere vecine din alfabet sau formate din aceeași literă. De exemplu mesajul: defffedcbab poate fi transmis, iar mesajul accded nu poate fi transmis deoarece literele a și c nu sunt vecine în alfabetul englez.

Din acest motiv mesajul ce urmează să fie transmis trebuie codificat pentru a fi compatibil cu aparatul.

Pentru codificare, mesajul este prelucrat în etape până satisface limitările aparatului. O etapă de prelucrare presupune inserarea între fiecare două litere vecine ale mesajului a literei mijlocii. Litera mijlocie este acea litera situată la jumătatea secvenței din alfabet ce are capete literele vecine. Dacă nu există se ia în considerare litera mai mică.

Literele vecine	Litera mijlocie	Explicații
`dd`	`d`
`ae`	`c`	Secvența `abcde` are litera `c` la mijloc
`af`	`c`	Secvența `abcdef` are la mijloc literele `cd`, din care alegem `c`
`ha`	`d`	Secvența este tratată la fel ca și `ah` deci `abcdefgh`

Cerința

Determinați numărul de etape de prelucrare necesare pentru codificarea mesajului și lungimea finală a mesajului.

Date de intrare

Fișierul de intrare abba.in conține pe prima linie un șir s de litere mici ale alfabetului englez.

Date de ieșire

Fișierul de ieșire abba.out va conţine o singură linie cu două numere naturale separate printr-un spațiu, care reprezintă numărul de etape de prelucrare și lungimea finală a mesajului.

Restricții și precizări

2 ≤ lungime șir s ≤ 50000
Mesajul va suferi cel puțin o etapă de prelucrare.

Exemplu

abba.in

oli

abba.out

2 9

Explicație

În prima etapă între ol se introduce m și între li se introduce j. Mesajul devine omlji.

În etapa a doua se inserează literele n l k i și se obține onmllkjii care are 9 litere.

Nu se continuă mai departe prelucrarea mesajului, el poate fi transmis de aparatul electronic fiindcă oricare două litere alăturate în mesaj sunt fie identice fie vecine în alfabet.

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 Abba:

/**
Problema: abba
    codificare sir prin
    inserare litera mijlocie
*/
#include <fstream>
#include <cstdlib>
using namespace std;
char x,y,dif_max,a,b,z,etape;
int n=0;
long long p;
int main()
{
    ifstream f("abba.in");
    ofstream g("abba.out");
    f>>x>>y;
    n=2;
    dif_max=labs(x-y);
    a=x;
    b=y;
    x=y;
    while(f>>y)
    {
        n++;
        z=labs(x-y);
        if(dif_max<z)
        {
            dif_max=z;
            a=x;
            b=y;
        }
        x=y;
    }
    if(b<a)
        swap(a,b);
    while(b-a>1)
    {
        a=(a+b)/2; ///cout<<a<<endl;
        etape++;
    }
    p= (long long)(1<<etape) * (n-1) + 1; /// 2^k(n-1)+1
    g<<int(etape)<<<<p;
    return 0;
}

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 #1562 Abba

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1562 Abba 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 #1562 Abba