Fișierul intrare/ieșire | asasin.in, asasin.out | Sursă | ad-hoc |
---|---|---|---|
Autor | Mihai-Alexandru Dușmanu | Teodor Plop | Adăugată de | Teodor Plop • teodor94 |
Timp de execuție pe test | 0.1 sec | Limită de memorie | 2048 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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. 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] = 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.
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
- 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.
Exemplu
asasin.in | asasin.out |
---|---|
8 1 1 1 -1 4 1 2 0 3 -1 1 0 4 1 1 -1 |
5 1 7 |
Explicație
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.