Se consideră un şir de cuvinte separate două câte două printr-un spaţiu. Fiecare cuvânt este caracterizat prin numărul de ordine care reprezintă poziţia lui în şirul de cuvinte (primul cuvânt are numărul de ordine 1). Unui cuvânt i se pot aplica în mod repetat următoarele transformări: primul caracter al cuvântului (cel mai din stânga) se şterge de acolo şi se adaugă după ultimul caracter din cuvânt. Astfel, dintr-un cuvânt s cu k caractere se pot obţine alte k-1 cuvinte pe care le numim cuvinte obţinute din transformarea cuvântului s. De exemplu, dintr-un cuvânt format din 4 caractere c1c2c3c4, cuvintele obţinute prin transformarea lui sunt: c2c3c4c1, c3c4c1c2, c4c1c2c3.

Se caută în şirul de cuvinte prima pereche de cuvinte vecine (a,b), în care al doilea cuvânt din pereche (cuvântul b) este identic cu un cuvânt obţinut din transformarea lui a. Dacă există o astfel de pereche, se şterge cuvântul b din şir. Prin ştergerea cuvântului b din şir, acesta va avea mai puţin cu un cuvânt! Se repetă operaţia de căutare de mai sus până când în şirul rămas nu mai există o pereche (a,b) de cuvinte vecine, astfel încât b să fie obţinut prin transformarea lui a.

Se ştie că pe parcursul modificărilor, cuvintele nu-şi schimbă numerele de ordine pe care le-au avut iniţial.

Cerinţă:

Scrieţi un program care să citească şirul de cuvinte şi să afişeze:

a) numărul de ordine al primului cuvânt şters sau valoarea 0 în cazul în care nu se şterge niciun cuvânt
b) numerele de ordine ale cuvintelor rămase după finalizarea operaţiilor de modificare.

Date de intrare

Fișierul de intrare cuvinte4.in conține o singură linie pe care se află şirul de cuvinte separate două câte două printr-un spaţiu.

Date de ieșire

Fișierul de ieșire cuvinte4.out va conține:

pe prima linie numărul de ordine al primului cuvânt şters sau valoarea 0 în cazul în care nu se şterge niciun cuvânt
pe a doua linie numerele de ordine ale cuvintelor rămase în final în şirul de cuvinte, despărţite două câte două printr-un spaţiu.

Restricții și precizări

După ultimul cuvânt din şirul iniţial există caracterul !
Fiecare cuvânt are maxim 10 caractere, iar în şirul iniţial nu există mai mult de 25 cuvinte.
Şirul de cuvinte iniţial este format din cel puţin un cuvânt. O pereche de cuvinte vecine (a,b), din şirul de cuvinte este caracterizată prin faptul că, după cuvântul a se afla imediat cuvântul b.

Exemplu

cuvinte4.in

alfa faal alfa fala lafa afal calfa calfa!

cuvinte4.out

2
1 3 4 7 8

Explicație

Cuvintele obţinute prin transformarea cuvântului alfa sunt: : lfaa, faal, aalf. Prima pereche de cuvinte vecine care îndeplinesc cerinţele sunt cuvintele cu numerele de ordine 1 şi 2. Va fi şters cuvântul cu numărul de ordine 2. Şirul rezultat este format din următoarele 7 cuvinte: alfa alfa fala lafa afal calfa calfa. Prima pereche care îndeplineşte cerinţele din noul şir este perechea formată din cuvintele fala şi lafa, având numerele de ordine 4 şi 5, pentru că lista de cuvinte obţinute prin transformarea cuvântului fala sunt: alaf, lafa, afal. Se va şterge cuvântul cu numărul de ordine 5. Şirul rezultat după ştergere este: alfa alfa fala afal calfa calfa. Prima pereche care îndeplineşte cerinţele problemei în noul şir este fala şi afal. Se şterge afal cu numărul de ordine 6. Şirul rezultat după ştergere este: alfa alfa fala calfa calfa. În acest şir nu se mai găseşte nicio pereche care să îndeplinească cerinţele. Au rămas deci cuvintele: alfa, alfa, fala, calfa, calfa care au numerele de ordine 1, 3, 4, 7, 8.

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

#include<fstream>
#include<cstring>
using namespace std;

char x[25][255],y[25][255];
int poz[25];

void transforma(char s[255])
{
    unsigned int i;
    for(i=0;i<strlen(s);i++)
    { 
        char t[255];
        strcpy(t, s + 1);
        strncat(t,s,1);
        strcpy(s , t);
        strcpy(y[i],s);
    }
}   

int verifica(unsigned int j, unsigned int n)
{
    unsigned int i;
    for(i=0;i<n;i++)
        if (strcmp(x[j],y[i])==0) 
            return 1;
    return 0;
}




int  main()
{
    char s[255] , *p;
    unsigned int n,i=0,t,j,prima=0;
    ifstream f("cuvinte4.in");
    ofstream g("cuvinte4.out");
    f.get(s,255);
    p=strtok(s," !");
    while(p)
    {   
        strcpy(x[i++],p);
        poz[i-1]=i; 
        p=strtok(NULL," !");
    }
    n=i;
    i=0;
    j=1;
    while(i<n-1)
    {
        transforma(x[i]);
        if (verifica(j,strlen(x[i])-1)) 
        {
            for(t=j;t<n-1;t++)
            {
                strcpy(x[t],x[t+1]);
                poz[t]=poz[t+1];
            }
            if (prima==0) 
                prima=j+1;
            n--;
        }
        else 
        {
            i++;j=i+1;
        }
    }
    g<<prima<<"
";
    for(j=0;j<n;j++)
        g<<poz[j]<<" "; 
            
    f.close();
    g.close();
    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 #1087 Cuvinte4

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