Rezolvare completă PbInfo #1620 Interesant

Se consideră o mulțime S care conține N șiruri de caractere formate din litere mici ale alfabetului englezesc.

Un șir de caractere se numește interesant în raport cu celelalte șiruri ale mulțimii, dacă nu există un alt șir în mulțime care să-l conțină ca subșir. De exemplu, dacă mulțimea S conține șirurile abc, bde și abcdef, atunci singurul șir interesant este abcdef deoarece abc și bde nu îl conțin ca subșir. Mai mult, abc și bde sunt subșiruri în abcdef, deci nu sunt interesante.

Cerința

Fiind dată o mulțime S formată din N șiruri de caractere se cere:

  1. Să se determine cel mai lung șir. Dacă sunt mai multe șiruri având aceeași lungime maximă, se cere cel mai mic din punct de vedere lexicografic.
  2. Să se determine toate șirurile interesante din mulțimea S.

Date de intrare

Fișierul de intrare interesant.in conține pe prima linie două numere naturale p și N, despărțite prin spațiu. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2. Pe următoarele N linii, se găsesc șirurile de caractere, câte unul pe linie.

Date de ieșire

Dacă valoarea lui p este 1, se va rezolva numai cerința 1.
În acest caz, în fișierul de ieșire interesant.out se va scrie cel mai lung șir dintre cele citite. Dacă există mai multe șiruri de aceeași lungime, se va scrie cel mai mic din punct de vedere lexicografic.
Dacă valoarea lui p este 2, se va rezolva numai cerința 2.
În acest caz, fișierul de ieșire interesant.out va conține pe prima linie o valoare K ce reprezintă numărul de șiruri interesante, iar pe următoarele K linii, șirurile interesante în ordinea în care apar în fișierul de intrare.

Restricții și precizări

  • 2 ≤ N ≤ 200
  • Lungimea unui șir va fi cuprinsă între 1 și 5000
  • Un subșir al șirului de caractere C0C1C2 …Ck se definește ca fiind o succesiune de caractere Ci1Ci2Ci3…Cik, unde 0 ≤ i1 < i2 < i3 < … < ik ≤ k.
  • Fișierul de intrare NU conține șiruri identice.
  • Pentru rezolvarea corectă a primei cerințe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.

Exemplul 1

interesant.in

1 5
abcacaaz
ad
abcacaad
acd
zyt

interesant.out

abcacaad

Explicație

p=1
Fișierul de intrare conține 5 șiruri.
abcacaad este șirul de lungime maximă. Șirul abcacaaz are aceeași lungime, dar este mai mare din punct de vedere lexicografic.

  • Atenție! Pentru acest test se rezolvă doar cerința 1.*

Exemplul 2

interesant.in

2 5
abcacaad
ad
zayyt
acd
zyt

interesant.out

2
abcacaad
zayyt

Explicație

p=2
Fișierul de intrare conține 5 șiruri.
ad, acd sunt subșiruri al lui abcacaad, iar zyt este subșir al lui zayyt

  • Atenție! Pentru acest test se rezolvă doar cerința 2.*

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

// prof. Nicu Vlad
#include <algorithm>
#include <fstream>
#include <cstring>
#define N 205
#define M 10010
using namespace std;
ifstream cin("interesant.in");
ofstream cout("interesant.out");

char A[N][M], AX[M],AY[M];
bool viz[N];

bool verif(char A[], char B[])
{
    int x=strlen(A);
    int y=strlen(B);
    int i=0,j=0;
    bool ok=false;
    while(i<x&&j<y)
    {
        if(A[i]!=B[j]);
        else j++;
        i++;
        if(i==x && j<y) return false;
    }
    if(j==y) return true;
    return false;
}

int main()
{
    int cer=0,n;
    cin>>cer>>n;
    if(cer==1)
    {
        int   i=0,maxi=0;
       for(i=0; i<n; i++)
        {
            cin>>AX;
            int x=strlen(AX);
            if(x>maxi)
            {
                maxi=x;
                strcpy(AY,AX);
            }
            else if(x==maxi)
            {
                if(strcmp(AY,AX)>0) strcpy(AY,AX);
            }

        }
        cout<<AY;
    }
    else
    {

        for(int i=0; i<n; i++)
        {
            cin>>A[i];
            int l=strlen(A[i]);
            for(int j=0;j<i;j++)
            {
                if(!viz[j])
                {
                    int k=strlen(A[j]);
                    if(l>=k)
                    {
                        if(verif(A[i],A[j])) viz[j]=1;
                    }
                    else
                    {
                        if(verif(A[j], A[i])) viz[i]=1;
                    }
                }
            }
        }
        int nr=n;
        for(int j=0; j<n; j++)
            if(viz[j]) nr--;
        cout<<nr<<"\n";
        for(int j=0; j<n; j++)
            if(!viz[j]) cout<<A[j]<<"\n";
    }
    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 #1620 Interesant

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