Informatika gyűjtemény

Egy szinttel feljebb Csapatok

2004050607080910

NézetNyomtat

Csapatok

Az "Extrém Programozók Versenyére" N programozó jelentkezett. A jelentkezőket két csapatba kell osztanunk, a következő szempontok érvényesítésével:
  • minden jelentkező pontosan az egyik csapathoz tartozik
  • minden csapatnak legalább egy tagja van
  • minden programozó ismeri az összes csapattársát
  • a csapatok létszáma közötti különbség minimális

Feladat

Írj programot, ami elkészíti a csapatbeosztást, vagy kiírja, hogy a megadott feltételek mellett nem készíthető el a beosztás.

Bemenet

A programozókat az 1,2,...,N számokkal jelöljük. ($1 \lt N \le 100$) A teams.in inputfájl első sora a jelentkezők számát, a további N sor pedig a jelentkezők által ismert programozók sorszámát tartalmazza. (Az ismerettség nem kölcsönös!) Az ismerősök sorszámát szóközök választják el, a listát 0 zárja.

Kimenet

A teams.out kimeneti fájl a "No solution" szöveget tartalmazza, ha nem készíthető beosztás. Ha készíthető, akkor a kimeneti fájl két sora a csapatokat adja meg, a tagok sorszámának felsorolásával. Az első szám a tagok száma, utána következik a tagok sorszáma, szóközökkel elválasztva.

Példák

teams.inteams.out
5 3 4 5 0 1 3 5 0 2 1 4 5 0 2 3 5 0 1 2 3 4 0 No solution
teams.in teams.out
5 2 3 5 0 1 4 5 3 0 1 2 5 0 1 2 3 0 4 3 2 1 0 3 1 3 5 2 2 4

Tesztadatok