K1

k1

== include(page="template/taskheader" task_id="k1") ==

Pentru a diminua efectele crizei economice prin creşterea numărului de telespectatori (şi implicit a veniturilor provenite din publicitate), redacţia „Şocuri şi concursuri” a unei televiziuni selecte a decis să organizeze un turneu de lupte K1. La acesta vor lua parte $N$ sportivi. Fiecare dintre aceştia are un rating, calculat pe baza rezultatelor sale anterioare. Suma de bani pe care o primeşte pentru fiecare luptă la care va lua parte este egală cu acest rating. În urma fiecărei lupte rating-ul învingătorului creşte cu valoarea rating-ului învinsului.
 
h2. Cerinta
 
Cum televiziunea îşi doreşte un profit cât mai mare, conducătorii acesteia doresc să programeze meciurile astfel încât să plătească luptătorilor o sumă totală cât mai mică. Ştiind că nu există lupte încheiate la egalitate şi că turneul se termină doar după ce a fost stabilit un învingător, stabiliţi care este suma totală minimă pe care o pot plăti organizatorii. Suma totală plătită de televiziune este obţinută prin adunarea sumelor plătite tuturor luptătorilor pe parcursul turneului.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $k1.in$ conţine pe prima linie o valoare $N$, reprezentând numărul de luptători invitaţi la turneu, iar pe următoarele $N$ linii se află câte un număr natural nenul $x${~i~}, reprezentând rating-ul iniţial al celui de-al $i$-lea luptător.

Fişierul de intrare $k1.in$ ...

h2. Date de ieşire

Fişierul de ieşire $k1.out$ conţine un singur număr natural $s$, reprezentând suma totală minimă pe care o poate plăti televiziunea luptătorilor.

În fişierul de ieşire $k1.out$ ...

h2. Restricţii

* $0 < N &le; 1 000 000$
* $1 &le; x{~i~} &le; 10 000$ pentru orice $i$ numar natural cu proprietatea $1 &le; i &le; N$

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. k1.in |_. k1.out |

| 3
1
1
1
| 5 |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţie

La prima luptă participă $2$ sportivi având fiecare rating-ul $1$. În ultimul meci se vor întâlni un luptător cu rating-ul $2$ (învingătorul primului meci) şi altul cu rating $1$ (cel care nu a participat la prima luptă). Învingătorul primului meci primeşte în total $3$ ({$1$} pentru prima luptă şi $2$ pentru cea de a doua), cel care a pierdut prima luptă şi cel care a participat doar la ultima primesc câte $1$, deci televiziunea va plăti în total $5$.

...

== include(page="template/taskfooter" task_id="k1") ==

4153