Atenție! Aceasta este o versiune veche a paginii., scrisă la 2012-12-11 19:22:23.
Revizia anterioară   Revizia următoare  

Fișierul intrare/ieșire asasin.in, asasin.out Sursă ad-hoc
Autor Mihai-Alexandru Dușmanu | Teodor Plop Adăugată de avatar teodor94 Teodor Plop teodor94
Timp de execuție pe test 0.1 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Assassin's Creed

Celebrul asasin Ezio Auditore a avut o peripetie putin comica – plecat in Venetia, furat de privelistile splendide ale orasului a uitat sa ii dea de mancare calului sau, Pol, asa ca acesta s-a suparat si l-a abandonat. Desigur, Ezio este mai presus de a parcurge drumul spre orasul sau natal, Florenta, pe jos, dar pentru a inchiria o trasura are nevoie de bani.

Norocul face ca tocmai atunci, cu ocazia carnavalului, un grup de templieri trecea prin oras. Cum asasinii sunt dusmanii de moarte ai templierilor, Ezio a decis ca va putea sa isi cumpere o trasura furand pungutele cu bani ale acestora.

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.

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.

Date de intrare

Fișierul de intrare asasin.in va contine pe prima linie numarul natural N. Pe urmatoarele N linii se vor afla v[i] si t[i], cu semnificatia din enunt.

Date de ieșire

În fișierul de ieșire asasin.out se vor gasi 3 valori, reprezentand castig maxim pe care il poate obtine Ezio, pozitia primei tinte si numarul de oameni cu care intra acesta in contact in timpul jafului.

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.

Exemplu

asasin.in asasin.out
This is some
text written on
multiple lines.
This is another
text written on
multiple lines.

Explicație

...

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 1 categorii