tactica

Pentru a fi cât mai eficienți în blocarea atacurilor echipei adverse, antrenorul și-a instruit cei $N$ jucători să se regrupeze într-o zonă de teren, de lungime exact $L$. Considerăm că terenul de joc este axa $Ox$, iar poziția curentă a fiecărui jucător este un număr natural. Considerăm, în plus, că jucătorii sunt numerotați de la $1$ la $N$, în ordinea crescătoare a pozițiilor lor pe axa $Ox$.

Costul deplasării unui jucător $i$ ($1 \leq i \leq N$) de la poziția sa $x_i$ la o poziție $y$ este $|x_i - y|$. Costul regrupării este suma costurilor deplasărilor tuturor jucătorilor. La finalul regrupării, distanța dintre cel mai din stânga și cel mai din dreapta jucător din zonă trebuie să fie exact $L$.

Cerință

Să se determine costul minim posibil al unei regrupări.

Interacțiune

Programul nu va citi date de la intrare și nu va face afișări. Concurentul trebuie să implementeze funcția:

long long solve(int N, int L);

Funcția primește ca parametri valorile lui $N$ și $L$ și trebuie să returneze costul total minim cu care toți cei $N$ jucători pot fi aduși în aceeași zonă compactă de lungime exact $L$.

Funcția solve() poate apela următoarele funcții:

• int getX(int i) - returnează poziția la care se află inițial jucătorul $i$
• int getNumber(int x1, int x2); returnează numărul de jucători care au poziția cuprinsă în intervalul de valori $[x_1, x_2]$
• long long getSumX(int x1, int x2); returnează suma pozițiilor jucătorilor care au poziția cuprinsă în intervalul de valori $[x_1, x_2]$

Concurentul va trebui să trimită un fișier cu structura:

#include "problem.h"

long long solve(int N, int L) {
    ...
}

Restricții și precizări

• $2 \leq N \leq 10^6$
• $1 \leq L \leq 10^9$
• $1 \leq x_i \leq 10^9$, pentru $1 \leq i \leq N$
• Pozițiile inițiale ale jucătorilor sunt distincte, dar în zona de lungime $L$ este permis să ajungă doi sau mai mulți jucători în aceeași poziție.

Modalitate de punctare

Notăm cu $A$ numărul total cumulat de apeluri ale funcțiilor de mai sus.

• dacă $A \leq 100$ se obține întreg punctajul pentru acel test;
• altfel dacă $A \leq 150$ se obține $0.8$ din punctajul alocat acelui test;
• altfel dacă $A \leq 250$ se obține $0.6$ din punctajul alocat acelui test;
• altfel dacă $A \leq 400$ se obține $0.4$ din punctajul alocat acelui test;
• altfel, punctajul acordat pe acel test va fi $0$.

Testare locală

Pentru testare locală puteți folosi următoarele fișiere listate la atașamente:

• grader.cpp
• problem.h

Exemplu

Presupunem că $N = 3$, $L = 4$, $x_1 = 2$, $x_2 = 7$ și $x_3 = 13$. Atunci un comportament posibil al soluției este:

• getX(1); va returna $2$;
• getX(2); va returna $7$;
• getX(3); va returna $13$;
• Una dintre regrupările optime este în fereastra $[5, 9]$. Jucătorul $1$ se deplasează la poziția $5$ (cost $3$), jucătorul $2$ stă pe loc (cost $0$), iar jucătorul $3$ se deplasează la poziția $9$ (cost $4$).
• Costul regrupării este $7$, deci funcția va returna $7$.

O versiune de program ar putea fi:

#include "problem.h"

long long solve(int N, int L) {
    int x1 = getX(1); // va returna 2
    int x2 = getX(2); // va returna 7
    int x3 = getX(3); // va returna 13
    long long res = /* calculele voastre aici */;
    return res;
}