Equips de programació balancejats solidàriament X71059

Una companyia multinacional participa cada any en les competicions de programació CodeStrengths amb uns quants equips de programadors. Quan organitza els equips, sempre crea un primer equip amb els millors programadors de la companyia, després un segon equip amb els restants millors programadors de la companyia, i així successivament.

Aquest any, amb l’ànim de fer un gest en pro de la concòrdia i la solidaritat entre els pobles del món, la companyia ha decidit formar equips amb només programadors del seu staff que siguin Russos i Estadounidencs, de manera que, si pot ser, els equips estiguin formats per programadors d’ambdós grups i en quantitat balancejada.

De totes maneres, el primer criteri per a formar un equip continua sent el nivell de programació. Per exemple, el primer equip no pot tenir un programador que sigui pitjor que un altre que no estigui al primer equip.

Com a segon criteri, s’intentarà que l’equip a formar estigui tan balancejat com sigui possible. Per exemple, si els equips estan formats per quatre persones, es prefereix un equip amb dos Russos i dos Estadounidencs que no pas un equip amb tres Russos i un Estadounidenc, i això últim és preferible a un equip amb quatre Russos i cap Estadounidenc.

Com a últim criteri, els programadors s’escullen per nom en ordre lexicogràfic (ordre estandar de comparació entre strings).

Entrada

L’entrada té varis casos. La primera línia de cada cas té un natural positiu k, que és el nombre de membres de cada equip a formar. En una segona línia hi ha un natural positiu n₁, que és el nombre de programadors Russos. Després venen n₁ línies, cadascuna amb el nom d’un programador Rus i un natural positiu indicant el seu nivell de programació. Aquestes línies estan ordenades de major a menor per nivell de programació, i en ordre lexicogràfic per a programadors amb el mateix nivell. Després hi ha una nova línia amb un natural positiu n₂, que és el nombre de programadors Estadounidencs. Després venen n₂ línies amb la informació dels programadors Estadounidencs, seguint exactament el mateix format que per als programadors Russos.

Es garantitza que n₁+n₂ és múltiple de k, i que no hi ha repetició de noms. En particular, un nom d’una llista no apareix a l’altra llista.

Sortida

Per a cada cas, s’han d’escriure (n₁+n₂)/k línies. La primera contindrà la llista de noms del primer equip en ordre lexicogràfic. La segona contindrà la llista de noms del segon equip en ordre lexicogràfic. I així successivament. Després de la sortida de cada cas hi ha una línia en blanc.

Observació

Avaluació sobre 10 punts:

• Solució lenta: 5 punts.
• solució ràpida: 10 punts.

Entenem com a solució ràpida una que és correcta, de cost lineal (es permet cost (n₁+n₂)log(k) per a poder aplicar un sort als membres de cada equip) i capaç de superar els jocs de proves públics i privats. Entenem com a solució lenta una que no és ràpida, però és correcta i capaç de superar els jocs de proves públics.