Coalicions polítiques P13519


Statement
 

pdf   zip

thehtml

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.

Public test cases
  • 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}
    ----------
    
  • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++