| Fişierul intrare/ieşire: | takara.in, takara.out | Sursă | ONI 2019, baraj |
| Autor | Costin Oncescu | Adăugată de |  Tinca Matei •TincaMatei |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Takara
Legenda spune că, acum mult timp, în oraşul Suceava ar fi fost îngropată o comoară de o valoare infinită. Fascinat de această teorie, ai decis să îţi încerci şi tu norocul.
Din fericire, amatorii de arheologie de pe site-urile de socializare au propus o listă de N locaţii populare pentru îngroparea comorilor, toate fiind plasate în linie, de-a lungul plaiurilor Sucevei. Mai mult, ai găsit pe internet o aplicaţie de detectat comori profesională, a cărei radar pretinde să aibă o putere infinită de detectare şi în care poate fi inclusiv setată comoara care se caută!
Problema este că această aplicaţie consumă bateria telefonului, iar tu îţi doreşti să fii econom, aşa că ai decis să nu menţii telefonul aprins încontinuu, ci să îl aprinzi doar în diferite locaţii posibile. Astfel, tu poţi alege să mergi către o locaţie şi să îl aprinzi. Aplicaţia va spune dacă în acel loc este comoara, sau, în caz contrar, îţi va arăta direcţia către aceasta. Această direcţie poate fi spre dreapta sau spre stânga, în funcţie de locaţia adevărată a comorii.
Din păcate, din cauza descărcărilor electrostatice din aer, în funcţie de locul în care decizi să decizi să detectezi comoara, aplicaţia poate necesita mai mult timp de calibrare, astfel consumând mai multă baterie. Mai exact, pentru a aprinde detectorul în locaţia i, vei consuma Ci unităţi de baterie. Tu nu ştii unde este îngropată comoara, de aceea vrei să te asiguri că telefonul nu va rămâne fără baterie. Tu nu ştii unde este îngropată comoara, de aceea vrei să te asiguri că telefonul nu va rămâne fără baterie fără să găseşti comoara, oriunde ar fi aceasta îngropată.
Cerinţă
Dându-se numărul de unităţi de baterie consumate pentru fiecare dintre cele N locaţii, care este numărul minim de unităţi de baterie de care vei avea nevoie, astfel încât să găseşti cu siguranţă comoara folosind detectorul, oriunde s-ar afla, înainte ca telefonul să rămână fără baterie?
Date de intrare
Pe prima linie a fişierului de intrare takara.in se află un număr întreg pozitiv N, reprezentând numărul de locaţii posibile. Pe a doua linie se află N numere întregi pozitive Ci, separate prin spaţii, cu semnificaţiile din enunţ.
Date de ieşire
Pe prima linie a fişierului de ieşire takara.out se va afla un singur număr întreg pozitiv, reprezentând numărul minim de unităţi de baterie necesar pentru a afla locaţia comorii, oriunde s-ar afla aceasta.
Restricţii
- 1 ≤ N ≤ 5.000
- 1 ≤ Ci ≤ 200.000
- Pentru teste în valoare de 15 puncte, 1 ≤ N ≤ 500
- Pentru alte teste în valoare de 55 de puncte, 1 ≤ N ≤ 2.000
Exemplu
| takara.in | takara.out |
|---|---|
| 4 10 1 5 2 | 3 |
| 6 73 33 44 25 6 70 | 58 |
| 9 91 35 21 55 30 45 53 29 91 | 96 |
| 20 18 32 37 17 22 13 3 35 20 30 37 32 10 23 9 5 27 36 27 22 | 65 |
Explicaţie
În primul exemplu, începi prin a verifica locaţia 2, consumând o unitate de baterie. Dacă aplicaţia te va direcţiona spre stânga, vei şti că locaţia comorii este 1. Dacă te va direcţiona spre dreapta, vei verifica locaţia 4, consumând încă două unităţi. După aceasta, vei şti sigur unde se află comoara.
