# Investidura

En un indret molt molt llunyà, les darreres eleccions estatals han
deixat el parlament molt fragmentat. Tant, que els partits polítics no
han estat capaços fins ara de trobar la manera d'acordar la investidura
d'un president del govern, ni tan sols en segona ronda (on només cal
majoria simple). Els podeu donar un cop de mà?

<figure data-latex-placement="htp">
<embed src="parlament.eps" style="width:70mm" />
</figure>

## Entrada

L'entrada comença amb $n$, el nombre de partits polítics. El segueixen
parells $e_{i}$, $p_{i}$, un per cada $0 \leq i < n$, on $e_{i}$ és un
natural que indica el nombre d'escons al parlament aconseguits pel
partit $i$-èsim en les darreres eleccions, i $p_{i}$ és un natural entre
0 i 1000 que mesura el perfil polític del partit (sent $0$ extrema
esquerra, i $1000$ extrema dreta). L'entrada conclou amb un natural $m$,
que és la diferència màxima de perfil polític permesa entre els partits
*que no estan en contra* de la investidura. Podeu assumir també que
$2 \leq n \leq 20$, que $1 \leq e_{i} \leq 300$, i que
$0 \leq m \leq 1000$.

## Sortida

Escriviu cadascuna de les diferents possibilitats per investir president
del govern (en segona ronda). Per a que això sigui possible, cal que hi
hagi majoria simple: això és, que la suma dels vots a favor sigui més
gran estrictament que la suma dels vots en contra; les abstencions no
compten. Assumiu que els parlamentaris poden votar a favor, en contra, o
abtenir-se; i que segueixen la disciplina de partit, això és, tots els
membres d'un partit voten el mateix. També cal que la diferència de
perfil polític entre dos partits qualssevol que estiguin a favor de la
investidura o que s'abstinguin sigui no superior a $m$.

Seguiu el format donat en els jocs de prova. Per cada $0 \leq i < n$, el
partit $i$-èsim s'identifica amb $i$. A més d'escriure els partits a
favor, els que s'abstenen i els que hi estan en contra, indiqueu també,
dels partits a favor, els que tinguin més escons (ja que el candidat a
president del govern serà d'un d'aquests partits).

No importa l'ordre de les solucions, però a cada solució, els partits
que voten a favor han d'estar ordenats de forma creixent; i igualment
per als que s'abstenen i per als que voten en contra. També els partits
a favor amb el màxim d'escons s'han d'escriure ordenats de la mateixa
manera.

Escriviu una línia en blanc després de cada solució.

## Informació del problema

Autoria: Enric Rodríguez

Generació: 2026-01-25T17:22:06.994Z

© *Jutge.org*, 2006--2026.\
<https://jutge.org>
