Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | zlego.in, zlego.out | Sursă | ONI 2012 - clasele 11-12 |
| Autor | Andrei Parvu | Adăugată de |  Simoiu Robert •SpiderMan |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Zlego
Recent, Bujorel a dat în mintea copiilor şi s-a apucat să se joace cu piese de zlego. El are o piesă formată din N bucăţi numerotate de la 1 la N, fiecare cu o înalţime şi un coeficient de frumuseţe date. Se defineşte un zprefix ca fiind un şir format din una sau mai multe bucăţi consecutive care să înceapă cu piesa 1. Scopul este să aleagă un zprefix, să găsească toate apariţiile acestuia în restul piesei şi să facă suma costurilor de frumuseţe ale acestor apariţii. Pentru o apariţie a zprefixului ales care corespunde secvenţei formate din bucăţile numerotate de la i la j (înălţimea bucăţii 1 este egală cu înălţimea bucăţii i, înălţimea bucăţii 2 este egală cu înălţimea bucăţii i+1 etc.) costul său de frumuseţe este coeficientul de frumuseţe al ultimei bucăţi, adică al lui j.
Bujorel e curios ce se întamplă pentru orice zprefix şi vrea să afişeze suma costurilor de frumuseţe ale tuturor apariţiilor fiecarui zprefix.
Date de intrare
Pe prima linie a fisierului zlego.in se află numarul de teste T. Fiecare test are următorul format: pe prima linie un număr natural N reprezentând dimensiunea piesei de zlego, pe următoarea linie se află N numere întregi, reprezentând înălţimile pieselor, despărţite prin câte un spaţiu, iar pe cea de-a treia linie se află tot N numere întregi, despărţite prin câte un spaţiu, cel de-al i-lea număr reprezentând coeficientul de frumuseţe a celei de-a i-a piese.
Date de ieşire
Fişierul zlego.out trebuie să conţină, pentru fiecare din cele T teste, câte N linii, cea de-a i-a linie reprezentând suma costurilor de frumuseţe ale apariţiilor zprefixului [1, i].
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| zlego.in | zlego.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
