# PBinfo #3942 – fazan – Rezolvare C++

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

## Enunț

Cerința
Se dau n cuvinte distincte formate din litere mici și un număr m. Afișați în ordine lexicografică toate șirurile de câte m 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ă numerele n și m, iar apoi n cuvinte, separate prin spații sau scrise pe rânduri separate.

Date de ieșire
Programul va afișa pe ecran pe linii separate în ordine lexicografică toate șirurile de câte m cuvinte dintre cele date, care respectă regula jocului Fazan. Cuvintele de pe același rând se vor separa prin câte un spațiu.
Dacă nu se pot alege m cuvinte care să respecte condiția, atunci se va afișa IMPOSIBIL.

Restricții și precizări

1 ≤ m < 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

11 3
cosmin nasture repede cosmina alina interactiv ascutit anual incrementare ananas banana
Ieșire

alina nasture repede 
anual alina nasture 
banana nasture repede 
cosmin incrementare repede 
cosmina nasture repede

## Cod sursă C++

```cpp
#include <iostream>
using namespace std;
string S[32];
int X[32],n,m,P[32],gasit;
void afisare()
{
    for(int i=1;i<=m;i++)
        cout<<S[X[i]]<<" ";
    cout<<endl;
    gasit=1;
}
int ok(int k)
{
    if(k>1 && S[X[k]].substr(0,2)!=S[X[k-1]].substr(S[X[k-1]].length()-2))
        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==m) afisare();
                else back(k+1);
            P[i]=0;
        }
}
int main()
{
    cin>>n>>m;
    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(S[i]>S[j])
                swap(S[i],S[j]);
    back(1);
    if(!gasit) cout<<"IMPOSIBIL";
    return 0;
}
```

## Resurse

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