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.

Cerința

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 x[i], 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 va conține pe prima linie un singur număr natural s, reprezentând suma totală minimă pe care o poate plăti televiziunea luptătorilor.

Restricții și precizări

0 < N ≤ 1 000 000
1 ≤ xi ≤ 10 000 pentru orice i număr natural cu proprietatea 1 ≤ i ≤ N

Exemplu

k1.in

k1.out

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema K1:

#include<cstdio>
#include<ctime>

using namespace std;

const int N=1000000;
const int MAX=10001;
const long long oo=(long long)1<<40;

long long q[N],r[N];
int pq,pr=0,uq,ur=0;

void citire()
{
    int x,n;
    scanf("%d",&n);
    while(scanf("%d",&x)!=EOF)
        q[uq++]=(long long)x;
}

inline long long minim(long long a,long long b,long long c,long long d)
{
    long long m=a+b;
    if(a+c<m)
        m=a+c;
    if(c+d<m)
        m=c+d;
    return m;
}

long long suma()
{
    long long s=0,aq,bq,ar,br,m;
    while(uq-pq+ur-pr>1)
    {
        if(pq<uq)
            aq=q[pq];
        else
            aq=oo;
        if(pq+1<uq)
            bq=q[pq+1];
        else
            bq=oo;
        if(pr<ur)
            ar=r[pr];
        else
            ar=oo;
        if(pr+1<ur)
            br=r[pr+1];
        else
            br=oo;
        m=minim(aq,bq,ar,br);
        s+=m;
        r[ur++]=m;
        if(m==aq+bq)
        {
            pq+=2;
            continue;
        }
        if(m==aq+ar)
        {
            ++pq;
            ++pr;
            continue;
        }
        if(m==ar+br)
        {
            pr+=2;
            continue;
        }
    }
    return s;
}

void sortare()
{
    int nr[MAX]={0},i;
    for(i=0;i<uq;++i)
        ++nr[q[i]];
    for(i=1,uq=0 ; i<MAX ; ++i)
        while(nr[i]--)
            q[uq++]=i;
}

int main()
{
    freopen("k1.in","r",stdin);
    freopen("k1.out","w",stdout);
    citire();
    sortare();
    printf("%lld
",suma());
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #745 K1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #745 K1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #745 K1