# PBinfo #3945 – fazan_max – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Se dau n cuvinte distincte formate din litere mici. Afișați șirul format dintr-un număr maxim de cuvinte distincte dintre cele date, care respectă regula jocului Fazan. La jocul Fazan o succesiune de două cuvine a și b se consideră corectă dacă ultimele două litere din cuvântul a sunt identice cu primele două din b. De exemplu, cuvintele fazan și anterior sunt corecte în această ordine.

Date de intrare
Programul citește de la tastatură numărul n și apoi n cuvinte, separate prin spații sau scrise pe rânduri separate.

Date de ieșire
Programul va afișa pe ecran cuvintele care formează șirul cerut, separate prin câte un spațiu.
Dacă există mai multe șiruri formate dintr-un număr maxim de cuvinte, se va afișa cel mai mic lexicografic. 

Restricții și precizări

1 ≤ n ≤ 30
cele n cuvinte sunt formate din litere mici, au lungimea cel puțin 2 și cel mult 20 și sunt distincte.

Exemplu:
Intrare

7
dor ana nasture repede alina diana decis
Ieșire

alina nasture repede decis
Explicație

Există mai multe soluții de lungime maximă, dar cea afișată este minimă lexicografic. Celelalte soluții sunt:

ana nasture repede decis
diana nasture repede decis

## Cod sursă C++

```cpp
#include <iostream>
#include <cstring>
using namespace std;
char S[32][22];
int X[32],n,P[32],kmax,Y[32];
void afisare()
{
    for(int i=1;i<=kmax;i++)
        cout<<S[Y[i]]<<" ";
}
int ok(int k)
{
    if(k>1 && strncmp(S[X[k]],S[X[k-1]]+strlen(S[X[k-1]])-2,2)!=0)
        return 0;
    return 1;
}
void back(int k)
{
    for(int i=1;i<=n;i++)
        if(!P[i])
        {
            X[k]=i;
            P[i]=1;
            if(ok(k))
            {
                if(k>kmax)
                {
                    kmax=k;
                    for(int i=1;i<=k;i++)
                        Y[i]=X[i];
                }
                back(k+1);
            }
            P[i]=0;
        }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>S[i];
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            if(strcmp(S[i],S[j])>0)
                swap(S[i],S[j]);
    back(1);
    afisare();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3945)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3945/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3945/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)