Diferente pentru problema/sant intre reviziile #1 si #6

Diferente intre titluri:

sant
Sant

Diferente intre continut:

== include(page="template/taskheader" task_id="sant") ==
Poveste si cerinta...
Pentru a sapa un sant de lungime $S$, apelam la o firma de constructii care ne pune la dispozitie muncitori de diverse categorii (in total $C$ categorii notate $1$, $2$, ..., $C$). Un muncitor de categorie superioara munceste mai mult si mai bine, dar cere si un salariu mai mare. Vrem sa terminam lucrarea intr-o singura zi, asa ca ne intereseaza pentru fiecare categorie care e salariul si cati metri sapa pe zi un muncitor din categoria respectiva. In plus vrem sa angajam exact $N$ muncitori (avem $N$ locuri la masa!). Se mai stie ca pentru fiecare categorie exista un numar suficient de mare de muncitori si un muncitor nu se opreste pana nu sapa lungimea corespunzatoare categoriei sale.
 
h2. Cerinta
 
Gasiti posibilitatea de a angaja $N$ muncitori de diverse categorii care sa sape exact $S$ metri intr-o zi si sa poata fi platiti cu suma cea mai mica posibila.
h2. Date de intrare
...
Pe prima linie a fisierului de intrare $sant.in$ sunt scrise numerele naturale $S$, $N$ si $C$, (lungimea santului, numarul de muncitori pe care vrem sa-i angajam si numarul de categorii) separate prin cate un spatiu. Pe urmatoarele $C$ linii sunt cate doua numere naturale $L{~i~}$ si $P{~i~}$ ({$i$}= {$1$}, $2$, ..., $C$) reprezentand lungimea santului sapat si plata ceruta pentru o zi, de un muncitor de categoria $i$.
h2. Date de iesire
...
Prima linie a fisierului $sant.out$ va contine suma minima care poate fi platita unui numar de $N$ muncitori care sapa exact $S$ metri intr-o zi sau cifra $0$ daca nu exista solutie. Daca exista solutie, urmatoarea linie va contine un sir de $N$ numere ordonate crescator, reprezentand categoriile muncitorilor angajati. Daca sunt mai multe solutii se va alege solutia cea mai mica din punct de vedere lexicografic (pentru cine a uitat, un exemplu: conform ordinei lexicografice sirul $1$ $1$ $1$ $2$ $3$ $3$ este mai mic decat sirul $1$ $1$ $2$ $2$ $2$ $3$).
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1$ ≤ $N$ ≤ $100$
* $1$ ≤ $S$ ≤ $1000$
* $1$ ≤ $C$ ≤ $20$
* $1$ ≤ $L{~i~}$, $P{~i~}$ ≤ $100$
h2. Exemplu
table(example). |_. sant.in |_. sant.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 15 5 4
1 1
2 3
3 7
5 10
| 27
1 2 2 4 4
|
h3. Explicatie
== include(page="template/taskfooter" task_id="sant") ==
 
...
== include(page="template/taskfooter" task_id="sant") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
1787