Estem preparant la distribució dels convidats al banquet nupcial dels nostres estimats amics Gride i Broom. A la taula principal, on seuran els nuvis, volem que tothom conegui tothom. A més, volem que hi hagi el màxim de gent possible sota aquesta condició. Quants convidats podem trobar per seure-hi?
Les dades ens diuen quins convidats es coneixen. Tenim primer una línea amb un valor enter no negatiu . Segueixen línies; cadascuna conté dos noms i vol dir que aquests dos convidats es coneixen. Els noms estan formats per letres majúscules o minúscules y venen separats per un espai. (Els nuvis no hi apareixen, doncs sabem que coneixen a la totalitat dels convidats.)
La sortida comença per la quantitat de gent que seurà a la taula principal, sense comptar-hi la feliç parella. Després segueix, en ordre alfabètic, la llista dels noms dels convidats que seuran amb els nuvis a aquesta taula de màxima grandària, cadascú a una línea.
1/ El temps de càlcul dels enviaments correctes es compara amb el d’un backtracking que no és pas especialment intel·ligent. Tanmateix, enviaments massa senzills poden ser rebutjats degut a resultar massa lents.
2/ En principi, podrien existir casos on hi haguès més d’una solució. Tanmateix, es garanteix que, a tots els jocs de proves d’aquest problema, tant públics com privats, la solució és única.
Autoria: Unknown
Traducció: José Luis Balcázar
Generació: 2026-03-27T16:32:47.662Z
© Jutge.org, 2006–2026.
https://jutge.org