paznici2

Paznici2

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

Poveste si cerinta...

Intr-un oras in plina reconstructie exista $N$ obiective turistice ce trebuie pazite peste nopte. Admistratia orasului a contractat o firma de paza care i-a pus la dispozitie $N$ paznici. Totusi exista un aspect bizar legat de aceasta tranzactie: fiecare paznic isi negociaza individual salariul, in functie de obiectul turistic pe care trebuie sa-l pazeasca. Stiind pretentiile salariale ale fiecarui paznic, Algorel - seful IT de la primarie - trebuie sa distribuie cei $N$ paznici astfel incat:
 
* fiecare obiectiv turistic este pazit de cel putin un paznic
* suma totala a salariilor sa fie cat mai mica
 
Cum Algorel stia sa rezolve rapid astfel de probleme inca din liceu, el a inceput sa mediteze la alte aspecte legate de distribuirea paznicilor. Astfel, pentru fiecare obiectiv el s-a intrebat ce paznici ar putea fi distribuiti sa-l pazeasca in distributiile optime (suma salariilor sa fie minima). Altfel spus, pentru fiecare pereche (paznic $X$, obiectiv $Y$) Algorel doreste sa stie daca exista o distribuire optima in care paznicul $X$ pazeste obiectivul $Y$. Problema s-a dovedit interesanta si Algorel a propus-o in acest concurs.

h2. Date de intrare

Fisierul de intrare $paznici2.in$ ...

Fisierul de intrare $paznici2.in$ contine pe prima linie numarul natural $N$, reprezentand numarul de paznici si numarul de obiective. Urmatorele $N$ linii contin cate $N$ numere: numarul $j$ de pe linia $i+1$ reprezinta salariul paznicului cu numarul $i$ daca va pazi obiectivul cu numarul $j$ (atat obiectivele cat si paznicii sunt numerotati cu numerele de la $1$ la $N$).

h2. Date de iesire

In fisierul de iesire $paznici2.out$ ...

Pe prima linie a fisierului de iesire $paznici2.out$ se va afla suma salariilor paznicilor intr-o distribuire optima. Urmatoarele $N$ linii contin informatii despre paznicii ce pot pazi fiecare obiectiv: primul numar va reprezenta numarul de paznici si apoi numerele de ordine ale acestora in ordine _crescatoare_. Linia $i+1$ va contine informatii despre obiectivul numarul $i$.

h2. Restrictii

* $... ≤ ... ≤ ...$

* Salariile paznicilor sunt numere naturale in intervalul $[1, 1000]$
* In tabelul de mai jos gasiti informatii cu privire la cele 10 teste folosite pentru testare:
 
table(numbers). |_. Test | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|_. N | 7 | 15 | 19 | 25 | 30 | 50 | 80 | 150 | 170 | 200 |
 

h2. Exemplu
table(example). |_. paznici2.in |_. paznici2.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
1 1 1
1 1 1
10 10 1
| 3
2 1 2
2 1 2
1 3

|
h3. Explicatie

...

Distributiile optime sunt: ${(1, 1) (2, 2) (3, 3)}$ si ${(1, 2) (2, 1) (3, 3)}$.

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

2673