Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ab.in, ab.out | Sursă | lot 2006 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Adrian Vladu •azotlichid |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   4/5 |
Vezi solutiile trimise | Statistici
AB
Compania farmaceutica AB produce substante ce fac parte din doua categorii: Acizi si Baze. Ea produce M acizi si N baze. Acizii sunt numerotati de la 1 la M, iar bazele sunt numerotate de la 1 la N.
Unii acizi au o afinitate pentru unele baze. Daca un acid este pus impreuna cu o baza pentru care are afinitate, se produce o reactie chimica foarte periculoasa. Doi acizi pusi impreuna nu produc nici o reactie si nici doua baze puse impreuna. Fiecare acid X (1 ≤ X ≤ M) are afinitate pentru fiecare din bazele numerotate cu numere de la 1 la BX. Acizii au o proprietate interesanta, datorata faptului ca acidul X (2 ≤ X ≤ M) este produs ca urmare a rafinarii compozitiei acidului X-1. Astfel, daca acidul X-1 are afinitate pentru fiecare baza dintr-o multime Q, atunci si acidul X are afinitate pentru fiecare dintre bazele din multimea Q. Altfel spus, bazele pentru care are afinitate acidul X-1 reprezinta o submultime a bazelor pentru care are afinitate acidul X. Aceasta implica inegalitatea BX ≥ BX-1.
Compania are la dispozitie K containere si fiecare dintre cele M+N substante trebuie depozitata intr-unul dintre aceste containere. Doua substante pot fi depozitate in acelasi container cu conditia ca ele sa nu reactioneze una cu alta. Depozitarea uneia dintre cele M+N substante in al P-lea container presupune plata unei sume SP. Asadar, pentru fiecare substanta, trebuie platita suma corespunzatoare containerului in care este depozitata. Suma totala platita este egala cu suma sumelor platite pentru fiecare substanta.
Determinati care este suma totala minima pe care trebuie sa o plateasca compania AB pentru a depozita toate substantele, respectand restrictiile precizate.
Date de intrare
Prima linie a fisierului de intrare contine numarul intreg T, reprezentand numarul de seturi de date ce sunt descrise în continuare. Prima linie a fiecarui set de date contine 3 numere intregi, separate prin cate un spaţiu: M, N si K. Urmatoarea linie conţine K numere intregi, separate prin spatii. Al P-lea dintre aceste numere reprezinta suma ce trebuie platita daca o substanta este depozitata in al P-lea container. Urmatoarea linie contine numarul intreg B1. Urmatoarele M-1 linii contin, pentru fiecare acid X de la 2 la M, valorile BX-BX-1 (numarul bazelor "suplimentare" pentru care are afinitate acidul X si nu are afinitate acidul X-1).
Date de iesire
...
Restrictii
- ... ≤ ...
Exemplu
| ab.in | ab.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicatie
...
