InfoAs Atlas

<- Go back View preview

Problema Buldo

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

Dorești să nivelezi terenul pe care l-ai cumpărat, care are lățimea de `1` metru și lungimea de `N` metri, fiind alcătuit din `N` zone succesive, fiecare zonă având lungimea de `1` metru. Terenul se reprezintă ca un șir de `N` numere naturale `h1, h2, h3, …, hN` reprezentând înălțimile în metri pe care le au zonele din terenul inițial, privite de la stânga spre dreapta. 
 
Pentru a nivela terenul ai închiriat un buldozer care funcționează astfel. Se alege o înălțime `H` (număr natural) la care ridicăm lama buldozerului. Inițial buldozerul are pe lamă o cantitate `C = 0` metri cubi de pământ. Buldozerul începe să mergă de la stânga la dreapta și când ajunge la zona `i`, în funcție de înălțimea `hi` a acesteia, se va afla în una dintre următoarele situații:

* dacă `hi ≥ H` atunci cantitatea suplimentară `hi - H` se adaugă la `C` și nivelul zonei ajunge la `H`;
 * dacă `hi < H` atunci se scade din `C` diferența `H - hi` pentru a aduce nivelul zonei la nivelul `H`.

Remarcăm faptul că `H` trebuie ales inițial astfel încât de fiecare dată când buldozerul ajunge în a doua situație să aibă pe lamă suficient pământ (`C ≥ H - hi)`. După ce buldozerul parcurge cele `N` zone de lungime `1` pe lama buldozerului e posibil să mai rămână pământ, dar asta nu te interesează, pentru că la capătul din dreapta al terenului este un râu, și pământul rămas se va vărsa acolo.

## Cerință

Scrieți un program care calculează înălțimea maximă `H` la care poate fi ridicată lama, astfel încât terenul să poată fi nivelat la acea înălțime.
## Date de intrare

Fișierul de intrare `buldo.in` conține pe prima linie numărul natural `N`, iar pe a doua linie, separate prin câte un spațiu, cele `N` numere naturale `h1, h2, h3, …, hN`, cu semnificația din enunț.
## Date de ieșire

Fișierul de ieșire `buldo.out` va conține o singură linie, pe care va fi scris numărul natural `H` cerut. 
## Restricții și precizări

* `1 ≤ N ≤ 100.000`
 * Înălțimile sunt numere naturale, `1 ≤ hi ≤ 1.000.000.000`, pentru orice `i`, `1 ≤ i ≤ N`
 * Pentru teste în valoare de 50 de puncte, `N ≤ 1000``hi ≤ 1000`, pentru orice `i`, `1 ≤ i ≤ N`

Examples

[{"input": "4\n5 2 1 6", "output": "2", "explanation": "Dac\u0103 se fixeaz\u0103 lama la \u00een\u0103l\u021bimea <code>H = 2</code>, dup\u0103 ce se trece de zona <code>1</code> (primul metru pe lungime), aceast\u0103 zon\u0103 r\u0103m\u00e2ne la \u00een\u0103l\u021bimea <code>2</code> \u0219i <code>C = 3</code> metri cubi de p\u0103m\u00e2nt sunt du\u0219i de lam\u0103 la zona <code>2</code>. Acolo se vor ob\u021bine \u00een total <code>2 + 3 = 5</code> metri cubi de p\u0103m\u00e2nt, dar se p\u0103streaz\u0103 doar <code>2</code>, iar restul de <code>C = 3</code> se transport\u0103 la zona <code>3</code>. La zona <code>3</code> se vor ob\u021bine \u00een total <code>1 + 3 = 4</code> metri cubi de p\u0103m\u00e2nt, dar se p\u0103streaz\u0103 doar <code>2</code>, iar restul de <code>C = 2</code> se transport\u0103 la zona <code>4</code>. La zona <code>4</code> se vor ob\u021bine \u00een total <code>6 + 2 = 8</code> metri cubi de p\u0103m\u00e2nt, dar se p\u0103streaz\u0103 doar <code>2</code>, iar restul de <code>C = 6</code> se arunc\u0103 \u00een r\u00e2u. Dac\u0103 s-ar fixa lama la \u00een\u0103l\u021bimea <code>H = 3</code>, la zona <code>3</code> se poate ajunge doar la \u00een\u0103l\u021bimea <code>2</code> \u0219i \u00eencercarea e\u0219ueaz\u0103 (fiind o \u00een\u0103l\u021bime mai mic\u0103 dec\u00e2t cea propus\u0103).\r\n\r\n"}]

Default code

Summary

Editorial

Solution

Contributor ID

Author

Tags

Problem set

Chapter ID

Published At

Admin Approved

Difficulty

License

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	2 KB	View
0-buldo.in	/ 100	10 January 2025 21:26	23 B	View
0-buldo.ok	/ 100	10 January 2025 21:26	1 B	View
1-buldo.in	/ 100	10 January 2025 21:26	51 B	View
1-buldo.ok	/ 100	10 January 2025 21:26	1 B	View
2-buldo.in	/ 100	10 January 2025 21:26	63 B	View
2-buldo.ok	/ 100	10 January 2025 21:26	2 B	View
3-buldo.in	/ 100	10 January 2025 21:26	144 B	View
3-buldo.ok	/ 100	10 January 2025 21:26	2 B	View
4-buldo.in	/ 100	10 January 2025 21:26	299 B	View
4-buldo.ok	/ 100	10 January 2025 21:26	2 B	View
5-buldo.in	/ 100	10 January 2025 21:26	351 KB	View
5-buldo.ok	/ 100	10 January 2025 21:26	6 B	View
6-buldo.in	/ 100	10 January 2025 21:26	939 KB	View
6-buldo.ok	/ 100	10 January 2025 21:26	8 B	View
7-buldo.in	/ 100	10 January 2025 21:26	202 KB	View
7-buldo.ok	/ 100	10 January 2025 21:26	6 B	View
8-buldo.in	/ 100	10 January 2025 21:26	600 KB	View
8-buldo.ok	/ 100	10 January 2025 21:26	6 B	View
9-buldo.in	/ 100	10 January 2025 21:26	674 KB	View
9-buldo.ok	/ 100	10 January 2025 21:26	7 B	View
10-buldo.in	/ 100	10 January 2025 21:26	878 KB	View
10-buldo.ok	/ 100	10 January 2025 21:26	9 B	View
11-buldo.in	/ 100	10 January 2025 21:26	878 KB	View
11-buldo.ok	/ 100	10 January 2025 21:26	9 B	View
12-buldo.in	/ 100	10 January 2025 21:26	960 KB	View
12-buldo.ok	/ 100	10 January 2025 21:26	9 B	View
13-buldo.in	/ 100	10 January 2025 21:26	973 KB	View
13-buldo.ok	/ 100	10 January 2025 21:26	8 B	View
14-buldo.in	/ 100	10 January 2025 21:26	906 KB	View
14-buldo.ok	/ 100	10 January 2025 21:26	8 B	View
In total: 32 files 7 MB

View files grouped by their test cases.

Index	Input file	Output file	Score	Visibility

Enzo Judge

Offline

Server is offline.

Fernando Judge

Offline

Server is offline.

Main Instance

Offline

Server is offline.

Judge count: 2 Instance count: 1

Online judges will be synchronised with all the files. The previous version(s) of the problem will be overwritten.

Problema Buldo

Identification properties

Content properties

Technical properties

Delete all files