În Piatra Neamț sunt N+2 locații numerotate de la 0 la N+1, de la stânga la dreapta. Distanța dintre două locații i si j este egală cu |i – j|. La început, în locațiile 0 și N+1, sunt construite benzinării, și în celelalte locații sunt case. Compania BuildNT a decis sa construiască N benzinării, una în fața fiecărei case.

Înainte să construiască o benzinărie, constructorii calculează valoarea S egală cu suma distanțelor de la fiecare casă la cea mai apropiată benzinărie, si adaugă această sumă la suma totală T. După, ei aleg o casă, la cea mai mare distanță de orice benzinărie, în fața căreia construiesc o nouă benzinărie. Casele sunt alese în așa fel încât, după construirea benzinăriilor, valoarea S recalculată sa fie minimă. Dacă sunt mai multe case ce respectă această regulă, se alege prima din stânga.
Desigur, după ce toate benzinăriile au fost construite, suma S va deveni 0 și suma totală T nu se va mai schimba.

Cerința

Calculați T pentru o valoare dată N.

Date de intrare

Prima linie conține doar un număr N – numărul de case.

Date de ieșire

Scrieți un singur număr – suma totală T după ce toate cele N benzinării au fost construite.

Restricții și precizări

1 ≤ N ≤ 1 000 000 000
Pentru 30% din cazuri N ≤ 10 000
Pentru alte 30% din cazuri N ≤ 1 000 000

Exemplu

Intrare

Ieșire

Explicație

In tabelul de mai jos este explicația pentru calcularea T când N=12.
Prima coloană conține distanța de la fiecare locație (incluzând locațiile 0 și N+1=13) la cele mai apropiate benzinării.

Distante pentru toate locațiile S T Locația unde se construiește o benzinărie
0 1 2 3 4 5 6 6 5 4 3 2 1 0 42 42 6
0 1 2 3 2 1 0 1 2 3 3 2 1 0 21 63 9
0 1 2 3 2 1 0 1 1 0 1 2 1 0 15 78 3
0 1 1 0 1 1 0 1 1 0 1 2 1 0 10 88 11
0 1 1 0 1 1 0 1 1 0 1 0 1 0 8 96 1
0 0 1 0 1 1 0 1 1 0 1 0 1 0 7 103 2
0 0 0 0 1 1 0 1 1 0 1 0 1 0 6 109 4
0 0 0 0 0 1 0 1 1 0 1 0 1 0 5 114 5
0 0 0 0 0 0 0 1 1 0 1 0 1 0 4 118 7
0 0 0 0 0 0 0 0 1 0 1 0 1 0 3 121 8
0 0 0 0 0 0 0 0 0 0 1 0 1 0 2 123 10
0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 124 12
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 124 Sfârșit

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 Benzinarii1:

#include <bits/stdc++.h>
#define Int long long
using namespace std;
queue<pair<Int,Int>> q;
Int n,x,s,r,sol;
inline Int val(Int L)
{
    return (L*L+2*L+L%2)/4;
}
inline Int progresion_sum(Int a1,Int r,Int n)
{
    return n*(2*a1+(n-1)*r)/2;
}
inline void updateQueue(Int x,Int n)
{
    if(x==0)return;
    if(q.back().first==x)
        q.back().second+=n;
    else
        q.push(make_pair(x,n));
}
int main()
{
    cin>>n;
    q.push(make_pair(n,1));
    s=val(n);
    for(;q.size();q.pop())
    {
        tie(x,n)=q.front();
        r=val(x)-val(x/2)-val(x-x/2-1);
        sol+=n*(2*s-(n-1)*r)/2;
        s-=n*r;
        updateQueue(x/2,n);
        updateQueue(x-x/2-1,n);
    }
    cout<<sol;
    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 #2537 Benzinarii1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2537 Benzinarii1 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 #2537 Benzinarii1