Fişierul intrare/ieşire:paznici2.in, paznici2.outSursăStelele Informaticii 2007-2008, Clasele 11-12
AutorSilviu-Ionut GanceanuAdăugată desilviugSilviu-Ionut Ganceanu silviug
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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:
Test12345678910
N7151925305080150170200

Exemplu

paznici2.inpaznici2.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)}.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content