Fişierul intrare/ieşire:k1.in, k1.outSursăLot Juniori 2009 - Baraj 3
AutorVictor ManzAdăugată deCezarMocanCezar Mocan CezarMocan
Timp execuţie pe test0.4 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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.

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.

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 xi, reprezentând rating-ul iniţial al celui de-al i-lea luptător.

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.

Restricţii

  • 0 < N ≤ 1 000 000
  • 1 ≤ xi ≤ 10 000 pentru orice i numar natural cu proprietatea 1 ≤ i ≤ N

Exemplu

k1.ink1.out
3
1
1
1
5

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content