La un dineu participă reprezentanţii mai multor state. Fiecare reprezentant cunoaşte un număr de limbi străine. Doi reprezentanţi vor putea discuta direct dacă există cel puţin o limbă pe care o înţeleg amândoi. Organizatorii dineului doresc să existe cel puţin o masă la care să nu fie nevoie de translator, astfel oricare două persoane care stau la această masă să se înţeleagă direct.
Cerința
Cunoscând N – numărul de reprezentanţi, identificăm fiecare reprezentant cu un număr natural cuprins între 1 şi N, L – numărul limbilor străine care se vorbesc la dineu (acestea sunt codificate prin numerele naturale de la 1 la L), numărul de limbi vorbite de fiecare reprezentant şi codurile acestora să se determine numărul maxim de persoane care pot sta la o masa fără translator.
Date de intrare
Fişierul de intrare dineu.in conţine, pe prima linie, numerele naturale N şi L, separate printr-un spaţiu, cu semnificaţia de mai sus. Pe fiecare dintre următoarele N linii se află informaţii despre câte un reprezentant, în ordinea numerelor de identificare a acestora. Astfel, pe linia corespunzătoare reprezentantului i (1≤i≤N), se află un număr natural nri- numărul limbilor străine vorbite de acesta, urmat de nri numere naturale distincte l1 l2 ... lnri, reprezentând codurile acestora. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.
Date de ieșire
Fişierul de ieşire dineu.out va conţine două linii. Pe prima linie se află numărul maxim de reprezentanţi care stau la aceeaşi masă. Pe a doua linie se află numerele de identificare ale acestora. Numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.
Restricții și precizări
• 1 <= N <= 20
• 1 <= L <= 10
• 1 <= nri, l1, l2, ..., lnri <= 10
• Dacă există mai multe soluţii se va afişa cea mai mică din punct de vedere lexicografic
Exemplu
dineu.in
5 5 3 1 3 5 2 3 4 3 1 2 4 2 4 5 2 2 3
dineu.out
4 1 2 3 4
Explicație
1 cu 2 vorbesc în limba 3
1 cu 4 vorbesc în limba 5
1 cu 3 vorbesc în limba 1
2 cu 4 vorbesc în limba 4
2 cu 3 vorbesc în limba 4
3 cu 4 vorbesc în limba 4
există şi alte soluţii, de exemplu soluţia 1 2 3 5, dar este mai mare din punct de vedere lexicografic
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 Dineu:
//Prof. Lucia Miron
#include <fstream>
using namespace std;
ifstream fin("dineu.in");
ofstream fout("dineu.out");
int n,l, a[30][30],b[30][15],x[30],ok;
void citire()
{
int i, j,x;
fin>>n>>l;
for(i=1;i<=n;i++)
{
fin>>b[i][0];
for(j=1;j<=b[i][0];j++)
{fin>>x;b[i][x]=1;}
}
}
void matrice_ad()
{
int i,j,ex,k;
for(i=1;i<=n-1;i++)
{
for(j=i+1;j<=n;j++)
{
ex=0;
for(k=1;k<=l;k++)
if(b[i][k]&&b[j][k]){ex=1;break;}
if(ex)
a[i][j]=a[j][i]=1;
}
}
}
void afisare(int m)
{
int i;
fout<<m<<'\n';
for(i=1;i<=m;i++)
fout<<x[i]<<' ';
fout<<'\n';
fout.close();
}
int complet(int m)
{
int i,j;
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
if(a[x[i]][x[j]]==0&&i!=j)return 0;
return 1;
}
void gen(int k, int m)
{
int i;
if(!ok)
{if(k>m)
{ if(complet(m))
{ok=1;afisare(m);}
}
else for(i=x[k-1]+1;i<=n-m+k;i++)
{
x[k]=i;
gen(k+1,m);
}
}
}
void rezolvare()
{
int m;
ok=0;
for(m=n;m>=1&&!ok;m--)
gen(1,m);
}
int main()
{
citire();
matrice_ad();
rezolvare();
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 
.
Rezolvarea problemei #2109 Dineu
Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2109 Dineu 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!