Lời Giải HSG Tin Tỉnh Quảng Ninh (B) - 2023

Author Hung Nguyen Tuong

Bài 1. Tài khoản

An có một phần mềm máy tính, người dùng muốn sử dụng được phần mềm này thì phải đăng ký tài khoản.

Tuy nhiên với số lượng người dùng ngày càng nhiều, dẫn tới việc có thể người dùng đăng ký tài khoản trùng nhau (tài khoản người đăng ký sau trùng với tài khoản người đã đăng ký trước đó).

Để xử lí việc này An nghĩ ra một ý tưởng như sau:

• Nếu tên tài người dùng đăng ký chưa được lưu trong hệ thống thì người dùng sẽ được đăng ký với tên tài khoản đó.
• Nếu tên tài khoản người dùng muốn đăng ký trùng với tên tài khoản đã được đăng ký trước đó thì hệ sống sẽ tự động thêm một số nguyên dương nhỏ nhất vào sau tên tài khoản đó sao cho tên tài khoản đó chưa được đăng ký.

Ví dụ giả sử trong hệ thống đã tồn tại tên $\text{"tinhoc"}$ mà người dùng tiếp theo đăng ký trùng tên thì sẽ được lưu tên tài khoản là $\text{"tinhoc1"}$, tương tự như vậy trong trường hợp có thêm người dùng đăng ký trùng tên $\text{"tinhoc"}$ thì hệ thống sẽ lưu tiếp theo là $\text{"tinhoc2"}$, $\text{"tinhoc3"}$…

Yêu cầu

Bạn hãy giúp An lập trình để thực hiện ý tưởng của mình.

Dữ liệu

Vào từ tệp văn bản acco.inp:

• Dòng đầu tiên chứa số nguyên dương $n \ ( 1 \le n \le 10^4)$ là số lượng tên tài khoản mà người dùng muốn đăng ký.
• Dòng thứ $i$ trong $n$ dòng tiếp theo chứa một xâu kí tự $s_i \ (1 \le i \le n)$ chỉ gồm các chữ cái tiếng Anh thường $'a'...'z'$ và có độ dài không quá 10 kí tự là tên các tài khoản muốn đăng ký.

Kết quả

Ghi ra tệp văn bản acco.out gồm $n$ dòng là kết quả các tài khoản của người dùng được lưu trong hệ thống tương ứng với dữ liệu vào.

Ví dụ

Ràng buộc

• Có $20\%$ số test ứng với $20\%$ số điểm của bài thoả mãn: $n \le 10^2$.
• $20\%$ số test khác ứng với $20\%$ số điểm của bài thoả mãn: $n \le 10^3$.
• $60\%$ số test còn lại ứng với $60\%$ số điểm của bài không có thêm ràng buộc nào.

Lời giải

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

int main()
{
    int n;
    cin >> n;
    map<string, int> mp;
    for (int i = 0; i < n; i++)
    {
        string ten;
        cin >> ten;
        if (mp.find(ten) != mp.end())
            cout << ten << mp[ten] << nl;
        else
            cout << ten << nl;
        mp[ten]++;
    }
    return 0;
}

Bài 2. Tổng ước

Cho một số nguyên dương $n \ (1 \le n \le 10^9)$.

Yêu cầu

Đếm các số nguyên dương trong đoạn $[1,n]$ mà có tổng các ước nguyên dương là số nguyên tố.

Dữ liệu

Vào từ tệp văn bản prim.inp một số nguyên dương duy nhất $n$.

Kết quả

Ghi ra tệp văn bản prim.out một số nguyên duy nhất là số các số nguyên trong đoạn $[1,n]$ mà có tổng các ước là số nguyên tố.

Ví dụ

Lời giải

Thuật toán ngây thơ 1

Với từng $i$ từ $1 \to n$, ta tính tổng các ước của $i$. Sau đó kiểm tra xem tổng đó có phải là số nguyên tố hay không.

Chi phí tính tổng các ước là: $O(\sqrt n)$.

Thực tế, tổng các ước nguyên dương của một số nguyên $n$ sẽ nằm trong khoảng $[1,2n]$. Và khi sử dụng thuật toán ngây thơ để in ra các tổng ước mà là số nguyên tố thì ta nhận thấy tổng đó $\approx n$. Vậy chi phí kiểm tra tính nguyên tố sẽ là: $O(\sqrt n)$.

Và ta thực hiện 2 việc đó $n$ lần từ $1 \to n$, nên độ phức tạp cuối cùng của thuật toán là: $O(n \sqrt n)$.

Với ràng buộc $1 \le n \le 10^9$ thì thuật toán này không thể nào được full điểm.

Thuật toán ngây thơ 2

Xét ví dụ với $n \le 10^4$, ta sử dụng thuật ngây thơ 1 để in ra những số $n$ thoả mãn, $\sqrt n$, thừa số nguyên tố của $n$, tổng các ước của $n$.

4 2 2^1 7
9 3 3^1 13
16 4 2^2 31
25 5 5^1 31
64 8 2^3 127
289 17 17^1 307
729 27 3^3 1093
1681 41 41^1 1723
2401 49 7^2 2801
3481 59 59^1 3541
4096 64 2^6 8191
5041 71 71^1 5113
7921 89 89^1 8011

Ta nhìn thấy rằng các số $n$ thoả mãn ở đây đều là các số chính phương. Và đặc biệt hơn nữa $\sqrt n$ chỉ có duy nhất $1$ ước nguyên tố.

Vậy việc tính tổng các ước của $n$ sẽ trở lên vô cùng nhanh chóng bằng cách sử dụng Sàng Eratosthenes để tìm ước nguyên tố nhỏ nhất của nhiều số $\le \sqrt n$ trong $O(1)$.

Giả sử $\sqrt n = p^k \Rightarrow n = p^{2k}$. Ta có tổng các ước là:

Đây là tổng cấp số nhân nên ta có thể tính tổng đó trong $O(1)$:

Thay vì duyệt từ $1 \to n$, ta chỉ cần duyệt từ $2 \to \sqrt n$, sau đó cộng $1$ vào kết quả (tính thêm số $2$).

Ở đây có lẽ chúng ta nghĩ sao không sử dụng sàng nguyên tố để kiểm tra tính nguyên tố của tổng. Tuy nhiên, tổng các ước có thể rất lớn nên việc khai báo sàng sẽ rất tốn bộ nhớ và không phù hợp. Thế nên ta ở thuật toán ngây thơ này, ta vẫn sử dụng giải thuật $O(\sqrt n)$ để kiểm tra tính nguyên tố.

Vậy độ phức tạp là: $O(\sqrt n \times \log (\log \sqrt n) + \sqrt n \times \sqrt n) \approx O(n)$. Và thuật toán này đã đủ tốt để chạy được full điểm.

Thuật toán tối ưu

Tới đây đã tối ưu hết các bước trừ việc kiểm tra tính nguyên tố của tổng ước. Vì tổng ước có thể rất lớn, nên sàng nguyên tố là không phù hợp. Do vậy ta sử dụng phép Kiểm tra Miller-Rabin với $c = 5$ cơ số là: $2,3,5,7,61$.

Độ phức tạp chỉ còn: $O(\sqrt n \times \log (\log \sqrt n) + \sqrt n \times c\log (n)) \approx O(\sqrt n \times \log n)$.

Ta có thể dễ dàng chạy đến $n \le 10^{12}$, thậm chí còn hơn.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

const int maxn = 1e6;
vector<int> minPrime(maxn + 1, 0);
void sieve()
{
    for (int i = 2; i * i <= maxn; i++)
    {
        if (minPrime[i] == 0)
        {
            for (int j = i * i; j <= maxn; j += i)
            {
                if (minPrime[j] == 0)
                    minPrime[j] = i;
            }
        }
    }
    for (int i = 2; i <= maxn; i++)
    {
        if (minPrime[i] == 0)
            minPrime[i] = i;
    }
}
int prime_power(ll num)
{
    int k = 0, p = minPrime[num];
    while (num % p == 0)
    {
        num /= p;
        k++;
    }
    return (num == 1 ? k : -1);
}
ll sum_of_divisor(ll num)
{
    ll q = minPrime[num];
    ll qn = num * num * q;
    return (qn - 1) / (q - 1);
}
ll power(ll a, ll b, ll m)
{
    a %= m;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % m;
        b >>= 1;
        a = (a * a) % m;
    }
    return res;
}
bool test(ll a, ll n, ll k, ll m)
{
    ll mod = power(a, m, n);
    if (mod == 1 || mod == n - 1)
        return true;

    for (int l = 1; l < k; l++)
    {
        mod = (mod * mod) % n;
        if (mod == n - 1)
            return true;
    }

    return false;
}
bool RabinMiller(ll n)
{
    if (n == 2 || n == 3 || n == 5 || n == 7)
        return true;
    if (n < 11)
        return false;

    ll k = 0, m = n - 1;
    while (!(m & 1))
    {
        m >>= 1;
        k++;
    }

    vector<int> checkSet = {2, 3, 5, 7, 61};
    for (auto a : checkSet)
    {
        if (!test(a, n, k, m))
            return false;
    }

    return true;
}
int solve(ll n)
{
    if (n < 2)
        return 0;
    if (n < 4)
        return 1;

    int ans = 1;
    for (ll i = 2; i * i <= n; i++)
    {
        if (prime_power(i) == -1)
            continue;
        if (RabinMiller(sum_of_divisor(i)))
            ans++;
    }

    return ans;
}
int main()
{
    sieve();
    ll n;
    cin >> n;
    cout << solve(n);
    return 0;
}

Bài 3. Khai thác radium

Để thăm dò địa chất trước khi khai thác radium trên cao nguyên $X$, một vệ tinh đặc biệt đã được phóng lên quỹ đạo giúp đo mức độ phóng xạ trên bề mặt.

Chúng ta biểu diễn cao nguyên dưới dạng một hình chữ nhật bao gồm $m * n$ ô vuông đơn vị. Ký hiệu ô vuông trong hàng thứ $i$ và cột thứ $j$ là $(i,j)$.

Kết quả của việc khảo sát cao nguyên đã xác định được mức độ phóng xạ cho từng ô vuông. Mức độ phóng xạ của ô $(i,j)$ được cho bởi một số nguyên dương $a_{ij}$. Độ chính xác của phép đo cao đến mức tất cả các số $a_{ij}$ đều khác nhau. Ô $(i,j)$ được coi là phù hợp để khai thác radium nếu giá trị của $a_{ij}$ lớn nhất ở hàng thứ $i$ và cũng lớn nhất ở cột thứ $j$.

Trong quá trình đo, $q$ lần tinh chỉnh liên tiếp mức độ phóng xạ đã được thực hiện. Cụ thể, lần tinh chỉnh thứ $k$ đã thay đổi giá trị của $a_{r_k c_k}$ thành một giá trị hoàn toàn lớn hơn. Hơn nữa, sau mỗi lần tinh chỉnh, tất cả các giá trị của $a_{ij}$ vẫn khác nhau.

Yêu cầu

Cho các giá trị ban đầu $a_{ij}$ và danh sách các lần tinh chỉnh, bạn hãy viết một chương trình xác định số ô phù hợp để khai thác radium sau mỗi lần tinh chỉnh.

Dữ liệu

Vào từ tệp văn bản radi.inp:

• Dòng đầu tiên chứa ba số nguyên dương $m,n$ và $q \ (1 \le m \times n \le 2 \times 10^5; \ 1 \le q \le 2 \times 10^5)$ tương ứng là số hàng, số cột của hình chữ nhật và số lần tinh chỉnh.
• Mỗi dòng trong $m$ dòng tiếp theo chứa $n$ số nguyên dương, số thứ $j$ trong dòng thứ $i$ là giá trị ban đầu của $a_{ij} \ (1 \le a_{ij} \le 10^7,$ tất cả các $a_{ij}$ đều khác nhau $)$.
• Tiếp theo, có $q$ dòng mô tả các tinh chỉnh mức độ phóng xạ, dòng thứ $k$ chứa ba số nguyên $r_k, c_k, x_k$ mô tả sự thay đổi mức độ phóng xạ của ô $(r_k,c_k)$ thành giá trị mới là $x_k \ (1 \le r_k \le m; \ 1 \le c_k \le n; \ 1 \le x_k \le 10^7)$.
• Dữ liệu đảm bảo rằng $x_k$ hoàn toàn lớn hơn mức độ phóng xạ trước đó trong ô này và tất cả các mức độ phóng xạ đều khác nhau sau mỗi lần thay đổi.

Kết quả

Ghi ra tệp văn bản radi.out gồm $q$ dòng, ở dòng thứ $k$ chứa một số nguyên là số ô phù hợp để khai thác radium sau lần tinh chỉnh thứ $k$.

Ví dụ

Giải thích:

• Trong lần tinh chỉnh thứ nhất, ta thay đổi mức độ phóng xạ của ô $(2,2)$ từ $5$ thành $9$. Sau lần tinh chỉnh này, mức độ phóng xạ trong các ô như sau và chỉ có 1 ô phù hợp là $(2,2)$.

  1 4 3 6 9 2

• Trong lần tinh chỉnh thứ hai, ta thay đổi mức độ phóng xạ của ô $(1,3)$ từ $3$ thành $5$. Sau lần tinh chỉnh này, mức độ phóng xạ trong các ô như sau và có 2 ô phù hợp là $(1,3)$ và $(2,2)$.

  1 4 5 6 9 2

• Trong lần tinh chỉnh thứ ba, ta thay đổi mức độ phóng xạ của ô $(2,2)$ từ $9$ thành $10$. Sau lần tinh chỉnh này, mức độ phóng xạ trong các ô như sau và có 2 ô phù hợp là $(1,3)$ và $(2,2)$.

  1 4 5 6 10 2

Ràng buộc

• Có $40\%$ số test ứng với $40\%$ số điểm của bài toán thoả mãn: $1 \le m \times n \le 100$ và $1 \le q \le 100$.
• $24\%$ số test khác ứng với $24\%$ số điểm của bài thoả mãn: $1 \le m\times n \le 5000$ và $1 \le q \le 5000$.
• $20\%$ số test khác ứng với $20\%$ số điểm của bài thoả mãn: $1 \le m \le 400; \ 1 \le n \le 400$ và $1 \le q \le 2\times 10^5$.
• $16\%$ số test còn lại ứng với $16\%$ số điểm của bài không có thêm ràng buộc nào.

Lời giải

Theo đề bài, ô $(i,j)$ được coi là phù hợp để khai thác radium nếu giá trị của $a_{ij}$ là lớn nhất ở hàng thứ $i$ và cũng lớn nhất ở cột thứ $j$.

Mặt khác, tất cả các giá trị của $a_{ij}$ đều khác nhau, kể cả khi sau tinh chỉnh.

Do vậy, 2 ô khai thác được sẽ không bao giờ nằm cùng hàng hay cùng cột.

Ta cần khai báo các mảng sau:

• $r[i]$: vị trí trong hàng của ô khai thác được ở hàng $i$ từ trái sang. Nếu trong hàng không có ô nào khai thác được thì $r[i] = -1$.
• $c[j]$: vị trí trong cột của ô khai thác được ở cột $j$ từ trên xuống. Nếu trong cột không có ô nào khai thác được thì $c[j]=-1$.
• $\text{rmax}[i]$: mức độ phóng xạ lớn nhất ở hàng $i$.
• $\text{cmax}[j]$: mức độ phóng xạ lớn nhất ở cột $j$.

Từ đây ta duyệt từng ô và đếm xem ban đầu có bao nhiêu ô phù hợp để khai thác.

Ta có $(i,j)$ là ô phù hợp nếu:

⇒ Kéo theo là $r[i]=j$ và $c[j]=i$.

Khi tinh chỉnh mức độ phóng xạ là $x$ tại ô $(i,j)$ thì có 2 trường hợp sau:

• Trường hợp 1: Ô $(i,j)$ đã là ô có thể khai thác được ($r[i]=j$ và $c[j]=i$). Thì sau khi tinh chỉnh với mức độ phóng xạ lớn hơn thì $(i,j)$ vẫn là ô có thể khai thác được, nên tổng số ô phù hợp để khai thác là không thay đổi.
• Trường hợp 2: Ô $(i,j)$ chưa phải ô khai thác được. Nên sau khi tỉnh chỉnh với mức độ phóng xạ lớn hơn thì ta lại có các trường hợp sau:

  • Trường hợp 2.1: Ô $(i,j)$ trở thành ô khai thác được nếu:

    $$x > \max(\text{rmax}[i], \text{cmax}[j])$$

    Lúc này ta cập nhật $\text{rmax}[i] = \text{cmax}[j] = x$.

    Như đã giải thích, 2 ô khai thác được sẽ không bao giờ nằm cùng hàng hay cùng cột, nên nhiều nhất 1 ô khai thác được ở hàng $i$ và nhiều nhất 1 ô khai thác được ở cột $j$ sau lần tinh chỉnh này thì không còn khai thác được nữa.

    Nếu có 1 ô khai thác được ở hàng $i$ nghĩa là $r[i] \neq -1$ và $c[r[i]] \neq -1$. Sau khi tinh chỉnh thì ô đó không còn khai thác được, vậy tổng số ô khai thác được giảm đi $1$.

    Tương tự, nếu có 1 ô khai thác được ở cột $j$ nghĩa là $c[j] \neq -1$ và $r[c[j]] \neq -1$. Sau khi tinh chỉnh thì ô đó không còn khai thác được, vậy tổng số ô khai thác cũng giảm đi $1$.

    Bây giờ $(i,j)$ là ô khai thác được nên $r[i]=j$ và $c[j]=i$.

  • Trường hợp 2.2: Ô $(i,j)$ vẫn chưa trở thành ô khai thác được vì không thoả mãn điều kiện: $x > \text{rmax}[i]$ và $x > \text{cmax}[j]$.

    • Nếu $x$ đều nhỏ hơn $\text{rmax}[i]$ và $\text{cmax}[j]$ thì không có điều gì thay đổi.
    • Nếu $x$ chỉ lớn hơn $\text{rmax}[i]$, thì ô khai thác được ở hàng $i \ (r[i] \neq -1, \ c[r[i]] \neq -1)$ sẽ không còn khai thác được nữa. Số ô khai thác được giảm đi $1$.
    • Nếu $x$ chỉ lớn hơn $\text{cmax}[j]$, thì ô khai thác được ở cột $j \ (c[j] \neq -1, \ r[c[j]] \neq -1)$ sẽ không còn khai thác được nữa. Số ô khai thác được giảm đi $1$.

Độ phức tạp là: $O(mn + q)$.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl '\n'

int main()
{
    int m, n, q;
    cin >> m >> n >> q;
    int a[m][n];
    const int INF = 1e9;
    vector<int> r(m, -1), c(n, -1);
    vector<int> r_max(m, -INF), c_max(n, -INF);
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    }

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
            r_max[i] = max(r_max[i], a[i][j]);
    }

    for (int j = 0; j < n; j++)
    {
        for (int i = 0; i < m; i++)
            c_max[j] = max(c_max[j], a[i][j]);
    }

    int res = 0;
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (a[i][j] == r_max[i] && a[i][j] == c_max[j])
            {
                r[i] = j;
                c[j] = i;
                res++;
            }
        }
    }

    while (q--)
    {
        int i, j, x;
        cin >> i >> j >> x;
        i--, j--;
        a[i][j] = x;
        if (r[i] == j && c[j] == i)
        {
            r_max[i] = c_max[j] = x;
        }
        else
        {
            if (x > max(r_max[i], c_max[j]))
            {
                res++;
                r_max[i] = c_max[j] = x;
                if (r[i] != -1 && c[r[i]] != -1)
                {
                    res--;
                    c[r[i]] = -1;
                }
                if (c[j] != -1 && r[c[j]] != -1)
                {
                    res--;
                    r[c[j]] = -1;
                }
                r[i] = j;
                c[j] = i;
            }
            else if (x > r_max[i])
            {
                r_max[i] = x;
                if (r[i] != -1 && c[r[i]] != -1)
                {
                    res--;
                    r[i] = c[r[i]] = -1;
                }
            }
            else if (x > c_max[j])
            {
                c_max[j] = x;
                if (c[j] != -1 && r[c[j]] != -1)
                {
                    res--;
                    c[j] = r[c[j]] = -1;
                }
            }
        }
        cout << res << nl;
    }
    return 0;
}

Bài 4. Khôi phục bức tường

Bạn phải khôi phục lại bức tường. Bức tường gồm $n$ cột gạch, chiều cao cột thứ $i$ ban đầu bằng $h_i$, chiều cao được đo bằng số viên gạch. Sau khi khôi phục, tất cả $n$ cột phải có chiều cao bằng nhau.

Bạn được phép thực hiện các thao tác sau:

• Đặt một viên gạch lên trên đỉnh một cột, chi phí của thao tác này là $a$.
• Dỡ một viên gạch khỏi đỉnh một cột không trống, chi phí cho thao tác này là $r$.
• Di chuyển một viên gạch từ đỉnh một cột không trống này sang đỉnh một cột khác, chi phí cho thao tác này là $m$.

Bạn không thể tạo thêm cột hoặc bỏ qua cột tồn tại trước đó ngay cả khi chiều cao của nó trở thành $0$.

Yêu cầu

Bạn hãy tính tổng chi phí khôi phục tối thiểu, hay nói cách khác là tính tổng chi phí tối thiểu để làm tất cả các cột có chiều cao bằng nhau.

Dữ liệu

Vào từ tệp văn bản rest.inp:

• Dòng đầu tiên chứa $4$ số nguyên $n,a,r,m \ (1 \le n \le 10^5; \ 0 \le a,r,m \le 10^4)$ tương ứng là số cột và chi phí các thao tác đặt, dỡ, di chuyển một viên gạch.
• Dòng thứ hai chứa $n$ số nguyên $h_1,h_2,...,h_n \ (0 \le h_i \le 10^9)$ là độ cao các cột.

Kết quả

Ghi ra tệp rest.out một số nguyên là chi phí khôi phục tối thiểu.

Ví dụ

Giải thích:

• Trong ví dụ thứ nhất, một cách khôi phục bức tường với chi phí tối thiểu là:

  • Đặt một viên gạch lên đỉnh cột thứ $3$, chi phí cho thao tác này là $1$. Bây giờ độ cao của các cột là: $5,5,4,6,5$.
  • Tiếp tục đặt một viên gạch lên đỉnh cột thứ $3$, chi phí cho thao tác này là $1$. Bây giờ độ cao của các cột là: $5,5,5,6,5$.
  • Dỡ một viên gạch khỏi đỉnh cột thứ $4$, chi phí cho thao tác này là $2$. Bây giờ độ cao của các cột là: $5,5,5,5,5$.

  ⇒ Sau các thao tác trên, tất cả các cột đều có chiều cao bằng nhau và tổng chi phí là $1+1+2=4$.

• Trong ví dụ thứ hai, một cách khôi phục bức tường với chi phí tối thiểu là:

  • Di chuyển một viên gạch từ đỉnh cột thứ $4$ sang đỉnh cột thứ $3$, chi phí cho thao tác này là $2$. Bây giờ độ cao của các cột là: $5,5,4,5,5$.
  • Đặt một viên gạch lên đỉnh cột thứ $3$, chi phí cho thao tác này là $1$. Bây giờ độ cao của các cột là: $5,5,5,5,5$.

  ⇒ Sau các thao tác trên, tất cả các cột đều có chiều cao bằng nhau và tổng chi phí là $2+1=3$.

Ràng buộc

• Có $25\%$ số test ứng với $25\%$ số điểm của bài thoả mãn: $a = r$ và $m \ge a + r$.
• $25\%$ số test khác ứng với $25\%$ số điểm của bài thoả mãn: $1 \le n \le 10^3$ và $0 \le h_i \le 10^4$.
• $25\%$ số test khác ứng với $25\%$ số điểm của bài thoả mãn: $0 \le h_i \le 10^6$.
• $25\%$ số test còn lại ứng với $25\%$ số điểm của bài không có thêm ràng buộc nào.

Lời giải

Ý tưởng

Ta sẽ duyệt từng độ cao, và đi tìm chi phí nhỏ nhất để khôi phục lại bức tường đến độ cao đó. Kết quả của bài toán chính là giá trị nhỏ nhất của những chi phí khôi phục đó.

Trước hết, ta cần tìm ra cách để khôi phục bức tường đến độ cao $i$. Ta sẽ sắp xếp mảng độ cao của các cột theo thứ tự không giảm. Sau đó thực hiện các thao tác để giảm đi số viên gạch ở những cột cao hơn $i$, và tăng thêm số viên gạch ở những cột thấp hơn $i$.

Lưu ý rằng, ta không được tạo thêm cột hay bỏ qua những cột có độ cao là $0$.

Ta thấy rằng có 2 trường hợp là:

1. $a+r\le m$: tổng chi phí đặt và gỡ ít hơn hoặc bằng chi phí di chuyển, ta nên gỡ đi những viên gạch ở cột cao hơn và đặt thêm vào những cột thấp hơn.
2. $a+r>m$: tổng chi phí đặt và gỡ nhiều hơn phí di chuyển, ta nên di chuyển những viên gạch ở cột cao hơn sang cột thấp hơn.

Ta cần tìm vị trí $p \ (1 \to n)$ sao cho: độ cao các cột từ $1 \to p$ đều $\le i$, độ cao các cột từ $p+1 \to n$ đều $> i$. Tiếp đến ta sử dụng mảng cộng dồn $\text{pref}[n]$ để tính xem từ $1 \to p$ có tổng cộng bao nhiêu viên gạch.

Gọi $A$ là tổng số viên gạch cần thêm vào những cột thấp hơn hoặc bằng $i$, ta có công thức:

Và $B$ là tổng số viên gạch cần bớt đi ở những cột cao hơn $i$, ta có công thức:

Từ đây ta có $3$ trường hợp khi khôi phục bức tường đến độ cao $i$:

1. Nếu $A=B$ thì chi phí khôi phục tối ưu sẽ là: $A \times \min(a+r,m)$.
2. Nếu $A<B$ thì sau khi thực hiện các thao tác đặt, gỡ và chuyển thì tổng số viên gạch cần bớt đi ở những cột cao hơn $i$ chỉ còn $B - A$, nên chi phí khôi phục là: $A \times \min(a+r,m) + (B-A) \times R$.
3. Nếu $A > B$ thì cũng tương tự, còn $A-B$ viên gạch cần thêm ở những cột thấp hơn $i$, nên chi phí khôi phục là: $B \times \min(a+r,m) + (A-B) \times a$.

Ta đã thực hiện những công việc sau:

• Sắp xếp: $O(n \times \log n)$,
• Duyệt từng độ cao $O(h_{\max})$ với $h_{\max}$ là hằng số $\ge$ chiều cao lớn nhất của các cột ban đầu,
• Tìm kiếm vị trí $p$ với $O(\log n)$,
• Tính chi phí khôi phục trong $O(1)$.

⇒ Độ phức tạp của thuật toán là:

Tối ưu

Với $h \le 10^9$ thì thuật toán trên không thể nào được full điểm. Ta mất chi phí nhiều nhất ở việc duyệt qua từng độ cao $i$, vậy nên ta phải tối ưu bằng cách chỉ duyệt những độ cao $i$ cần thiết.

Khi duyệt từng độ cao từ $0 \to h_{\max}$ và in ra chi phí khôi phục bức tường đến độ cao tương ứng thì ta thấy rằng, chi phí khôi phục có xu hướng giảm đến một giá trị nào đó rồi lại tăng lên. Nghĩa là đường biểu diễn chi phí của từng độ cao là một đường cong đi xuống rồi đi lên.

Vậy kết quả của bài toán chính là điểm cực tiểu của đường cong đó.

Ta tìm điểm cực tiểu đó bằng tìm kiếm tam phân. Ở đây, ta chọn cận dưới $low=0$ và cận trên $high=10^{10} \ (h_{\max})$ để đảm bảo là luôn có kết quả.

Tới đây ta đã tối ưu bằng cách chỉ xét những độ cao $i$ cần thiết.

Độ phức tạp của thuật toán chỉ còn: $O(n \times \log n + \log h_{\max} \times \log n) = O(n \times \log n)$.

Code

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define nl '\n'
const int maxn = 1e5 + 5;
int n;
ll a, r, m;
ll h[maxn], pref[maxn];

ll cost(ll height)
{
    ll p = upper_bound(h, h + n + 1, height) - h - 1;
    ll A = p * height - pref[p];
    ll B = pref[n] - pref[p] - (n - p) * height;
    if (A == B)
        return A * min(a + r, m);
    else if (A < B)
        return A * min(a + r, m) + (B - A) * r;
    return B * min(a + r, m) + (A - B) * a;
}

ll ternarySearch()
{
    ll low = 0, high = 1e10;
    while (high - low >= 3)
    {
        ll mid1 = low + (high - low) / 3;
        ll mid2 = high - (high - low) / 3;
        ll cost1 = cost(mid1);
        ll cost2 = cost(mid2);
        if (cost1 == cost2)
        {
            low = mid1;
            high = mid2;
        }
        else if (cost1 < cost2)
        {
            high = mid2 - 1;
        }
        else
        {
            low = mid1 + 1;
        }
    }
    ll ans = cost(low);
    for (ll i = low + 1; i <= high; i++)
    {
        ans = min(ans, cost(i));
    }
    return ans;
}

int main()
{
    cin >> n >> a >> r >> m;
    h[0] = pref[0] = 0;

    for (int i = 1; i <= n; i++)
        cin >> h[i];
    sort(h, h + n + 1);
    for (int i = 1; i <= n; i++)
        pref[i] = pref[i - 1] + h[i];

    cout << ternarySearch();
    return 0;
}