core2

Core2

== include(page="template/taskheader" task_id="core2") ==

Tocmai v-ati cumparat un procesor cu 2 core-uri, in speranta ca jocurile voastre preferate vor merge mult mai bine (dinamism mai ridicat, calitate a graficii mai buna, etc.). Fiind nerabdator sa testati noul procesor, vreti sa jucati toate cele N jocuri preferate cat mai curand. Jocurile sunt numerotate de la 1 la N si pentru fiecare joc i se cunoaste durata de joc $d{~i~}$ si satisfactia adusa $s{~i~}$. Constatati repede ca, desi, procesorul este mai avansat din punct de vedere tehnologic, jocurile preferate nu sunt in stare sa foloseasca complet noile capabilitati. Astfel, jocurile de la $1$ la $X$ pot fi rulate numai pe core-ul $1$, iar jocurile $X+1,...,N-1$ pot fi rulate numai pe al doilea core. Jocul $N$ este mai deosebit si necesita folosirea in paralel a ambelor core-uri. Stiind ca la fiecare moment de timp nu poate fi executat mai mult de un joc pe un core si ca nu va deranjeaza sa jucati cate doua jocuri in paralel (cate unul pe fiecare core), precum si ca aveti la dispozitie doar intervalul de timp $[0,T]$ (dupa care trebuie sa mergeti la scoala), determinati ce jocuri veti juca astfel incat satisfactia totala obtinuta sa fie maxima. O constrangere suplimentara este data de faptul ca in intervalul de timp $[T{~1,N~},T{~2,N~}]$ vine in vizita cel mai bun prieten, pe care vreti sa-l impresionati; prin urmare, daca veti decide sa jucati jocul $N$ (cel deosebit), o veti face doar in prezenta prietenului dumneavoastra (altfel spus, jocul $N$ poate fi jucat doar intr-un interval de timp complet inclus in $[T{~1,N~},T{~2,N~}]$). Un joc contribuie la satisfactia totala numai daca este jucat in intregime in intervalul de timp avut la dispozitie.

Tocmai v-ati cumparat un procesor cu 2 core-uri, in speranta ca jocurile voastre preferate vor merge mult mai bine (dinamism mai ridicat, calitate a graficii mai buna, etc.). Fiind nerabdator sa testati noul procesor, vreti sa jucati toate cele N jocuri preferate cat mai curand. Jocurile sunt numerotate de la 1 la N si pentru fiecare joc i se cunoaste durata de joc $d{~i~}$ si satisfactia adusa $s{~i~}$. Constatati repede ca, desi procesorul este mai avansat din punct de vedere tehnologic, jocurile preferate nu sunt in stare sa foloseasca complet noile capabilitati. Astfel, jocurile de la $1$ la $X$ pot fi rulate numai pe core-ul $1$, iar jocurile $X+1,...,N-1$ pot fi rulate numai pe al doilea core. Jocul $N$ este mai deosebit si necesita folosirea in paralel a ambelor core-uri. Stiind ca la fiecare moment de timp nu poate fi executat mai mult de un joc pe un core si ca nu va deranjeaza sa jucati cate doua jocuri in paralel (cate unul pe fiecare core), precum si ca aveti la dispozitie doar intervalul de timp $[0,T]$ (dupa care trebuie sa mergeti la scoala), determinati ce jocuri veti juca astfel incat satisfactia totala obtinuta sa fie maxima. O constrangere suplimentara este data de faptul ca in intervalul de timp $[T{~1,N~},T{~2,N~}]$ vine in vizita cel mai bun prieten, pe care vreti sa-l impresionati; prin urmare, daca veti decide sa jucati jocul $N$ (cel deosebit), o veti face doar in prezenta prietenului dumneavoastra (altfel spus, jocul $N$ poate fi jucat doar intr-un interval de timp complet inclus in $[T{~1,N~},T{~2,N~}]$). Un joc contribuie la satisfactia totala numai daca este jucat in intregime in intervalul de timp avut la dispozitie.

h2. Date de intrare

* $3 ≤ N ≤ 50$
* $1 ≤ X ≤ N-2$
* $1 ≤ d{~i~} ≤ T ≤ 1000$

* $0 ≤ T{~1,N~} ≤ T{~2,N~} ≤ T$

* $0 ≤ T{~1,N~} < T{~2,N~} ≤ T$

* $1 ≤ d{~N~} ≤ T{~2,N~}-T{~1,N~}$
* $1 ≤ s{~i~} ≤ 1000$

* O data inceput,un joc trebuie jucat pana la sfarsit (altfel spus, daca alegeti sa jucati jocul $i$, acesta trebuie jucat pe durata unui interval de timp avand durata $d{~i~}$)).
* Intervalul de timp in care jucati un joc $i$ ($1≤i≤N$) trebuie sa fie complet inclus in intervalul $[0,T]$. Intervalul de timp in care jucati jocul $N$ (daca il jucati) trebuie sa fie complet inclus in intervalul $[T{~1,N~},T{~2,N~}]$.

* O data inceput, un joc trebuie jucat pana la sfarsit (altfel spus, daca alegeti sa jucati jocul $i$, acesta trebuie jucat pe durata unui interval de timp avand durata $d{~i~}$)).
* Intervalul de timp in care jucati un joc $i$ $(1≤i≤N)$ trebuie sa fie complet inclus in intervalul $[0,T]$. Intervalul de timp in care jucati jocul $N$ (daca il jucati) trebuie sa fie complet inclus in intervalul $[T{~1,N~},T{~2,N~}]$.

h2. Exemplu

h3. Explicatie

Jocurile $1$,$2$ si $3$ pot fi rulate numai pe core-ul $1$, iar jocurile $4$, $5$ si $6$ pot fi rulate numai pe core-ul $2$. Jocul $7$ are nevoie de ambele core-uri in paralel. Satisfactia totala maxima egala cu $90$ se obtine in felul urmator: veti juca jocul $1$ in intervalul $[0,16]$, jocul $7$ in intervalul $[17,37]$, jocul $2$ in intervalul $[37,68]$, jocul $5$ in intervalul $[0,17]$ si jocul $4$ in intervalul $[37,60]$. Satisfactia totala este $s{~1~}+s{~2~}+s{~4~}+s{~5~}+s{~7~}=20+13+8+19+30=90$. Observati ca in intervalul $[17,37]$ (cand jucati jocul $7$), niciun alt joc nu este rulat pe nici unul din cele $2$ core-uri, acestea fiind folosite exclusiv de jocul $7$.

Jocurile $1, 2$ si $3$ pot fi rulate numai pe core-ul $1$, iar jocurile $4$, $5$ si $6$ pot fi rulate numai pe core-ul $2$. Jocul $7$ are nevoie de ambele core-uri in paralel. Satisfactia totala maxima egala cu $90$ se obtine in felul urmator: veti juca jocul $1$ in intervalul $[0,16]$, jocul $7$ in intervalul $[17,37]$, jocul $2$ in intervalul $[37,68]$, jocul $5$ in intervalul $[0,17]$ si jocul $4$ in intervalul $[37,60]$. Satisfactia totala este $s{~1~}+s{~2~}+s{~4~}+s{~5~}+s{~7~}=20+13+8+19+30=90$. Observati ca in intervalul $[17,37]$ (cand jucati jocul $7$), niciun alt joc nu este rulat pe nici unul din cele $2$ core-uri, acestea fiind folosite exclusiv de jocul $7$.

== include(page="template/taskfooter" task_id="core2") ==