| Fişierul intrare/ieşire: | silvania.in, silvania.out | Sursă | Algoritmiada 2019 Runda Finala |
| Autor | Adrian Budau, Eugenie Daniel Posdarascu | Adăugată de |  Adrian Budau •freak93 |
| Timp execuţie pe test | 0.8 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Silvania
Silvania, in latina, inseamna "zona impadurita". Problema aceasta este despre paduri
Bogdi din Silvania, taietorul de lemne, a dat-o pe ecologie. El a decis sa inconjoare padurea cu un gard, ca alti taietori de lemne sa nu o mai atace -- dar nestiind cum sa faca orice in afara de a taia lemne, gardul va fi construit din lemnul padurii.
Padurea din Silvania este formata de un numar de arbori, fiecare cu o anumita cantitate de lemn, pusi in linie, la diverse pozitii. Bogdi poate taia orice submultime de arbori, si din acest act strange o cantitate de lemn egal cu suma cantitatilor de lemn ale arborilor taiati. Bogdi vrea neaparat ca, dupa aceasta taiere, sa aiba suficient lemn pentru a inconjura restul arborilor cu un singur gard -- adica sa aiba o cantitate de lemn mai mare sau egala cu distanta dintre primul si ultimul arbore ramas netaiat. Ajutati-l sa gaseasca numarul minim de arbori pe care trebuie sa ii taie.
Date de intrare
Fişierul de intrare silvania.in va contine, pe primul rand, numarul N de teste.
Urmeaza N numere pe urmatorul rand, cantitatile de lemn ale arborilor.
Urmeaza N numere pe urmatorul rand, pozitiile arborilor.
Date de ieşire
În fişierul de ieşire silvania.out se va afisa un singur numar natural, numarul minim de arbori ce trebuie taiati.
Restricţii
- 1 ≤ N ≤ 5.000
- 1 ≤ cantitatea de lemn a unui arbore ≤ 1.000.000.000
- 1 ≤ pozitia unui arbore ≤ 1.000.000.000
- Pozitiile arborilor sunt distincte
- Pentru teste in valoare de 10 puncte 1 ≤ N ≤ 100
- Pentru teste in valoare de inca 30 de puncte 1 ≤ N ≤ 1.000
- Fiecare din aceste subtask-uri (cele 2 de mai sus, si cel in valoare de 60 de puncte cu 1 ≤ N ≤ 5.000) este impartit in 2 subtask-uri mai mici.
- Prima jumatate din punctajul pe subtask este pentru teste in care fiecare copac este unic. Mai exact, nu se gasesc doi copaci diferiti care au exact aceeasi cantitate de lemn.
- A doua jumatate din punctajul pe subtask este pentru teste care nu mai au nico restritie suplimentara.
Exemplu
| silvania.in | silvania.out |
|---|---|
| 5 2 3 2 1 2 4 5 1 3 10 | 2 |
Explicaţie
Exista mai multe modalitati de a taia copacii si a construi gardul. Una din ele:
- Se taie al doilea copac (pentru a obtine 3 lemn) si ultimul copac (pentru inca 2 lemn).
- Se construieste gard de la pozitia 1 la pozitia3 4.
