Índex de poder de Banzhaf (1) X23697

Statement

En un parlament hi ha $n$ partits polítics, als que ens referirem com $1$ , $2$ , $\ldots$ , $n$ . El partit polític $i$ té $w_{i}$ escons. Les lleis parlamentàries fixen que, per tal que una votació sigui aprovada, cal que hi hagi un mínim de $q$ vots favorables, on $q$ és anomenada la quota del parlament. Així doncs, una coalició de partits $S \subseteq \{1, 2, \ldots, n\}$ és guanyadora si $\sum_{i \in S} w_{i} \geq q$ (assumirem que els membres d’un partit segueixen la disciplina de vot); i que és perdedora altrament.

L’índex de poder de Banzhaf és una manera de quantificar el poder d’un partit polític en les votacions. Es pot calcular de la forma següent:

Es llisten totes les coalicions guanyadores.
En cadascuna d’aquestes coalicions, s’identifiquen els partits crítics. Un partit és crític en una coalició guanyadora si, sense aquest partit, la coalició passa a ser perdedora.
L’índex de poder d’un partit és el nombre de vegades que aquest partit és crític dividit pel nombre de vegades que qualsevol partit és crític.

Per exemple, si $q=8$ , $n = 3$ , $w_{1} = 6$ , $w_{2} = 3$ i $w_{3} = 2$ , hi ha tres coalicions guanyadores:

$\{1, 2\}$ , en la qual tots dos són crítics (ni $\{1\}$ ni $\{2\}$ són coalicions guanyadores).
$\{1, 3\}$ , en la qual tots dos són crítics (ni $\{1\}$ ni $\{3\}$ són coalicions guanyadores).
$\{1, 2, 3\}$ , en la qual només $1$ és crític (perquè tant $\{1, 2\}$ com $\{1, 3\}$ són guanyadores, però no $\{2, 3\}$ ).

En total, $1$ és crític 3 cops, $2$ és crític 1 cop, i $3$ és crític $1$ cop. Com que el nombre de vegades que qualsevol partit és crític és $3 + 1 + 1 = 5$ , els índexs de poder dels partits $1$ , $2$ i $3$ són $\frac{3}{5}$ , $\frac{1}{5}$ i $\frac{1}{5}$ , respectivament.

Un politòleg vol calcular els índexs de poder dels partits del parlament, però no se’n surt. Podeu generar-li totes les coalicions guanyadores, i indicar-li quins partits són crítics en cadascuna d’elles?

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $q$ , la quota, i $n$ , el nombre de partits. A continuació vénen $n$ nombres $w_{i}$ . Podeu suposar que $2 \leq n \leq 10$ , que $0 < w_{i} \leq 50$ per tot $1 \leq i \leq n$ , i que $\frac{s}{2} \leq q \leq s \leq 500$ , on $s = \sum_{i=1}^{n} w_{i}$ . En particular, això garanteix que sempre hi haurà almenys un partit crític.

Sortida

Per cada cas, genereu totes les coalicions guanyadores en l’ordre següent: primer les que no tenen $1$ , després les que sí; en cas d’empat, primer les que no tenen $2$ , després les que sí; en cas d’empat, primer les que no tenen $3$ , després les que sí; i així successivament. Per cadascuna de les coalicions guanyadores, indiqueu quins partits són crítics, en ordre numèric creixent. Seguiu el format dels jocs de prova públics. Acabeu cada cas amb una línia amb 10 guions.

Public test cases

Input

Output

de [1, 3] critics [1, 3]
de [1, 2] critics [1, 2]
de [1, 2, 3] critics [1]
----------
de [1] critics [1]
de [1, 3] critics [1]
de [1, 2] critics [1]
de [1, 2, 3] critics [1]
----------
de [1, 3] critics [1, 3]
de [1, 2] critics [1, 2]
de [1, 2, 3] critics [1]
----------
de [2, 3, 4] critics [2, 3, 4]
de [1, 3] critics [1, 3]
de [1, 3, 4] critics [1, 3]
de [1, 2] critics [1, 2]
de [1, 2, 4] critics [1, 2]
de [1, 2, 3] critics [1]
de [1, 2, 3, 4] critics []
----------
de [2, 3, 4] critics [2, 3, 4]
de [1, 3] critics [1, 3]
de [1, 3, 4] critics [1, 3]
de [1, 2] critics [1, 2]
de [1, 2, 4] critics [1, 2]
de [1, 2, 3] critics [1]
de [1, 2, 3, 4] critics []
----------
de [2, 3] critics [2, 3]
de [2, 3, 4] critics [2, 3]
de [1, 3] critics [1, 3]
de [1, 3, 4] critics [1, 3]
de [1, 2] critics [1, 2]
de [1, 2, 4] critics [1, 2]
de [1, 2, 3] critics []
de [1, 2, 3, 4] critics []
----------

Information

Author: Enric Rodríguez
Language: Catalan
Official solutions: Python
User solutions: Python