Anul acesta se organizează prima ediție a Olimpiadei Pluridisciplinare pentru Centrele de Excelență, PluriCEX. Fiecare Centru de Excelență din țară va trimite la concurs o echipă formată din k membri (toți participanți la Centrul de Excelență). Echipa va trebui să rezolve probleme interdisciplinare, disciplinele vizate fiind cele de la Centrul de Excelenţă (D discipline, pe care le vom considera numerotate de la 1 la D).
Directorul CEX Iași a făcut o listă cu primii n cei mai buni elevi de la CEX, apoi a numerotat elevii de la 1 la n, în ordinea apariției lor în listă. Pentru fiecare elev, directorul a notat disciplinele la care el participă la CEX.

Cerința

Scrieți un program care să determine toate echipele ce pot fi formate din k dintre cei n elevi de pe lista directorului, cu condiția ca pentru fiecare disciplină să existe în echipă cel puțin un membru care să studieze la CEX disciplina respectivă.

Date de intrare

Fișierul de intrare pluricex1.in conţine pe prima linie trei numere naturale n k D (cu semnificația din enunț). Urmează n linii care descriu participările la CEX ale celor n elevi de pe lista directorului. Mai exact, pe linia i+1 este descrisă participarea elevului i astfel: nr d1 d2 ... dnr. Primul număr de pe linie (nr) indică numărul de discipline la care participă elevul i. Următoarele nr numere reprezintă disciplinele la care participă elevul i. Numerele scrise pe aceeași linie sunt separate prin spațiu.

Date de ieșire

Fișierul de ieșire pluricex1.out va conţine toate echipele ce se pot forma respectând condiţiile din enunţ, câte o echipă pe o linie. Membrii unei echipe vor fi scrişi în ordine crescătoare, separaţi prin câte un spaţiu. Echipele vor fi scrise în ordine lexicografică.

Restricții și precizări

0 < n ≤ 22
0 < k ≤ 8
0 < D ≤ 10
Pentru datele de test problema admite întotdeauna soluţie, numărul de soluţii fiind mai mic de 20000.
Spunem că vectorul (x1, x2, ..., xn) precedă lexicografic vectorul (y1, y2, ..., yn) dacă există un indice i astfel încât xj=yj, pentru orice 1 ≤ j < i, iar xi < yi.

Exemplu

pluricex1.in

pluricex1.out

2 3 4
3 4 5

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

#include <bits/stdc++.h>

using namespace std;

int n, k, D, st[30], a[30], S;

ofstream fout("pluricex1.out");

void Citire()
{
    int i, j, p, x;
    ifstream fin("pluricex1.in");
    fin >> n >> k >> D;
    for (i = 1; i <= n; i++)
    {
        fin >> p;
        a[i] = 1;
        for (j = 1; j <= p; j++)
        {
            fin >> x;
            a[i] |= (1 << x);
        }
    }
    fin.close();
    S = (1 << (D+1)) - 1;
}

void Afisare()
{
    int i, rez;
    rez = 0;
    for (i = 1; i <= k; i++)
        rez |= a[st[i]];
    if (rez != S) return;
    for (i = 1; i <= k; i++)
        fout << st[i] << " ";
    fout << "\n";
}

void Gen(int top)
{
    int i;
    if (top == k + 1) Afisare();
    else for (i = st[top-1]+1; i <= n; i++)
    {
        st[top] = i;
        Gen(top + 1);
    }
}

int main()
{
    Citire();
    Gen(1);
    fout.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 #2171 pluricex1

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