Nu exista diferente intre titluri.
Diferente intre continut:
_Textul problemei stă sub influenţa noului curent literar numit $umorul absent$_
Marcel se plimba liniştit cu blatmobilul când, deodată, îi auzi pe _$Dl. IOI$_, _$Nry$_ şi _$Semicerc$_ vorbind ca la colţul străzii. Pentru că erau la colţul străzii. Spirit şantajist, Marcel s-a gândit că poate subtiliza informaţii relevante dacă stă şi îi ascultă. Pentru a nu părea suspect, a coborât din blatmobil şi le-a dat târcoale celor trei, dând senzaţia că e în căutare de benzină. În sensul de motivat. A aflat că cei trei puneau la cale o apariţie în Azerbaidjan sub noile nume de scenă _$Dl. IOIT$_, _$Nrz$_, respectiv _$Demicerc$_. Realizând că numai în romanele poliţiste şi în scrisori pierdute poţi afla informaţii suficient de prestigioase trăgând cu urechea, Marcel a plecat să caute benzină în altă parte. Adică motivat.
Marcel se plimba liniştit cu blatmobilul când, deodată, îi auzi pe _Dl IOI_, _Nry_ si _Semicerc_ vorbind ca la colţul strazii. Pentru că erau la colţul străzii. Spirit şantajist, Marcel s-a gândit că poate subtiliza informaţii relevante dacă stă şi îi ascultă. Pentru a nu părea suspect, a coborât din blatomobil si le-a dat târcoale celor trei dând senzatia că e în căutare de benzină. În sensul de motivat. A aflat că cei trei puneau la cale o apariţie în Azerbaidjan sub noile nume de scenă _Dl IOIT_, _Nrz_, respectiv _Demicerc_. Realizând că numai in romanele poliţiste şi în scrisori pierdute poţi afla informaţii suficient de prestigioase tragând cu urechea, Marcel a plecat să caute benzină in alta parte. Adică motivat.
h2. Cerinţă
h2. Cerinta
Se dă un număr $N$ şi două şiruri $A$ şi $B$ de câte $2 * N$ numere naturale. Să considerăm o parantezare corectă de lungime $2 * N$ căreia vrem să îi calculăm costul. Pentru fiecare paranteză $i$, dacă e deschisă adăugam $A{~i~}$ iar dacă e închisă adăugăm $B{~i~}$. Găsiţi costul maxim al unei parantezări corecte!
Se dă un numar $N$ şi doua siruri $A$ şi $B$ de câte $2N$ numere naturale. Să consideram o parantezare corectă de lungime $2N$ căreia vrem sa îi calculam costul. Pentru fiecare paranteza $i$, dacă e deschisă adăugam $A{~i~}$ iar dacă e închisa adaugăm $B{~i~}$. Găsiţi costul maxim al unei parantezări corecte!
O parantezare este corectă dacă este construită conform următoarelor reguli:
O parantezare este corectă daca este construită conform următoarelor reguli:
* $<şirul vid> = <parantezare corectă>$
* $<parantezare corectă> + <parantezare corectă> = <parantezare corectă>$
h2. Date de intrare
Fişierul de intrare $benzina.in$ (adică motivat.in) conţine numărul $N$ pe prima linie, şirul $A$ pe a doua linie şi şirul $B$ pe a treia linie. Un şir apare sub forma a $2 * N$ numere naturale mai mici ca $10^9^$ separate prin câte un spaţiu.
Fişierul de intrare $benzina.in$ (adica motivat.in) conţine numarul $N$ pe prima linie, sirul $A$ pe a doua linie şi şirul $B$ pe a treia linie. Un şir apare sub forma a $2N$ numere naturale mai mici ca $10^9^$ separate prin câte un spaţiu.
h2. Date de ieşire
În fişierul de ieşire $benzina.out$ (adica motivat.out) se va afla un singur număr, şi anume costul maxim al unei parantezări corecte.
În fişierul de ieşire $benzina.out$ (adica motivat.out) se va afla un singur numar, şi anume costul maxim al unei parantezari corecte.
h2. Subtaskuri
* $Subtask *Omul este o persoană umană* - 4 puncte (testele 1 şi 2): N ≤ 10$
* $Subtask *Să fie bine ca să nu fie rău* - 20 de puncte (testele 3-12): N ≤ 50$
* $Subtask *Am marcat goluri, aşa şi aşa, multe, dar nu prea multe* - 24 de puncte (testele 13-24): N ≤ 750$
* $Subtask *Noi... vedete; de la început până la sfârşit... nu pot să înţeleg ce s-a întâmplat* - 52 de puncte (testele 25-50): N ≤ 50.000$
* $Subtask *Omul este o persoană umană* - 4 puncte: N ≤ 10$
* $Subtask *Să fie bine ca să nu fie rău* - 20 de puncte: N ≤ 50$
* $Subtask *Am marcat goluri, aşa şi aşa, multe, dar nu prea multe* - 24 de puncte: N ≤ 750$
* $Subtask *Noi... vedete; de la început pana la sfârşit... nu pot sa înţeleg ce s-a intâmplat* - 52 de puncte: N ≤ 50.000$
h2. Exemplu
table(example). |_. benzina.in |_. benzina.out |
| 3
5 1 4 8 7 5
3 7 7 8 5 2
| 33 |
| 5
7 4 7 7 4 4 4 7 7 7
4 7 4 4 7 7 7 4 4 4
| 61 |
|ceva
| 33
|
h3. Explicaţie
Pentru primul exemplu, o parantezare optimă este $()()()$.
Pentru al doilea exemplu, câteva dintre parantezările optime sunt $(((()))())$, $(((())))()$ şi $()(()()())$.
...
== include(page="template/taskfooter" task_id="benzina") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.