La venjança de Cthulhu

Com potser sabreu, l’any passat els participants del SWERC van fer un
gran descobriment: mitjançant un ritual es pot invocar el gran Cthulhu,
sacrificar un integrant de l’equip, i a canvi rebre un AC. Però els
equips de la UPC van provocar la ira de Cthulhu gosant fer massa
invocacions, i al SWERC d’enguany Cthulhu es va venjar. El seu pla va
ser sinistre: La nit abans del SWERC, va fer sorgir un cementiri al
costat de l’hotel on estaven els equips de la UPC, i la mala sort que
duen els cementiris va condemnar els equips UPC al fracàs.

Cthulhu va haver de resoldre el següent problema: Donada la superfície s
del cementiri, el nombre de tombes disponibles n, i l’espai e_(i) i la
mala sort m_(i) de cada tomba i, cal maximitzar la suma de mala sort
sense que la suma d’espais excedeixi s. El gran Cthulu sap resoldre
aquest problema (ell ho sap tot), però com a servents seus li heu de fer
la feina bruta.

Entrada

L’entrada consisteix en diversos casos, només amb naturals, cadascun amb
s i n, seguits de n parells e_(i) m_(i). Podeu suposar 1 ≤ s ≤ 10⁴,
1 ≤ n ≤ 100, 1 ≤ e_(i) ≤ s, i 1 ≤ m_(i) ≤ 10⁹.

Sortida

Per a cada cas, escriviu la màxima mala sort que no sobrepassi la
superfície disponible.

[image]

Informació del problema

Autoria: Enrique Jiménez

Generació: 2026-01-25T10:06:27.782Z

© Jutge.org, 2006–2026.
https://jutge.org
