Hoata

Hoața

== include(page="template/taskheader" task_id="hoata2") ==

Într-un muzeu se află un coridor liniar format din $N$ camere, numerotate de la $1$ la $N$. În camera $1 &le; i &le; N$ se găseşte o rezervă infinită de lingouri de aur de acelaşi tip de valoare <tex> ${v}_{i}$ </tex> şi greutate <tex> ${g}_{i}$ </tex>. În prima cameră intră $K$ hoţi, fiecare având în spinare câte un rucsac de capacitate $G$, iniţial gol. Când un hoţ se află în camera $i$, acesta poate sustrage oricâte lingouri din camera curentă şi să le adauge în rucsacul său, cu condiţia ca suma greutăţilor lingourilor din rucsac să nu depăşească $G$. Un lingou o dată furat, acesta va rămâne în rucsacul hoţului până la ieşirea din muzeu.

Într-un muzeu se află un coridor liniar format din $N$ camere, numerotate de la $1$ la $N$. În camera $1 ≤ i ≤ N$ se găseşte o rezervă infinită de lingouri de aur de acelaşi tip de valoare $v{~i~}$ şi greutate $g{~i~}$. În prima cameră intră $K$ hoţi, fiecare având în spinare câte un rucsac de capacitate $G$, iniţial gol. Când un hoţ se află în camera $i$, acesta poate sustrage oricâte lingouri din camera curentă şi să le adauge în rucsacul său, cu condiţia ca suma greutăţilor lingourilor din rucsac să nu depăşească $G$. Un lingou o dată furat, acesta va rămâne în rucsacul hoţului până la ieşirea din muzeu.

Hoţii acţionează în grup, aşa că ei vor face turul muzeului în $N$ paşi, după cum urmează: la pasul $1 &le; i &le; N$ toţi hoţii avansează din camera $i$ în camera $i + 1$, unde camera $N + 1$ se consideră exteriorul muzeului. Observăm că după primii $i$ paşi toţi hoţii se vor afla în camera $i + 1$. Conducerea muzeului a instalat alarme în dreptul uşilor dintre oricare două camere consecutive. Mai exact, alarma $1 &le; i &le; N$ este instalată între camerele $i$ şi $i + 1$ şi este caracterizată de o valoare <tex> ${x}_{i}$ </tex>. Aceasta se declanşează dacă şi numai dacă în momentul când hoţii trec pe uşa dintre camerele $i$ şi $i + 1$ există cel puţin <tex> ${x}_{i} + 1$ </tex> hoţi ale căror rucsacuri au aceeaşi greutate totală la acel moment, deoarece în acest caz s-ar efectua un control de rutină şi hoţii ar fi prinşi (acest lucru se întâmplă chiar şi dacă hoţii nu au furat nimic până la acel moment). Bineînţeles, alarma $N$ este instalată între camera $N$ şi exteriorul muzeului.

Hoţii acţionează în grup, aşa că ei vor face turul muzeului în $N$ paşi, după cum urmează: la pasul $1 ≤ i ≤ N$ toţi hoţii avansează din camera $i$ în camera $i + 1$, unde camera $N + 1$ se consideră exteriorul muzeului. Observăm că după primii $i$ paşi toţi hoţii se vor afla în camera $i + 1$. Conducerea muzeului a instalat alarme în dreptul uşilor dintre oricare două camere consecutive. Mai exact, alarma $1 ≤ i ≤ N$ este instalată între camerele $i$ şi $i + 1$ şi este caracterizată de o valoare $x{~i~}$. Aceasta se declanşează dacă şi numai dacă în momentul când hoţii trec pe uşa dintre camerele $i$ şi $i + 1$ există cel puţin $x{~i~}$ hoţi ale căror rucsacuri au aceeaşi greutate totală la acel moment, deoarece în acest caz s-ar efectua un control de rutină şi hoţii ar fi prinşi (acest lucru se întâmplă chiar şi dacă hoţii nu au furat nimic până la acel moment). Bineînţeles, alarma $N$ este instalată între camera $N$ şi exteriorul muzeului.

Odată ieşiţi din muzeu, hoţii calculează captura totală ca fiind suma valorilor $v$ corespunzătoare lingourilor din cele $K$ rucsacuri. Se dau $T$ scenarii, şi pentru fiecare se cere captura maximă posibilă în condiţiile date, sau $−1$ dacă orice s-ar întâmpla hoţii ar fi prinşi.
h2. Date de intrare

Prima linie conţine un singur număr natural $T$, reprezentând numărul de scenarii. Urmează descrierile celor $T$ scenarii. Descrierea unui scenariu se face după cum urmează: pe prima linie trei numere naturale $N$, $K$, $G$, separate prin spaţii; pe următoarele $N$ linii câte trei numere naturale, unde pe linia $1 &le; i &le; N$ se află numerele <tex> ${v}_{i}$, ${g}_{i}$, ${x}_{i}$ </tex> separate prin spaţii.

Prima linie conţine un singur număr natural $T$, reprezentând numărul de scenarii. Urmează descrierile celor $T$ scenarii. Descrierea unui scenariu se face după cum urmează: pe prima linie trei numere naturale $N$, $K$, $G$, separate prin spaţii; pe următoarele $N$ linii câte trei numere naturale, unde pe linia $1 ≤ i ≤ N$ se află numerele $v{~i~}, g{~i~}, x{~i~}$ separate prin spaţii.

h2. Date de ieşire

* $1 ≤ $N$ ≤ 300$
* $1 ≤ $K$ ≤ 50$
* $1 ≤ $G$ ≤ 300$

* $1$ &le; <tex> ${v}_{i}$ </tex> &le; $300$, oricare ar fi $1 &le; i &le; N$.
* $1$ &le; <tex> ${g}_{i}$ </tex> &le; $300$, oricare ar fi $1 &le; i &le; N$.
* $1$ &le; <tex> ${x}_{i}$ </tex> &le; $50$, oricare ar fi $1 &le; i &le; N$.
* $1$ &le; <tex> ${S}_{N}$ </tex> &le; $900$, unde cu <tex> ${S}_{N}$ </tex> am notat suma valorilor $N$ corespunzătoare celor $T$ scenarii.

* $1 ≤ v{~i~} ≤ 300$, oricare ar fi $1 ≤ i ≤ N$.
* $1 ≤ g{~i~} ≤ 300$, oricare ar fi $1 ≤ i ≤ N$.
* $1 ≤ x{~i~} ≤ 50$, oricare ar fi $1 ≤ i ≤ N$.
* $1 ≤ S{~N~} ≤ 900$, unde cu $S{~N~}$ am notat suma valorilor $N$ corespunzătoare celor $T$ scenarii.
 
|_. # |_. Punctaj |_. Restricţii |
| $1$
$2$
$3$
$4$
| $11$
$18$
$40$
$31$
| $N ≤ 4, K ≤ 3, G ≤ 7, S{~N~} ≤ 12, v{~i~} ≤ 20, 2 ≤ g{~i~} ≤ 7, x{~i~} ≤ 3$, oricare ar fi $1 ≤ i ≤ N$.
Există $1 ≤ j ≤ N$ astfel încât $x{~i~} = K$ oricare ar fi $1 ≤ i ≤ N$, $i$ ≠ $j$.
$N ≤ 40, G ≤ 40, S{~N~} ≤ 120, v{~i~} ≤ 40, g{~i~} ≤ 40$, oricare ar fi $1 ≤ i ≤ N$.
Fără restricţii suplimentare.
|

h2. Exemplu

**Primul scenariu**

Avem $N = 2$ camere şi $K = 1$ hoţ înzestrat cu un rucsac de capacitate $G = 3$. În camera $1$ se află o rezervă infinită de lingouri de aur de valoare $10$ şi greutate $2$, iar în camera $2$ se află o rezervă infinită de lingouri de aur de valoare $9$ şi greutate $1$. Alarma dintre camera $1$ şi camera $2$ are <tex> ${x}_{1}$ </tex> = $1$, iar alarma dintre camera $2$ şi ieşire are <tex> ${x}_{1}$ </tex> = $2$. În condiţiile date alarmele nu vor suna indiferent ce alege să facă hoţul, aşa că acesta poate obţine o captura maximă de $27 = 9 + 9 + 9$ furând trei lingouri din camera $2$.

Avem $N = 2$ camere şi $K = 1$ hoţ înzestrat cu un rucsac de capacitate $G = 3$. În camera $1$ se află o rezervă infinită de lingouri de aur de valoare $10$ şi greutate $2$, iar în camera $2$ se află o rezervă infinită de lingouri de aur de valoare $9$ şi greutate $1$. Alarma dintre camera $1$ şi camera $2$ are $x{~1~} = 1$, iar alarma dintre camera $2$ şi ieşire are $x{~2~} = 2$. În condiţiile date alarmele nu vor suna indiferent ce alege să facă hoţul, aşa că acesta poate obţine o captura maximă de $27 = 9 + 9 + 9$ furând trei lingouri din camera $2$.

**Al doilea scenariu**

Acest scenariu este identic cu primul, doar că avem $K = 2$ hoţi, fiecare având cate un rucsac de capacitate $3$. Dacă ambii hoţi iau câte $3$ lingouri din camera $2$, atunci aceştia ar avea o captură totală de $54 = 6 × 9$. Din păcate, dacă ar face acest lucru, ei ar fi prinşi de alarma dintre camerele $1$ şi $2$. Observăm că ei ar fi prinşi de aceasta alarmă chiar şi dacă aleg sa nu fure nimic din nicio cameră! Captura maximă, de fapt, se obţine, de exemplu, dacă primul hoţ alege să fure câte un lingou din fiecare cameră(total $19 = 10 + 9$), iar al doilea hoţ alege să fure trei lingouri din camera 2(total $27 = 9 + 9 + 9$). În total $46 = 19 + 27$.

Acest scenariu este identic cu primul, doar că avem $K = 2$ hoţi, fiecare având cate un rucsac de capacitate $3$. Dacă ambii hoţi iau câte $3$ lingouri din camera $2$, atunci aceştia ar avea o captură totală de $54 = 6 × 9$. Din păcate, dacă ar face acest lucru, ei ar fi prinşi de alarma dintre camerele $1$ şi $2$. +Observăm că ei ar fi prinşi de aceasta alarmă chiar şi dacă aleg sa nu fure nimic din nicio cameră!+ Captura maximă, de fapt, se obţine, de exemplu, dacă primul hoţ alege să fure câte un lingou din fiecare cameră(total $19 = 10 + 9$), iar al doilea hoţ alege să fure trei lingouri din camera $2$(total $27 = 9 + 9 + 9$). În total $46 = 19 + 27$.
 
**Al treilea scenariu**
 
Acest scenariu este identic cu primele două, doar că avem $K = 3$ hoţi. În acest caz cei trei hoţi nu vor putea trece de camera $1$ fără să declanşeze alarma, deci răspunsul este $−1$.

== include(page="template/taskfooter" task_id="hoata2") ==