| Fişierul intrare/ieşire: | paznici2.in, paznici2.out | Sursă | Stelele Informaticii 2007-2008, Clasele 11-12 |
| Autor | Silviu-Ionut Ganceanu | Adăugată de |  Silviu-Ionut Ganceanu •silviug |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Paznici2
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.
Date de intrare
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).
Date de iesire
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.
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:
| Test | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| N | 7 | 15 | 19 | 25 | 30 | 50 | 80 | 150 | 170 | 200 |
Exemplu
| paznici2.in | paznici2.out |
|---|---|
| 3 1 1 1 1 1 1 10 10 1 | 3 2 1 2 2 1 2 1 3 |
Explicatie
Distributiile optime sunt: {(1, 1) (2, 2) (3, 3)} si {(1, 2) (2, 1) (3, 3)}.
