Índex de poder de Banzhaf (2) U17233

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:

1. Es llisten totes les coalicions guanyadores.

2. 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.

3. 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 calcular-los-hi vosaltres?

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 50$, 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, escriviu $n$ línies amb els índexs de poder dels partits $1$, $2$, $\ldots$, $n$. Escriviu els índexs com a fracció irreductible, seguint el format dels jocs de prova públics. Acabeu cada cas amb una línia amb 10 guions.

Observació

Per a escriure les fraccions irreductibles, podeu fer servir la funció math.gcd de la llibreria math de Python.

La solució esperada d’aquest problema és una programació dinàmica amb cost $O(n^{2} s)$, on $s = \sum_{i=1}^{n} w_{i}$, tot i que es pot resoldre més eficientment.