InfoAs Atlas

<- Go back View preview

Problema Cofetarie

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

Carolina _adoooră_ tot ce este dulce, astfel că vizitează des cofetăria din oraș. Din vitrină se văd `n` prăjituri așezate în linie, de toate tipurile: de la amandine, la eclere și savarine. Pentru fiecare prăjitură în parte se cunoaște un scor, care reprezintă cât de dulce este prăjitura. Astfel, prăjitura cu numărul `i` are scorul `ai`, pentru `1 ≤ i ≤ n`. 
 
Cum Carolina vine foarte des, și-a creat propriul ritual de alegere a prăjiturilor: ea va cumpăra prăjiturile aflate pe poziții consecutive (`i`, `i + 1`, `i + 2`, …, `j`, cu `i < j`) care au valoarea `max(ai, ai + 1, …, aj) × min(ai, ai + 1, …, aj)` maximă.

## Cerință

Știind scorul celor `n` prăjituri din vitrină, să se afișeze maximul valorilor tuturor secvențelor de prăjituri consecutive.
## Date de intrare

În fișierul de intrare `cofetarie.in`, pe prima linie se află numărul natural `n`, iar pe următoarea linie se află scorurile celor `n` prăjituri, separate prin câte un spațiu, a `i`-a valoare reprezentând `ai`.
## Date de ieșire

În fișierul de ieșire `cofetarie.out` se va afișa maximul valorilor tuturor secvențelor de prăjituri consecutive.
## Restricții și precizări

* `1 ≤ n ≤ 100.000`
 * `1 ≤ ai ≤ 1.000.000`, pentru `1 ≤ i ≤ n`
 * Secvențele de prăjituri consecutive trebuie să aibă lungimea minimă de `2`

Examples

[{"input": "5\n1 2 3 4 5", "output": "20", "explanation": "Valorile secven\u021belor de pr\u0103jituri consecutive sunt:\r\n<ol type=1>\r\n<li>Secven\u021ba <code>(1, 2)</code> are valoarea <code>1 × 2 = 2</code>;</li>\r\n<li>Secven\u021ba <code>(2, 3)</code> are valoarea <code>2 × 3 = 6</code>;</li>\r\n<li>Secven\u021ba <code>(3, 4)</code> are valoarea <code>3 × 4 = 12</code>;</li>\r\n<li>Secven\u021ba <code>(4, 5)</code> are valoarea <code>4 × 5 = 20</code>;</li>\r\n<li>Secven\u021ba <code>(1, 3)</code> are valoarea <code>1 × 3 = 3</code>;</li>\r\n<li>Secven\u021ba <code>(2, 4)</code> are valoarea <code>2 × 4 = 8</code>;</li>\r\n<li>Secven\u021ba <code>(3, 5)</code> are valoarea <code>3 × 5 = 15</code>;</li>\r\n<li>Secven\u021ba <code>(1, 4)</code> are valoarea <code>1 × 4 = 4</code>;</li>\r\n<li>Secven\u021ba <code>(2, 5)</code> are valoarea <code>2 × 5 = 10</code>;</li>\r\n<li>Secven\u021ba <code>(1, 5)</code> are valoarea <code>1 × 5 = 5</code>.</li>\r\n</ol>\r\nMaximul acestora este <code>20</code>, pentru secven\u021ba <code>(4, 5)</code>."}]

Default code

Summary

Editorial

Această problemă este mai mult de logică decât de tehnică. Se poate demonstra că intervalul răspuns este de lungime `2`. Vom demonstra acest lucru prin reducere la absurd.

Să presupunem că intervalul răspuns (adică cu produsul minimului și a maximului maximă posibil) este de lungime minim `3`: avem porțiunea `ai, ai + 1, …, aj`, cu `i + 1 < j` (pentru lungimea minim `3`). Înseamnă că avem doi indici, `kmin` și `kmax`, cu `i ≤ kmin, kmax ≤ j`, pentru care `akmin` este minimul intervalului, iar `akmax` este maximul intervalului. Observăm că intervalul delimitat de `kmin` și `kmax` (care are lungimea cel mult egală cu lungimea intervalului inițial delimitat de `i` și `j`), are aceeași valoare ca și intervalul delimitat de `i` și `j`, așadar putem să reducem intervalul la `kmin` și `kmax`. Dacă între `kmin` și `kmax` se află valori, înseamnă că acestea clar o să fie mai mari decât `akmin` (pentru că `akmin` este minimul). Asta înseamnă că dacă am reduce intervalul ca să nu includem `akmin`, am avea un alt minim mai mare decât `akmin`, așadar am găsit un interval mai mare ca valoare, prin urmare, intervalul delimitat de `i` și `j` nu este cel răspuns. În schimb, dacă intervalul ar avea lungimea `2` (pentru că `1` nu se poate), nu putem să scoatem nici `akmax` (deoarece ne vom micșora scorul) și nici `akmin` (deoarece am avea un interval de lungime `1`, ceea ce nu se poate).

Prin urmare, deși pot exista mai multe intervale răspuns, se garantează că minim un interval răspuns are lungimea `2`. Vom parcurge liniar vectorul, luând perechile de elemente consecutive, înmulțindu-le și contorizând valoarea maximă, pe care o afișăm la final. Complexitatea soluției este `O(n)`.

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	1 KB	View
0-cofetarie.in	/ 100	10 January 2025 21:26	11 B	View
0-cofetarie.ok	/ 100	10 January 2025 21:26	2 B	View
1-cofetarie.in	/ 100	10 January 2025 21:26	394 B	View
1-cofetarie.ok	/ 100	10 January 2025 21:26	6 B	View
2-cofetarie.in	/ 100	10 January 2025 21:26	3 KB	View
2-cofetarie.ok	/ 100	10 January 2025 21:26	6 B	View
3-cofetarie.in	/ 100	10 January 2025 21:26	38 KB	View
3-cofetarie.ok	/ 100	10 January 2025 21:26	6 B	View
4-cofetarie.in	/ 100	10 January 2025 21:26	380 KB	View
4-cofetarie.ok	/ 100	10 January 2025 21:26	6 B	View
5-cofetarie.in	/ 100	10 January 2025 21:26	477 KB	View
5-cofetarie.ok	/ 100	10 January 2025 21:26	8 B	View
6-cofetarie.in	/ 100	10 January 2025 21:26	477 KB	View
6-cofetarie.ok	/ 100	10 January 2025 21:26	8 B	View
7-cofetarie.in	/ 100	10 January 2025 21:26	575 KB	View
7-cofetarie.ok	/ 100	10 January 2025 21:26	10 B	View
8-cofetarie.in	/ 100	10 January 2025 21:26	672 KB	View
8-cofetarie.ok	/ 100	10 January 2025 21:26	12 B	View
9-cofetarie.in	/ 100	10 January 2025 21:26	672 KB	View
9-cofetarie.ok	/ 100	10 January 2025 21:26	12 B	View
In total: 22 files 3 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 Cofetarie

Identification properties

Content properties

Technical properties

Delete all files