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

Author Hung Nguyen Tuong

Bài 1. Doanh thu

Một nhà hàng buffet có $n$ khách hàng trong một ngày, mỗi khách có độ tuổi nhất định. Giá vé niêm yết là $300.000$ đồng/người, nhưng có chương trình khuyến mãi dựa trên độ tuổi:

1. Nếu tuổi $\le 5$ → Miễn phí.
2. Nếu $5 <$ tuổi $\le 10$ → Giảm 80%.
3. Nếu $10 <$ tuổi $\le 15$ → Giảm 50%.
4. Nếu tuổi $\ge 60$ → Giảm 20%.

Yêu cầu

Tính tổng doanh thu của nhà hàng trong ngày dựa trên chương trình khuyến mãi này.

Dữ liệu

File đầu vào: TURNO.INP

• Dòng 1: Số nguyên $n ~ (1 \le n \le 10^7)$ – Số lượng khách hàng.
• Dòng 2: $n$ số nguyên $a_1,a_2\ldots,a_n ~(1 \le a_i \le 100)$ – Tuổi của từng khách hàng.
• Các số cách nhau bởi dấu cách.

Kết quả

File đầu ra: TURNO.OUT

• Ghi một số nguyên duy nhất – tổng doanh thu của nhà hàng.
• Đơn vị mặc định là đồng.

Ví dụ

Ràng buộc

• 60% số test: $n\le 10^3$.
• 40% số test còn lại: $n \le 10^7$.

Lời giải

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

int price(int a)
{
    if (a <= 5)
        return 0;
    if (a <= 10)
        return 60;
    if (a <= 15)
        return 150;
    if (a >= 60)
        return 240;
    return 300;
}

int main()
{
    int n, ans = 0;
    cin >> n;
    while (n--)
    {
        int a;
        cin >> a;
        ans += price(a);
    }
    cout << ans * 1000;
    return 0;
}

Bài 2. Dãy số

Để chuẩn bị cho kỳ thi học sinh giỏi cấp tỉnh năm nay, thầy Minh – giáo viên dạy Tin học của trường – muốn kiểm tra kiến thức lập trình của đội tuyển học sinh giỏi cấp tỉnh môn Tin học. Thầy ra một bài toán như sau:

Cho một dãy $A$ gồm $n$ số nguyên không âm $a_1, a_2, \dots, a_n$. Sau đó, biến đổi dãy $A$ thành dãy $A'$ sao cho phần tử thứ $i$ của dãy $A'$ có giá trị bằng tổng các giá trị từ phần tử thứ nhất đến phần tử thứ $i$ của dãy $A$, với $i = 1, 2, \dots, n$.

Ví dụ, dãy $A$ có $5$ phần tử là $0,1,0,2,2$. Sau khi biến đổi, dãy $A'$ là $0,1,1,3,5$.

Tiếp theo, cho một dãy $B$ gồm $m$ số nguyên không âm $b_1, b_2, \dots, b_m$.

Yêu cầu

Hãy tìm vị trí xuất hiện của phần tử $b_j ~ (1 \leq j \leq m)$ trong dãy $A'$.

Dữ liệu

File đầu vào: SEQ.INP

• Dòng 1: Hai số nguyên $n, m ~ (1 \leq n, m \leq 10^6)$ lần lượt là số lượng phần tử của dãy $A$ và dãy $B$.
• Dòng 2: $n$ số nguyên không âm $a_1, a_2, \dots, a_n ~ (0 \leq a_i \leq 10^6, 1 \leq i \leq n)$.
• Dòng 3: $m$ số nguyên không âm $b_1, b_2, \dots, b_m ~ (0 \leq b_j \leq 10^6, 1 \leq j \leq m)$.

Các số trên một dòng của file dữ liệu vào được ghi cách nhau bởi dấu cách.

Kết quả

File đầu ra: SEQ.OUT

• Một dòng gồm $m$ số nguyên, số thứ $j$ là vị trí xuất hiện đầu tiên của $b_j ~ (1 \leq j \leq m)$ trong dãy $A'$.
• Nếu có nhiều vị trí xuất hiện, in ra vị trí xuất hiện đầu tiên.
• Nếu $b_j$ không xuất hiện trong dãy $A'$, thì số thứ $j$ in ra $-1$.

Ví dụ

Ràng buộc

• 40% số test ứng với 40% số điểm của bài có $n, m \leq 10^3$.
• 30% số test ứng với 30% số điểm của bài có $n, m \leq 3 \times 10^4$.
• 30% số test còn lại ứng với 30% số điểm của bài có $n, m \leq 10^6$.

Lời giải

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

int main()
{
    int n, m;
    cin >> n >> m;
    ll a, b, p = 0;
    map<ll, int> mp;
    for (int i = 1; i <= n; i++)
    {
        cin >> a;
        p += a;
        if (mp.find(p) == mp.end())
            mp[p] = i;
    }
    while (m--)
    {
        cin >> b;
        cout << (mp.find(b) == mp.end() ? -1 : mp[b]) << " ";
    }
    return 0;
}

• Độ phức tạp: $O((m+n)\log n)$.

Bài 3. Khảo cổ

Một nhóm khảo cổ tìm thấy những cổ vật có chứa thông tin được mã hóa theo quy tắc sau:

• Dòng đầu tiên là số $0$ hoặc số $1$.
• Dòng thứ hai là một dãy các ký tự chữ cái in thường (gọi là đoạn mã $V$).

Qua nghiên cứu, họ phát hiện rằng thông tin trên cổ vật sau khi giải mã sẽ thu được một đoạn mã thông tin gốc $S$. Quy luật biến đổi từ đoạn mã gốc $S$ về đoạn mã $V$ được thực hiện như sau:

1. Nhân đôi đoạn mã gốc $S$ để tạo thành đoạn mã $T$.
2. Chọn một ký tự trong đoạn mã $T$, nhân đôi ký tự đó, tạo thành đoạn mã $U$ (độ dài tăng thêm 1 ký tự).
3. Nếu dòng đầu tiên trên cổ vật là $1$, đảo ngược đoạn mã $U$ để nhận được đoạn mã $V$. Nếu dòng đầu tiên trên cổ vật là $0$, đoạn mã $U$ chính là đoạn mã $V$.

Yêu cầu

Dựa vào thông tin trên cổ vật, xác định:

• Ký tự đã được nhân đôi ở bước 2.
• Đoạn mã thông tin gốc $S$ của cổ vật.

Dữ liệu

File đầu vào: ARCHA.INP

• Dòng 1: Một số nguyên $K~(0 \leq K \leq 1)$ – Quy tắc biến đổi (có đảo ngược hay không).
• Dòng 2: Một đoạn mã $V$ – Chuỗi ký tự chữ cái in thường có độ dài không quá $10^6$.

Kết quả

File đầu ra: ARCHA.OUT

• Dòng 1: Ký tự đã được nhân đôi ở bước 2.
• Dòng 2: Đoạn mã gốc $S$ của cổ vật.

Ví dụ

Ràng buộc

• 40% số test ứng với 40% số điểm, có độ dài của $V$ không quá $10^2$.
• 30% số test ứng với 30% số điểm, có độ dài của $V$ không quá $10^5$.
• 30% số test còn lại ứng với 30% số điểm, có độ dài của $V$ không quá $10^6$.

Lời giải

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

int k;
string V;
int cnt[26] = {0};

int main()
{
    cin >> k >> V;
    if (k)
        reverse(V.begin(), V.end());

    for (auto c : V)
        cnt[c - 'a']++;

    char duplicate = 'a';
    for (int i = 0; i < 26; i++)
    {
        if (cnt[i] & 1)
        {
            duplicate += i;
            break;
        }
    }

    int n = V.size();
    int m = (n - 1) / 2;

    int i = 0, j = m + 1, d = 0;
    while (i <= m && j < n)
    {
        if (V[i++] == V[j])
            j++;
        else
            d++;
    }
    cout << duplicate << nl;
    for (int i = (d <= 1 ? m + 1 : 0); i < (d <= 1 ? n : m); i++)
        cout << V[i];

    return 0;
}

• Độ phức tạp: $O(n)$.

Bài 4. Mê cung

Hai bạn An và Bình cùng chơi trò chơi mê cung trong một công viên. Mê cung có dạng một bảng hình vuông kích thước $n \times n$, trong đó:

• Hàng được đánh số từ 1 đến $n$ (từ trên xuống dưới).
• Cột được đánh số từ 1 đến $n$ (từ trái sang phải).
• Ô tại hàng $i$, cột $j$ chứa số nguyên $a_{ij}$, với:
  • $a_{ij} = 1$ → Có cánh cửa thần kỳ, đưa người chơi đến hàng $j$.
  • $a_{ij} = 0$ → Không có cánh cửa nào.

Mỗi hàng có ít nhất một cánh cửa và không có cánh cửa nào đưa người chơi đến chính hàng đó.

Luật chơi:

• An bắt đầu ở hàng $1$, Bình bắt đầu ở hàng $n$.
• Cả hai đồng thời chọn một ô có cánh cửa để đi đến một hàng khác.
• Nếu không gặp nhau, mỗi người tiếp tục chọn một cánh cửa mới để di chuyển.
• Quá trình này lặp lại cho đến khi hai bạn gặp nhau tại cùng một hàng.

Yêu cầu

Xác định số lần chọn ô có cánh cửa ít nhất để An và Bình gặp nhau tại một hàng trong mê cung.

Dữ liệu

File đầu vào: MAZE.INP

• Dòng 1: Một số nguyên $n~(2 \leq n \leq 5 \times 10^3)$ – Kích thước mê cung.
• $n$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên $(a_{i1}, a_{i2}, \dots, a_{in})$, mỗi số là $0$ hoặc $1$, không có dấu cách giữa các số.

Kết quả

File đầu ra: MAZE.OUT

• Ghi một số nguyên duy nhất – số lần chọn ô có cánh cửa ít nhất để hai bạn gặp nhau.
• Luôn có ít nhất một phương án để gặp nhau.

Ví dụ

Ràng buộc

• 60% số test ứng với 60% số điểm, có $n \leq 10^2$.
• 30% số test ứng với 30% số điểm, có $n \leq 2 \times 10^3$.
• 10% số test ứng với 10% số điểm, có $n \leq 5 \times 10^3$.

Lời giải

Ý tưởng chính là ta sẽ xét tất cả các hàng mà cả An và Bình đều có thể đi đến với ít nhất $k$ lần chọn cửa, và sau đó đưa ra hàng với giá trị $k$ nhỏ nhất.

Vậy ta sẽ cần tính toán với mỗi hàng $i ~ (1 \le i \le n)$, An cần mở ít nhất bao nhiêu cách cửa để đi từ hàng $1 \to i$ và Bình cần mở ít nhất bao nhiêu cách cửa để đi từ hàng $n \to i$. Nếu số lần mở cửa để đi đến hàng $i$ của 2 bạn là như nhau thì ta sẽ xét hàng đó.

Vậy làm sao để biết An/Bình cần ít nhất bao nhiêu cánh cửa để đến $i$?

Ta biết rằng, từ hàng $i$ có thể đi đến hàng $j$ nếu như hàng $i$ có cánh cửa tại vị trí $j$.

Ta có thể đưa bài toán về dạng đồ thị và giải quyết một cách dễ dàng. Với ví dụ ở đề bài, ta có đồ thị như sau:

Mỗi đỉnh là biểu diễn một hàng, mỗi cạnh đại diện cho hàng $i$ có cửa đến hàng $j$.

Vậy ta chỉ cần duyệt DFS 2 lần:

• An: Bắt đầu từ đỉnh $1$ đến các đỉnh khác.
• Bình: Bắt đầu từ đỉnh $n$ đến các đỉnh khác.

Rồi sau đó so sánh để đưa ra kết quả là xong.

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

const int inf = 1e9;
int n;
vector<vector<int>> adj;
vector<int> dAn, dBinh;

void bfs(int s, vector<int> &d)
{
    d.assign(n + 1, inf);
    vector<bool> visited(n + 1, false);
    queue<int> q;

    q.push(s);
    d[s] = 0;
    visited[s] = true;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();

        for (int v : adj[u])
        {
            if (!visited[v])
            {
                visited[v] = true;
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
}

int main()
{
    cin >> n;
    adj.resize(n + 1);

    for (int i = 1; i <= n; i++)
    {
        string a;
        cin >> a;
        for (int j = 0; j < n; j++)
        {
            if (a[j] == '1')
                adj[i].push_back(j + 1);
        }
    }

    bfs(1, dAn);
    bfs(n, dBinh);

    int ans = inf;
    for (int i = 1; i <= n; i++)
    {
        if (dAn[i] != inf && dAn[i] == dBinh[i])
            ans = min(ans, dAn[i]);
    }

    cout << ans;
    return 0;
}

• Độ phức tạp: $O(n)$. Nhưng bước nhập dữ liệu đã là $O(n^2)$.