# Đề HSG9 - BRVT - 2022: Editorial

## Bài 1: Đếm số ô trống (6 điểm)

Cho số nguyên dương $n$ $\left( n \le 10^{18} \right)$, đếm tổng số ô trống có trong các chữ số của $n$, biết mỗi chữ số có các ô trống như sau:

- Chữ số $8$ có $2$ ô trống.
- Chữ số $0, 4, 6, 9$ có $1$ ô trống
- Chữ số $1, 2, 3, 5, 7$ không có ô trống.

### Accepted:
Để thuận tiện, ta dựng sẵn mảng $d$ với ==$d_i$ là số ô trống của chữ số $i$.==

Sau đó ta ==duyệt qua từng chữ số== và cộng số ô trống vào đáp án.

Độ phức tạp thời gian: $O \left( D \right)$ với $D$ là số lượng chữ số của $n$.

:::success
:::spoiler Code

#include<bits/stdc++.h>
using namespace std;

int n, d[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};

int main() {

    cin >> n;
    int res = 0;
    while (n > 0) {
        res += d[n % 10];
        n /= 10;
    }
    
    cout << res;

    return 0;
}

:::

## Bài 2: Tam giác đều lớn nhất (7 điểm)

Có $n$ thanh gỗ có độ đài là $A_1, A_2, \dots, A_n$ $\left( n \le 10^5, \; A_i \le 10^9 \right)$. Hãy cho biết có bao nhiêu tam giác đều có **cạnh lớn nhất** có thể được tạo ra bằng cách ghép các thanh gỗ đã cho.

**Biết rằng:** nếu có $k$ thanh gỗ có cùng độ dài thì có thể tạo ra $\frac {(k-2) \cdot (k-1) \cdot k}{6}$ tam giác đều.

### Accepted:

Sử dụng kiểu dữ liệu [map](https://blog.28tech.com.vn/stl-map-trong-c), đặt ==$d_x$ là số lượng thanh gỗ độ dài $x$.==
> Không thể sử dụng mảng bình thường vì $x \le 10^9$.

Đặt $res$ là độ dài $x$ lớn nhất thỏa mãn có ít nhất ba thanh gỗ độ dài $x$ $\left( d_x \ge 3 \right)$.

Kết quả của bài toán là: ==$\frac {(d_{res}-2) \cdot (d_{res}-1) \cdot d_{res}}{6}$.==

Độ phức tạp thời gian: $O(n \log n)$.
> Vì mỗi thao tác trên **map** mất chi phí thời gian là $\log n$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

int n;
map<int, int> d;

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        
        d[x]++;
        if (d[x] == 3) {
            res = max(res, x);
        }
    }
    
    long long k = d[res];
    cout << k * (k-1) * (k-2) / 6;

    return 0;
}

:::

## Bài 3: Aladdin (7 điểm)

Có $n$ cổ vật có giá trị là $A_1, A_2, \dots, A_n$ $\left( n \le 1000, \; A_i \le 10^9 \right)$. Tìm cách lấy các cổ vật để đạt tổng giá trị lớn nhất thỏa mãn quy tắc sau:

- Cổ vật lấy sau phải có **số thứ tự** lớn hơn cổ vật lấy trước.
- Cổ vật lấy sau phải có **giá trị** lớn hơn cổ vật lấy ngay trước và không được hơn quá $k$ đơn vị $\left( k \le 10^9 \right)$.

### Brute - force:

==Quay lui== thử tất cả các cách chọn.

Độ phức tạp thời gian: $O \left( 2^n \right)$.

### Accepted:

==Quy hoạch động cơ bản.==

Đặt $dp_i$ là tổng giá trị lớn nhất có thể nhận được nếu xét $i$ cổ vật đầu tiên và bắt buộc lấy cổ vật thứ $i$ ở vị trí cuối cùng.

Công thức quy hoạch động:
- Khởi gán: $dp_i$ = $A_i$ (chỉ lấy cổ vật thứ $i$).
- $dp_i = \max \left( dp_j \right) + A_i$ $\left( \forall \; j \lt i, \; A_j \le A_i \le A_j+k \right)$

Kết quả của bài toán: $\max(dp_i)$ $\left( 1 \le i \le n \right)$

Độ phức tạp thời gian: $O \left( n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1003;
int n, k, A[N];
long long dp[N], res;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        dp[i] = A[i];
        
        for (int j = 1; j < i; j++) {
            if (A[i] > A[j] && A[i] <= A[j]+k) {
                dp[i] = max(dp[i], dp[j] + A[i]);
            }
        }
        
        res = max(res, dp[i]);
    }
    
    cout << res;

    return 0;
}

:::