Diferente pentru problema/collar intre reviziile #2 si #12

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="collar") ==
Poveste şi cerinţă...
Tassadar a descoperit un colier Xel’Naga format din $N$ diamante, fiecare diamant $i$ având asociat un număr de carate $V{~i~}$. Puterea magică oferită de un colier este $max(V{~i~}, 1 ≤ i ≤ N) – min(V{~i~}, 1 ≤ i ≤ N)$. El vrea să împartă colierul în mai multe coliere de lungimi *egale*, astfel încat să fie respectate următoarele condiţii:
 
* fiecare colier nou să reprezinte o subsecvenţă a colierului iniţial
* fiecare perlă din colierul iniţial să facă parte din exact un colier nou
* suma puterilor oferite de colierele noi să fie maximă
 
 
Deoarece Tassadar nu este un bijutier prea iscusit, vă roagă pe voi să-i spuneţi care este puterea maximă pe care o poate obţine printr-o împărţire a colierului.
h2. Date de intrare
Fişierul de intrare $collar.in$ conţine pe prima linie numărul natural $N$ cu semnificaţia din enunţ. Pe linia următoare se află $N$ numere întregi $V{~i~}$ reprezentând frumuseţea fiecărei perle.
Fişierul de intrare $collar.in$ conţine pe prima linie numărul natural $N$ cu semnificaţia din enunţ. Pe linia următoare se află $N$ numere întregi $V{~i~}$ reprezentând numărul de carate pentru fiecare diamant.
h2. Date de ieşire
În fişierul de ieşire $collar.out$ veţi afişa un singur număr, reprezentând frumuseţea maximă pe care o poate obţine Tassadar prin împărţirea colierului.
În fişierul de ieşire $collar.out$ veţi afişa un singur număr, reprezentând suma maximă a puterilor pe care o poate obţine Tassadar prin împărţirea colierului.
h2. Restricţii
* $1 ≤ N ≤ 50.000$
* $1 ≤ N ≤ 65.536$
* $-1.000.000.000 ≤ V{~i~} ≤ 1.000.000.000$
* Colierul iniţial este circular
* Vă recomandăm să folosiţi numere întregi pe 64 de biţi cu semn
h2. Exemplu
table(example). |_. collar.in |_. collar.out |
| 6
1 4 2 3 1 2
4 2 3 1 2 1
| 5
|
h3. Explicaţie
Împărţim şirul în subsecvenţele [1, 4, 2] şi [3, 1, 2]. O altă împărţire validă este [1, 4] [2, 3] [1, 2].
Împărţim şirul în subsecvenţele $[1, 4, 2]$ şi $[3, 1, 2]$. O altă împărţire validă este $[1, 4]$ $[2, 3]$ $[1, 2]$ (putem considera aceste îmărţiri, deoarece colierul iniţial este circular).
== include(page="template/taskfooter" task_id="collar") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
9614