== include(page="template/taskheader" task_id="terenuri3d") ==
Poveste şi cerinţă...
_“Iarba din curtea vecinului este întotdeauna mai verde ...”_
Împărţirea recentă a terenurilor din Gheorgheni a generat multă invidie în rândul ţăranilor. Astfel, unii ţărani au impresia că iarba creşte mai verde în curtea unora dintre vecini şi ar dori să se mute într-una din casele acestora. Primaria Gheorgheni a hotărât o redistribuire a proprietăţilor astfel încât gradul total de fericire al ţăranilor să fie cât mai mare.
Redistribuirea se va face ţinând cont de preferinţele ţăranilor pentru anumite case şi de gradul de fericire al fiecărui ţăran, în funcţie de casa în care ar fi repartizat. Vor exista astfel triplete $(x, y, z)$ cu semnificaţia : ţăranul $x$ ar avea gradul de fericire $z$ dacă ar locui în casa $y$. Un ţăran va fi satisfăcut dacă în urma redistribuirii va primi una dintre proprietăţile râvnite. E posibil ca nu toţi ţăranii să poată fi satisfăcuţi, caz în care gradul de fericire al acestora va fi $0$.
Primarul satului Gheorgheni v-ar recompensa cu $100$ de puncte în cazul în care îl ajutati să obţină cel mai mare grad de fericire posibil în sat, adică suma gradelor de fericire a ţăranilor satisfăcuţi. În acest mod şi-ar asigura un nou mandat la următoarele alegeri.
h2. Cerinţă
Dându-se $N$ şi $M$ reprezentând numărul ţăranilor, respectiv numărul caselor din Gheorgheni, precum şi $K$ triplete de forma $(x, y, z)$ cu semnificaţia de mai sus, se cere gradul maxim de fericire, numărul de ţărani satisfăcuţi după împărtire, precum şi toate perechile de forma $(A, B)$ cu semnificaţia : ţăranul $A$ primeşte casa $B$.
h2. Date de intrare
Fişierul de intrare $terenuri3d.in$ ...
Fişierul de intrare $terenuri3d.in$ va conţine pe prima linie trei numere $N$, $M$ şi $K$ cu semnificaţia din enunţ. Următoarele $K$ linii vor conţine câte trei numere $x, y, z$ cu semnificaţia din enunţ, separate prin câte un spaţiu.
h2. Date de ieşire
În fişierul de ieşire $terenuri3d.out$ ...
Fişierul de ieşire $terenuri3d.out$ va conţine pe prima linie un număr întreg $G$ reprezentând gradul maxim de fericire. Pe linia a doua se va afla un număr $P$ reprezentând numărul de ţărani care vor primi o casă dintre cele dorite, iar pe următoarele $P$ linii se vor afla perechile de numere $A, B$ separate printr-un spaţiu cu semnificaţia din enunţ.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, M ≤ 250$
* $1 ≤ K ≤ 1000$
* $1 ≤ gradul maxim de fericire ≤ 30000$
h2. Exemplu
table(example). |_. terenuri3d.in |_. terenuri3d.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2 2 3
1 1 1
2 2 2
1 2 10
| 10
1
1 2
|
h3. Explicaţie
...
Ţăranul $1$ va primi casa $2$, iar ţăranul $2$ nu va fi satisfăcut. Gradul total de fericire din sat va fi $10$. Nicio altă imparţire nu va genera un grad de fericire mai mare.
== include(page="template/taskfooter" task_id="terenuri3d") ==
