Diferențe pentru problema/asasin între reviziile #18 si #32

Nu există diferențe între titluri.

Diferențe între conținut:

Avantajul sau este ca acestia parcurg orasul intr-un sir indian, unul in spatele celuilalt.
In dezavantajul sau, insa, in grupul templierilor se afla si garzi de corp si cetateni obisnuiti. Ezio va aplica o tactica de jefuire atipica - isi va alege o tinta initiala, iar apoi va parcurge sirul de oameni, jefuindu-i succesiv. Asasinul hot poate abandona oricand sirul pentru a se reintoarce la o tinta aflata in fata ultimului om jefuit, dar aceasta manevra grabita il va costa toate castigurile pe care le obtinuse pana atunci; asa ca Ezio va trebui sa estimeze care este cea mai lunga insiruire de persoane care pot fi jefuite succesiv pentru un castig maxim. O alta problema o reprezinta garzile de corp, pe care Ezio trebuie sa le mituiasca din banii acumulati pentru a nu il aresta. Se stie ca garzile de corp sunt profitoare si cer drept mita exact suma de bani pe care acestea o detin deja.
In dezavantajul sau, insa, in grupul templierilor se afla si garzi de corp si cetateni obisnuiti. Ezio va aplica o tactica de jefuire atipica - isi va alege o tinta initiala, iar apoi va parcurge sirul de oameni, jefuindu-i succesiv. Asa ca Ezio va trebui sa estimeze care este cea mai lunga insiruire de persoane care pot fi jefuite succesiv pentru un castig maxim. O alta problema o reprezinta garzile de corp, pe care Ezio trebuie sa le mituiasca din banii acumulati pentru a nu il aresta. Se stie ca garzile de corp sunt profitoare si cer drept mita exact suma de bani pe care acestea o detin deja.
Dupa cum bine stiti, programarea nu era tocmai in voga in secolul XV, asa ca Ezio are nevoie de ajutorul vostru - daca va afla castigul maxim pe care il poate obtine, pozitia din sir a primei tinte cat si numarul de oameni jefuiti, eroul nostru va putea avea suficienti bani pentru a se intoarce in Florenta.
Se dau [$N$], numarul de oameni care participa la carnaval, asezati in sir indian; $N$ numere naturale $v[i]$, reprezentand suma de bani pe care ii are omul de pe pozitia [$i$]; $N$ valori $t[i]$ de tipul -1, 0, sau 1, reprezentand tipul omului de pe pozitia $i$ astfel:
* Daca $t[i] = -1$, omul de pe pozitia $i$ este gardian, deci Ezio va trebui sa il mituiasca pe acesta.
* Daca $t[i] = 0$, omul de pe pozitia $i$ este templier, deci Ezio il va jefui.
* Daca $t[i] = 1$, omul de pe pozitia $i$ este un simplu cetatean, Ezio neavand ce sa fure de la acesta.
* Daca $t[i] = 1$, omul de pe pozitia $i$ este templier, deci Ezio il va jefui.
* Daca $t[i] = 0$, omul de pe pozitia $i$ este un simplu cetatean, Ezio fiind prea orgolios sa fure de la un om de rand.
h2. Date de intrare
h2. Restricții
* $1 ≤ N ≤ 100000$
* $0 ≤ v[i] ≤ 1000, 1 ≤ i ≤ N$
* Daca Ezio jefuieste un templier, acesta ii fura toti banii pe care templierul ii are asupra sa.
* Daca exista mai multe solutii in care castigul este maxim, se va afisa aceea in care pozitia primei tinte este minima.
* Daca exista mai multe solutii de castig maxim in care pozitia primei tinte este aceeasi, se va afisa solutia care are numarul de oameni cu care Ezio intra in contact minim.
* $1 ≤ v[i] ≤ 1000, 1 ≤ i ≤ N$
* $Daca exista mai multe solutii in care castigul este maxim, se va afisa aceea in care pozitia primei tinte este minima.$
* $Daca exista mai multe solutii de castig maxim in care pozitia primei tinte este aceeasi, se va afisa solutia in care numarul de oameni cu care Ezio intra in contact este minim.$
* $Daca Ezio jefuieste un templier, acesta ii fura toti banii pe care templierul ii are asupra sa.$
* $Ezio va incerca intotdeauna sa jefuiasca cel putin un om!$
* $Suma de bani obtinuta de Ezio in calatoria sa poate ajunge oricand pe minus.$
h2. Exemplu
table(example).
|_. asasin.in |_. asasin.out |
| 6
1 -1 4 -3 4 -1
| 5 1 5
| 8
1 1
1 -1
4 1
2 0
3 -1
1 0
4 1
1 -1
| 5 1 7
|
h3. Explicație
Optim pentru asasinul nostru este sa parcurga fie sirul oamenilor $3, 4, 5$, fie $1, 2, 3, 4, 5$, in ambele situatii suma obtinuta fiind [$5$]. Avand in vedere ca pozitia de inceput a primului sir este [$3$], iar pozitia de inceput a celui de-al doilea sir este [$1$], solutia afisata va fi cea de-a doua.
Optim pentru asasinul nostru este sa parcurga fie sirul oamenilor $3, 4, 5, 6, 7$, fie $1, 2, 3, 4, 5, 6, 7$, in ambele situatii suma obtinuta fiind [$5$]. Avand in vedere ca pozitia de inceput a primului sir este [$3$], iar pozitia de inceput a celui de-al doilea sir este [$1$], solutia afisata va fi cea de-a doua.
== include(page="template/taskfooter" task_id="asasin") ==

Nu există diferențe între securitate.