Coalicions polítiques P13519
La situació política d’un país llunyà està complicada. Hi ha n partits polítics, numerats entre 1 i n, cadascun amb di diputats. Diem que una coalició de partits és guanyadora si la suma dels nombres de diputats és almenys una certa k. Una coalició guanyadora és redundant si té algun partit tal que, treient-lo de la coalició, aquesta encara té k o més diputats. Feu un programa que calculi totes les coalicions guanyadores no redundants.
Entrada
L’entrada consisteix en diversos casos, només amb nombres naturals, cadascun amb k i n, seguides de les di. Suposeu 1 ≤ n ≤ 20, i que tant k com les di estan entre 1 i 106.
Sortida
Per a cada cas, escriviu en ordre lexicogràfic totes les coalicions guanyadores no redundants. Escriviu una línia amb 10 guions després de cada cas.
Observació
La solució esperada és un backtracking amb diverses optimitzacions. Els jocs de proves s’han generat amb la intenció que els punts que us doni el jutge (sobre 100) siguin una aproximació a la nota màxima que podeu obtenir.
Input
68 7 4 8 32 17 34 4 36 100 2 49 50 3 4 1 2 3 2
Output
{1, 2, 4, 6, 7}
{1, 3, 5}
{2, 3, 5}
{3, 4, 5}
{3, 5, 6}
{3, 7}
{5, 7}
----------
----------
{1, 2}
{1, 4}
{2, 4}
{3}
----------
- Author
- Salvador Roura
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++