Lời Giải HSG Tin TP Hà Nội - 2023

Author Hung Nguyen Tuong

Bài 1. Số chính phương đặc biệt

Số chính phương đặc biệt là số chính phương được tạo bởi một số nguyên tố.

Ví dụ: $4 = 2 \times 2; 9 = 3 \times 3; 36 = 6 \times 6$ nên $4$ và $9$ là số chính phương đặc biệt còn $36$ thì không phải là số chính phương đặc biệt.

Yêu cầu

Cho 2 số nguyên dương $a, b$. Hãy đếm xem trong đoạn $[a,b]$ có bao nhiêu số chính phương đặc biệt?

Dữ liệu

Vào từ tệp văn bản CP.INP: gồm hai số nguyên dương $a, b$ $(2 \leq a \leq b \leq 10^{12})$.

Kết quả

Ghi ra tệp văn bản CP.OUT: gồm một dòng chứa một số duy nhất là kết quả của bài toán.

Ràng buộc

• Có 80% số test ứng với 80% số điểm của bài thoả mãn $2 \leq a \leq b \leq 10^6$.
• 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Lời giải

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

int main()
{
    ll a, b;
    cin >> a >> b;
    int n = 1e6;
    vector<bool> sieve(n + 1, true);
    for (int i = 2; i <= sqrt(n); i++)
    {
        if (sieve[i])
        {
            for (int j = i * i; j <= n; j += i)
                sieve[j] = false;
        }
    }
    ll ans = 0;
    for (ll i = sqrt(a); i * i <= b; i++)
    {
        ll ii = i * i;
        if (sieve[i] && a <= ii && ii <= b)
            ans++;
    }
    cout << ans;
    return 0;
}

Bài 2. Bảng số

Cho một bảng vuông gồm $n$ hàng và $n$ cột. Các hàng được đánh số từ 1 đến $n$, các cột được đánh số từ 1 đến $n$. Ở ô hàng thứ $i$ và cột thứ $j$ có giá trị là $i \times j \ (1 \leq i,j \leq n)$.

Yêu cầu

Cho một số nguyên dương $x$. Hãy đếm số lượng ô trong bảng có giá trị bằng $x$.

Dữ liệu

Vào từ tệp văn bản BS.INP: gồm hai số nguyên $n$ và $x$ $(1 \leq n \leq 10^6, 1 \leq x \leq 10^{12})$ là kích thước của bảng và số nguyên cần đếm trong bảng.

Kết quả

Ghi ra tệp văn bản BS.OUT: số nguyên duy nhất là số lượng ô trong bảng có giá trị bằng $x$.

Ràng buộc

• Có 70% số test ứng với 70% số điểm của bài thoả mãn $0 < n \leq 10^3, 1 \leq x \leq 10^6$.
• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Giải thích:

Lời giải

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

int main()
{
    ll n, x, ans = 0;
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
    {
        if (x % i != 0 || x < i)
            continue;
        if (x / i <= n)
            ans++;
    }
    cout << ans;
    return 0;
}

Bài 3. Chia tiền thưởng

Nhờ hoàn thành tốt công việc, An và Bình được công ty thưởng $N$ tờ tiền.

Tờ tiền thứ $i$ có mệnh giá $a_i$. Hai bạn muốn chia đôi số tiền thành hai phần bằng nhau bằng cách chia cho mỗi người một số tờ tiền. Vì thế hai bạn quyết định sẽ chọn ra những tờ tiền để tổng số tiền hai bạn nhận được bằng nhau và lớn nhất, phần còn lại (nếu có) sẽ đem đi đầu tư.

Yêu cầu

Hãy giúp hai bạn tìm tổng số tiền lớn nhất mà mỗi người nhận được trước khi đầu tư.

Dữ liệu

Vào từ tệp văn bản CT.INP:

• Dòng đầu tiên chứa số nguyên dương $N \ (N\leq 500)$.
• Dòng thứ hai bao gồm $N$ số nguyên dương $a_1, a_2, ..., a_N$ là mệnh giá của những tờ tiền. Tổng giá trị những tờ tiền sẽ không vượt quá $10^5$.

Kết quả

Ghi ra tệp văn bản CT.OUT: gồm một dòng duy nhất là số tiền lớn nhất mà mỗi người nhận được.

Ràng buộc

• Có 40% số test ứng với 40% số điểm của bài thoả mãn $N \leq 3$.
• 30% số test tiếp theo ứng với 30% số điểm của bài thoả mãn $N \leq 12$.
• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Lời giải

Ý tưởng

Mục tiêu của ta là tìm ra số tiền lớn nhất mà mỗi người có được sau khi chia tiền với tiêu chí là 2 người đều có số tiền như nhau, nghĩa là số tiền còn lại mang đi đầu tư là nhỏ nhất và số tiền chênh lệch giữa họ là bằng 0.

Ý tưởng là ta sẽ bắt đầu tính toán khi số tiền chênh lệch giữa 2 người là lớn nhất, và lần lượt giảm số tiền chênh lệch đó đi đến khi bằng 0.

Gọi:

• $j$ là số tiền chênh lệch giữa 2 người.
• $m[i]$ là giá trị tờ tiền thứ $i$.

Tại vị trí $(i,j)$, khi mà số tiền chênh lệch giữa 2 người là $j$, và công ty mới chỉ thưởng cho 2 người đến tờ tiền thứ $i$, thì ta quan tâm việc mỗi người được nhiều nhất bao nhiêu tiền sau khi chia. Nói cách khác, số tiền để lại mang đi đầu tư nhỏ nhất là bao nhiêu.

Ta định nghĩa $dp[i][j]$ là số tiền nhỏ nhất để lại.

Hiển nhiên rằng, số tiền chênh lệch giữa 2 người không thể lớn hơn tổng số tiền mà công ty đã thưởng. Vì vậy ta cần thêm một giá trị nữa, $p[i]$, tổng số tiền từ tờ thứ $1$ đến $i$.

Khi xét đến tờ thứ $i$ tại số tiền chênh lệch $j$:

• Nếu $j > p[i]$ (số tiền chênh lệch lớn hơn cả tổng số tiền công ty thưởng), vậy thì sự chênh lệch đó không tồn tại:

  $$dp[i][j] = \infty$$

• Nếu $j = p[i]$ (số tiền chênh lệch bằng tổng số tiền công ty thưởng), vậy thì một người sẽ không có số tiền nào và người kia sẽ có toàn bộ số tiền:

  $$dp[i][j] = 0$$

• Trường hợp còn lại:

  • Hai người quyết định để lại tờ tiền thứ $i$ để đầu tư:

    $$dp[i][j] = dp[i-1][j] + m[i]$$

  • Ngược lại, ta lại có 2 lựa chọn:

    1. Tờ tiền thứ $i$ thuộc về người đang có ít tiền hơn:

       $$dp[i][j] = dp[i-1][\text{abs}(j-m[i])]$$

    2. Tờ tiền thứ $i$ thuộc về người đang có nhiều tiền hơn, và tất nhiên số tiền chênh lệch sau đó vẫn không thể vượt quá được tổng số tiền tính đến tờ thứ $i$:

       $$dp[i][j] = dp[i-1][j+m[i]]$$

  ⇒ Vậy giá trị tốt ưu nhất là giá trị nhỏ nhất trong 3 giá trị trên.

Kết quả của bài toán chính là tổng số tiền trừ đi $dp[n-1][0]$ và chia cho 2.

Code

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

int main()
{
    int n;
    cin >> n;
    vector<ll> m(n), p(n);
    for (int i = 0; i < n; i++)
    {
        cin >> m[i];
        p[i] = (i == 0 ? m[i] : p[i - 1] + m[i]);
    }

    vector<vector<ll>> dp(n, vector<ll>(p[n - 1] + 1));
    fill(dp[0].begin(), dp[0].end(), inf);
    dp[0][0] = m[0];
    dp[0][m[0]] = 0;

    for (int i = 1; i < n; i++)
    {
        for (int j = p[n - 1]; j >= 0; j--)
        {
            if (j > p[i])
                dp[i][j] = inf;
            else if (j == p[i])
                dp[i][j] = 0;
            else
            {
                dp[i][j] = min(dp[i - 1][j] + m[i], dp[i - 1][abs(j - m[i])]);
                if (j + m[i] <= p[i])
                    dp[i][j] = min(dp[i][j], dp[i - 1][j + m[i]]);
            }
        }
    }
    p[n - 1] = (p[n - 1] - dp[n - 1][0]) / 2;
    cout << p[n - 1];
    return 0;
}

Bài 4. Trạm gác trung tâm

Ban quản lý rừng nguyên sinh đang quản lý một khu vực rộng lớn.

Họ đã xây dựng $N$ trạm canh gác rừng (được đánh số từ $1 \to N$) và các trạm này được nối với nhau bởi $M$ con đường.

Trong $N$ trạm canh gác người ta đã chọn ra $K$ trạm làm trạm gác trung tâm - nơi điều hành các trạm gác nhỏ hơn và chứa các dụng cụ, phương tiện bảo vệ rừng.

Để đi lại và vận chuyển thiết bị dễ dàng giữa các trạm gác trung tâm, Ban quản lí quyết định nâng cấp một số con đường sao cho $K$ trạm gác trung tâm đều đi được đến nhau.

Yêu cầu

Hãy chọn các con đường nối $K$ trạm gác trung tâm để nâng cấp sao cho tổng độ dài của các con đường này là nhỏ nhất.

Dữ liệu

Vào từ tệp văn bản TG.INP:

• Dòng đầu tiên ghi ba số nguyên dương $N, M, K$ lần lượt là số lượng các trạm gác, số lượng con đường nối giữa các trạm gác và số lượng các trạm gác trung tâm $(1 < N \leq 500; N - 1 \leq M < N^2/2; 1 < K \leq N)$.
• Dòng thứ hai ghi $K$ số nguyên là số hiệu của $K$ trạm gác trung tâm.
• Trong $M$ dòng tiếp theo, mỗi dòng ghi ba số nguyên $u, v, c$ với ý nghĩa con đường hai chiều nối trực tiếp giữa hai trạm $u$ và $v$ có độ dài là $c$ $(1 < c \leq 10^9)$.

Kết quả

Ghi ra tệp văn bản TG.OUT: một dòng duy nhất chứa tổng độ dài các con đường thỏa mãn yêu cầu trên.

Ràng buộc

• Có 40% số test ứng với 40% số điểm của bài thoả mãn $K = N, N \leq 500$.
• 30% số test tiếp theo ứng với 30% số điểm của bài thoả mãn $K \leq 10, N \leq 200$.
• 30% số test còn lại ứng với 30% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Bài 5. Sắp xếp hoán vị

Cho số nguyên dương $N$ và dãy hoán vị từ $1$ đến $N$.

Hãy tính tổng chi phí nhỏ nhất để sắp xếp lại dãy con này thành dãy tăng dần.

Biết rằng có thể chọn một dãy con liên tiếp từ $i$ đến $j$ và sắp xếp lại dãy con này thành dãy tăng dần với chi phí là $\lfloor \sqrt{j - i + 1} \rfloor$ (lấy phần nguyên, ví dụ $\lfloor \sqrt{103} \rfloor = 10$).

Dữ liệu

Vào từ tệp văn bản SX.INP:

• Dòng đầu tiên chứa số nguyên dương $N$ $(1 \leq N \leq 10^6)$.
• Dòng thứ hai chứa $N$ số nguyên dương là hoán vị từ $1$ đến $N$.

Kết quả

Ghi ra tệp văn bản SX.OUT: chỉ phí nhỏ nhất để sắp xếp dãy hoán vị đã cho thành dãy tăng dần.

Ràng buộc

• Có 30% số test ứng với 30% số điểm của bài thoả mãn $N \leq 9$.
• 30% số test tiếp theo ứng với 30% số điểm của bài thoả mãn $N \leq 2000$.
• 30% số test tiếp theo ứng với 30% số điểm của bài thoả mãn $N \leq 10^5$.
• 10% số test còn lại ứng với 10% số điểm của bài thoả mãn $N \leq 10^6$.

Ví dụ