La Conferència de Pau de la Federació (continuació)

Com ja sabem, en haver resolt el problema Y63099, la Federació de
Planetes Units organitza una important conferència de pau on assistiran
N delegacions de diferents espècies: Vulcanians, Klingons, Romulans,
Bajorans, Ferengis, i altres. Per invitació del seu comandant B. Sisko,
la conferència te lloc a l’estació Deep Space 9 en òrbita del planeta
Bajor, que aviat s’unirà a la Federació (però no ho ha fet encara). S’ha
aconseguit prou progrés i alguns delegats faran una roda de premsa.
Triar qui hi participarà és un tema delicat, perquè hi ha delegats que
odien altres (moltes vegades, encara que no sempre, l’odi és mutu). No
voldríem tenir a la taula de la roda de premsa dos delegats on un odia
l’altre, però sí voldríem que hi hagués el màxim possible de delegats.

El doctor Bashir ha vist de seguida totes les possibilitats però, tot
seguit, ha marxat a un congrés i no ha deixat cap còpia de les seves
anotacions. Et caldrà ajudar a en Sisko tot reconstruint-les. Qapla’!

Entrada

Un enter no negatiu n indicant quants parells de noms segueixen, i n
parelles de noms que indiquen que la primera persona de la parella odia
a la segona. El valor n apareix sol a una línia i, després, hi ha una
parella per línia. Es garanteix que tothom odia algú altre o és odiat
per algú altre: no hi ha noms que no apareguin a alguna parella.

Sortida

El número més alt de delegats que poden participar a la roda de premsa
sense que ningú dels participants odiï algú altre participant, seguit, a
partir de la línia següent, de totes les maneres d’arribar a aquesta
grandària, amb una solució per línia.

Pista

Cal aplicar un esquema de backtracking.

Observació

L’enunciat no descarta el valor n = 0. En aquest cas, hi ha exactament
una solució (buida!).

Informació sobre el corrector

Podeu escriure en qualsevol ordre tant les solucions com els elements
dins de cada solució.

Informació del problema

Autoria: José Luis Balcázar

Generació: 2026-06-05T06:25:40.554Z

© Jutge.org, 2006–2026.
https://jutge.org
