Nu exista diferente intre titluri.
Diferente intre continut:
== include(page="template/taskheader" task_id="checkin") ==
Ministerul organizează o excursie pentru olimpici la Paris. Suntem toţi la aeroport, $K$ olimpici având în total $P$ bagaje. Olimpicii la informatică trebuie să rezolve acum următoarea problemă.
Pentru zborul către Paris au fost deschise $N$ ghişee pentru check-in, numerotate de la $1$ la $N$. La fiecare ghişeu lucrează exact un angajat. Angajatul de la ghişeul $i$ are nevoie de $A{~i~}$ secunde pentru a procesa fiecare bagaj al clientului prezentat la ghişeu şi $B{~i~}$ secunde pentru a emite toate tichetele de îmbarcare solicitate de client (acelaşi timp $B{~i~}$, indiferent de numărul de tichete solicitate de client).
O persoană poate sta la un singur ghişeu şi poate preda $0$, $1$ sau mai multe bagaje (acestea vor fi trecute pe numele său). Evident, aceeaşi persoană nu poate sta la mai multe ghişee. De asemenea, o persoană poate să prezinte angajatului de la ghişeu biletele şi paşapoartele altor persoane, astfel că poate solicita emiterea mai multor tichete de îmbarcare. O persoană trebuie să solicite de la ghişeul la care se prezintă cel puţin un tichet de îmbarcare.
Pentru zborul către Paris au fost deschise $N$ ghişee pentru check-in, numerotate de la $1$ la $N$. La fiecare ghişeu lucrează exact un angajat. Angajatul de la ghişeul $i$ are nevoie de $A{~i~}$ secunde pentru a procesa fiecare bagaj al clientului prezentat la ghişeu şi $B{~i~}$ secunde pentru a emite toate tichetele de îmbarcare solicitate de client (acelaşi timp $B{~i~}$, indiferent de numărul de tichete solicitate de client). O persoană poate sta la un singur ghişeu şi poate preda $0$, $1$ sau mai multe bagaje (acestea vor fi trecute pe numele său). Evident, aceeaşi persoană nu poate sta la mai multe ghişee. De asemenea, o persoană poate să prezinte angajatului de la ghişeu biletele şi paşapoartele altor persoane, astfel că poate solicita emiterea mai multor tichete de îmbarcare. O persoană trebuie să solicite de la ghişeul la care se prezintă cel puţin un tichet de îmbarcare.
Iniţial nimeni nu stă la coadă la ghişeele pentru Paris. Timpul necesar pentru a face check-in-ul (predarea tuturor celor $P$ bagaje şi obţinerea tichetelor de îmbarcare pentru toţi cei $K$ olimpici) depinde de strategia adoptată (alegerea ghişeelor, stabilirea persoanelor care stau la coadă la ghişee şi împărţirea bagajelor). Olimpicii la informatică trebuie să găsească o strategie prin care cei $K$ olimpici pot preda cele $P$ bagaje şi obţine cele $K$ tichete de îmbarcare în cel mai scurt timp.
h2. Cerinta
h2. Restricţii
* $1 ≤ N ≤ 1000$
* $1 ≤ A{~i~}, B{~i~} ≤ 1000$
* $1 ≤ K ≤ 10000$
* $0 ≤ P ≤ 10000$
* $1 ≤ N ≤ 1.000$
* $1 ≤ A{~i~}, B{~i~} ≤ 1.000$
* $1 ≤ K ≤ 10.000$
* $0 ≤ P ≤ 10.000$
h2. Exemplu
10 10
4 10
| 70
|
|
h3. Explicaţie
O persoană stă la ghişeul $3$, predă un bagaj şi ia un tichet de îmbarcare.
Nu exista diferente intre securitate.
Diferente intre topic forum:
