Selecció musical X93236
Després d’un any de moltes penúries, per aixecar els ànims decideixes organitzar unes vacances amb uns amics en un racó perdut a la muntanya. Com que a tots els amics els agrada molt la música, però d’estils molt diferents, per tal que les vacances surtin bé és important que, durant el trajecte en cotxe, tothom pugui escoltar cançons del seu gust. Malauradament, la llista de totes les cançons que els amics voldrien escoltar és interminable, i el viatge en cotxe és llarg però no tant. Per això acordeu conformar-vos si cadascú pot escoltar almenys una de les seves cançons preferides. Pots encarregar-te tu de la selecció musical?
Entrada
L’entrada només conté nombres enters. Comença amb n, el nombre de cançons que es poden escollir. Segueix m, el nombre d’amics, i després m línies, cadascuna de les quals comença amb si, el nombre de cançons preferides de l’amic i-èsim, seguit de les corresponents si cançons. Cada cançó s’identifica amb un nombre entre 0 i n−1. L’entrada acaba amb k, el nombre màxim de cançons que es poden escollir. Podeu assumir que 1 ≤ n ≤ 25, que 1 ≤ m ≤ 250, i que 1 ≤ si, k ≤ n.
Sortida
Escriviu totes les seleccions de com a molt k cançons tals que cada amic pot escoltar almenys una de les seves cançons preferides. A cada selecció cal escriure les cançons en ordre creixent d’identificador. Les seleccions es poden escriure en ordre arbitrari.
Observació
Heu d’implementar un poda que descarti les solucions parcials quan ja no es poden estendre de forma que tots els amics quedin satisfets.
Input
7 4 3 1 2 5 4 5 3 1 0 3 4 6 3 1 6 2
Output
5,6 1,6
Input
2 2 1 0 1 1 1
Output
Input
2 2 1 0 1 1 2
Output
0,1
- Author
- Enric Rodríguez
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++