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

Author Hung Nguyen Tuong

Bài 1. Số đặc biệt

Minh là một người rất yêu thích số nguyên tố, đồng thời cậu cũng rất thích số $5$. Do đó, cậu ta luôn coi những số nguyên tố có tổng các chữ số chia hết cho $5$ là số đặc biệt. Lần này, thầy giáo cho Minh hai số nguyên dương $L,R \ (L \le R)$ và muốn Minh cho biết trong đoạn $[L,R]$ có bao nhiêu số đặc biệt.

Yêu cầu

Bạn hãy lập trình tìm câu trả lời giúp Minh.

Dữ liệu

Vào từ tệp văn bản sprime.inp có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương $T \le 10^5$ là số lượng cặp số nguyên $L, R$ cần trả lời.
• $T$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L, R \ (0 < L \le R \le 3*10^6)$ phân biệt nhau bởi một dấu cách.

Kết quả

Ghi ra tệp văn bản sprime.out gồm $T$ dòng, mỗi dòng ghi một số nguyên là số lượng số đặc biệt trong đoạn $[L,R]$ tương ứng với thứ tự dữ liệu đầu vào.

Ví dụ

Ràng buộc

• Có $40\%$ số test ứng với $40\%$ số điểm của bài thoả mãn: $T=1; \ 0 < L,R \le 10^3$.
• $30\%$ số test khác ứng với $30\%$ số điểm của bài thoả mãn: $2 \le T \le 10; \ 0 < L,R \le 10^5$.
• $30\%$ số test ứng với $30\%$ số điểm của bài thoả mãn: $T \le 10^5; \ 0 < L,R \le 3*10^6$.

Lời giải

Sử dụng Sàng Eratosthenes và mảng cộng dồn.

Giả sử $\text{pref}[i]$ là số lượng số đặc biệt từ $1 \to i$.

⇒ Số lượng số đặc biệt trong khoảng $[L,R]$ là $\text{pref}[R] - \text{pref}[L-1]$.

Độ phức tạp: $O(R \times \log (\log R) + T)$.

Code

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

const int maxn = 3 * 1e6 + 1;
vector<int> pref(maxn + 1, 0);
vector<bool> sieve(maxn + 1, true);
void sang_nguyen_to()
{
    sieve[0] = sieve[1] = false;
    for (int i = 2; i * i <= maxn; i++)
    {
        if (sieve[i])
        {
            for (int j = i * i; j <= maxn; j += i)
            {
                sieve[j] = false;
            }
        }
    }
    for (int i = 2; i <= maxn; i++)
    {
        if (!sieve[i])
        {
            pref[i] = pref[i - 1];
            continue;
        }
        int d_sum = 0, num = i;
        while (num != 0)
        {
            d_sum += num % 10;
            num /= 10;
        }
        pref[i] = pref[i - 1] + (d_sum % 5 == 0);
    }
}
int main()
{
    sang_nguyen_to();

    int t;
    cin >> t;
    while (t--)
    {
        int l, r;
        cin >> l >> r;
        cout << pref[r] - pref[l - 1] << nl;
    }
    return 0;
}

Bài 2. Luyện thi

Để chuẩn bị cho hội thi Tin học trẻ sắp tới, thầy giáo quyết định giao một bộ đề thi gồm $N$ đề thi khác nhau cho Minh để tự luyện tập.

Các đề thi được đánh số từ $1$ đến $N$, mỗi đề thi sẽ giúp rèn luyện một số kỹ năng cho Minh để có thể đạt thành tích tốt trong hội thi Tin học trẻ.

Nhằm định hướng cho quá trình luyện tập đạt hiệu quả cao nhất, mỗi đề thi có một yêu cầu tối thiểu về trình độ kỹ năng.

Để giải được đề thi $i$, Minh cần có trình độ kĩ năng tối thiểu là $a_i$. Điều này có nghĩa là Minh có thể giải được đề thi thứ $i$ khi và chỉ khi có trình độ kỹ năng bằng hoặc lớn hơn $a_i$. Nếu giải được đề thi $i$ thì trình độ kỹ năng của Minh sẽ tăng thêm một lượng là $b_i$. Giả sử ban đầu, trình độ kỹ năng của Minh trước khi tập luyện là $c$.

Các đề thi có thể được giải theo trình tự bất kỳ.

Yêu cầu

Cho các số nguyên $N,c$ và các cặp giá trị $(a_i,b_i)$, hãy xác định số lượng đề thi tối đa mà Minh có thể giải được.

Dữ liệu

Vào từ tệp văn bản practice.inp có cấu trúc như sau:

• Dòng đầu tiên chứa hai số nguyên $N,c \ ( \le N \le 10^5, \ 0 \le c \le 10^9)$.
• Dòng thứ $i$ trong $N$ dòng tiếp theo $(1 \le i \le N)$ chứa 2 số nguyên $a_i$ và $b_i \ (1 \le a_i,b_i \le 10^9)$. Các số trên cùng một dòng được phân cách nhau bởi một dấu cách.

Kết quả

Ghi ra tệp văn bản practice.out một số nguyên dương, là số đề thi tối đa mà Minh có thể giải được.

Ví dụ

Giải thích: Với $N=4,c=1$ và các cặp giá trị $(a_i,b_i)$ tương ứng là $(1,10),(21,5),(1,10),(100,100)$, Minh sẽ giải đề thi 1 sau đó giải đề thi 3 và cuối cùng giải đề thi 2. Đề thi 4 Minh không giải được vì không đủ kỹ năng. Như vậy, Minh giải tối đa 3 đề thi.

Ràng buộc

• Có $60\%$ số test ứng với $60\%$ số điểm của bài thoả mãn: $N \le 1000, \ (1 \le a_i,b_i \le 10^5)$.
• $40\%$ số test còn lại ứng với $40\%$ số điểm của bài toán 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'

bool cmp(pair<ll, ll> p1, pair<ll, ll> p2)
{
    return p1.first < p2.first;
}
int main()
{
    int n;
    cin >> n;
    ll c;
    cin >> c;
    vector<pair<ll, ll>> v(n);
    for (int i = 0; i < n; i++)
    {
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end(), cmp);
    int ans = 0;
    for (auto i : v)
    {
        if (c >= i.first)
        {
            ans++;
            c += i.second;
        }
    }
    cout << ans;
    return 0;
}

Bài 3. Mật khẩu

Do ảnh hưởng của đại dịch Covid-19, ban tổ chức hội thi Tin học trẻ dự kiến sẽ cho các thí sinh thi theo hình thức trực tuyến.

Để tham gia thi, thí sinh sẽ được cung cấp một tài khoản và mật khẩu để đăng nhập. Để đảm bảo yếu tố bảo mật, ban tổ chức yêu cầu các thí sinh phải thay đổi mật khẩu ngay sau khi nhận được.

Mật khẩu được coi là “an toàn” nếu thỏa mãn đồng thời các điều kiện sau:

• Có độ dài tối thiểu là 6.
• Chứa ít nhất 1 chữ cái in hoa $('A','B',...,'Z')$.
• Chứa ít nhất 1 chữ cái in thường $('a','b',...,'z')$.
• Chứa ít nhất 1 chữ số $('0','1',...,'9')$.

Ví dụ: các xâu kí tự: $"a1B2C3", "Tinhoc12"$ là các mật khẩu an toàn, còn các xâu kí tự: $"a1B2C", "a1b2c3", "A1B2C3", "TinHoc"$ không phải là mật khẩu an toàn.

Cho một xâu kí tự $S$ chỉ gồm các loại kí tự: chữ cái in hoa, chữ cái in thường và chữ số. Hãy cho biết có bao nhiêu cặp chỉ số $(i,j)$ thoả mãn đồng thời hai điều kiện:

• $1 \le i < j \le |S|$, trong đó $|S|$ là độ dài xâu $S$, $0 \le |S| \le 10^5$.
• Xâu con $S_{ij}$ gồm các kí tự liên tiếp từ chỉ số $i$ đến $j$ của xâu $S$ là mật khẩu an toàn.

Yêu cầu

Cho xâu kí tự $S$, tính số lượng cặp $(i,j)$ thoả mãn hai điều kiện trên.

Dữ liệu

Vào từ tệp văn bản password.inp gồm một dòng chứa xâu kí tự $S$.

Kết quả

Ghi ra tệp văn bản password.out một số nguyên dương là số lượng cặp chỉ số $(i,j)$ thoả mãn điều kiện xâu con $S_{ij}$ là mật khẩu an toàn.

Ví dụ

Ràng buộc

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

Lời giải

Sử dụng mảng cộng dồn và 2 con trỏ.

Khai báo các mảng:

• $\text{thg}[i]$: số ký tự chữ cái in thường từ đầu đến vị trí $i$.
• $\text{hoa}[i]$: số ký tự chữ cái in hoa từ đầu đến vị trí $i$.
• $\text{so}[i]$: số chữ số từ đầu đến vị trí $i$.

Cùng xem xét lại các điều kiện của mật khẩu an toàn. Giả sử một mật khẩu là dãy con của xâu đoạn $(i,j)$, mật khẩu đó an toàn khi:

• Độ dài tối thiểu là 6: $j-i+1 \ge 6$.
• Ít nhất 1 chữ cái in hoa: $\text{hoa}[j] - \text{hoa}[i-1] \ge 1$.
• Ít nhất 1 chữ cái in thường: $\text{thg}[j] - \text{thg}[i-1] \ge 1$.
• Ít nhất 1 chữ số: $\text{so}[j] - \text{so}[i-1] \ge 1$.

⇒ Ta biết nếu đoạn $(i,j)$ là một mật khẩu an toàn thì $(i-1,j), (i-2,j), (i-3,j), ..., (1,j)$ cũng phải là các mật khẩu an toàn.

Vậy thì với mỗi mật khẩu kết thúc tại vị trí $j$, ta sẽ cần tìm vị trí $i$ gần $j$ nhất sao cho thoả mãn tất cả điều kiện biên của mật khẩu an toàn.

⇒ Số lượng mật khẩu an toàn kết thúc tại $j$ là: $i$.

Độ phức tạp: $O(n)$, với $n$ là độ dài xâu $s$.

Code

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

const int maxn = 1e5 + 1;
int thg[maxn], hoa[maxn], so[maxn];

bool safe(int i, int j)
{
    return (j - i + 1 >= 6) &&
           (thg[j] - thg[i - 1] >= 1) &&
           (hoa[j] - hoa[i - 1] >= 1) &&
           (so[j] - so[i - 1] >= 1);
}

ll solve()
{
    string s;
    cin >> s;
    int n = s.size();

    if (n < 6)
        return 0;

    thg[0] = hoa[0] = so[0] = 0;

    for (int i = 0; i < n; i++)
    {
        thg[i + 1] = thg[i] + ('a' <= s[i] && s[i] <= 'z');
        hoa[i + 1] = hoa[i] + ('A' <= s[i] && s[i] <= 'Z');
        so[i + 1] = so[i] + ('0' <= s[i] && s[i] <= '9');
    }

    if (thg[n] * hoa[n] * so[n] == 0)
        return 0;

    int i = 1;
    ll ans = 0;

    for (int j = 6; j <= n; j++)
    {
        if (thg[j] * hoa[j] * so[j] == 0)
            continue;
        while (safe(i, j))
            i++;
        if (safe(i - 1, j))
            ans += i - 1;
    }

    return ans;
}
int main()
{
    cout << solve();
    return 0;
}

Bài 4. Lát nền

Viện Công nghệ thông tin đang được tu sửa và nâng cấp. Một trong những hạng mục công việc là lát lại hành lang nối từ phòng làm việc sang phòng đặt máy chủ.

Hành lang có độ rộng $2$ và độ dài $n$ được biểu thị như một lưới ô vuông gồm $2$ hàng và $n$ cột.

Để lát người ta dùng các viên gạch men loại kích thước $1\times 1$ và $1 \times 2$ với số lượng dự trữ không hạn chế. Các viên gạch $1 \times 2$ có thể lát dọc hoặc xoay ngang.

Trước đây hành lang được lát bằng các viên gạch kích thước $1 \times 1$ và có $k \ (k=0$ hoặc $k=1)$ viên gạch được lắp dưới các thiết bị điện tử. Nếu $k=1$ thì viên gạch ở hàng $r$ cột $c$.

Ban Giám đốc viện không muốn lắp lại hệ thống điện tử vốn đang hoạt động rất tốt, nên yêu cầu đánh dấu viên gạch này và không được bóc lên trong quá trình lát nền.

Bộ phận thi công phàn nàn về yêu cầu trên, vì như thế sẽ hạn chế khả năng lát. Điều này làm Trưởng phòng vật tư đề nghị bộ phận lập trình tính số phương án lát nền khác nhau mà vẫn đảm bảo yêu cầu đã nêu, để bên thi công thấy có nhiều cách làm khác nhau.

Yêu cầu

Bạn hãy tính và đưa ra số phương án lát nền theo module $10^9 + 7$ (tức là đưa ra số dư của số phương án lát nền chia cho $10^9 + 7$).

Hai phương án gọi là khác nhau nếu tồn tại hai ô kề cạnh trong phương án này được phủ bằng một viên gạch $1 \times 2$, còn theo phương án kia thì không được phủ bằng một viên gạch $1 \times 2$.

Ví dụ: với $n=2,\ k=0$ (không có viên gạch kích thước $1 \times 1$ nào được đánh dấu), ta có $7$ phương án lát nền như minh hoạ trong hình dưới đây:

Ví dụ khác: với $n=3, \ k = 1$ viên gạch kích thước $1 \times 1$ được đánh dấu ở vị trí $(1,2)$ (ô được tô kín trong hình vẽ), ta có $8$ phương án lát nền như minh hoạ trong hình dưới đây:

Dữ liệu

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

• Dòng đầu tiên chứa số nguyên $n,k \ (1 \le n \le 10^5; \ k=0$ hoặc $k=1)$.
• Nếu $k=1$ thì dòng tiếp theo chứa hai số nguyên $r$ và $c \ (1 \le r \le 2; \ 1 \le c \le n)$.

Kết quả

Ghi ra tệp văn bản tili.out một số nguyên là số phương án lát nền theo module $10^9 + 7$.

Ví dụ

Ràng buộc

• Có $25\%$ số test ứng với $25\%$ số điểm của bài thoả mãn: $1 \le n \le 8; \ k=0$.
• $*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; \ k=0$.
• $25\%$ số test khác ứng với $25\%$ số điểm của bài thoả mãn: $1 \le n \le 10^5; \ k=0$.
• $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

Sử dụng Quy hoạch động. Xoay nền dọc để dễ quan sát hơn.

• Trường hợp 1: $k=0$

  Để lát nền ở hàng $n$, thì ta phải biết ở hàng $n-1$ có những trường hợp nào.

  Ta có những tập hợp sau:

  • $C$: Ta liệt kê được hàng $n-1$ có $4$ trường hợp. Gọi $C1$ là trường hợp đủ; $C2,C3,C4$ là các trường hợp thiếu.
  • $A$: Khi ta lát nền $1$ trong $5$ cách này vào những trường hợp $C$ phù hợp thì nền hàng $n$ sẽ đủ (đều tạo ra $C1$). Cụ thể:
    • $A1 \to C1$.
    • $A2 \to C1$.
    • $A3 \to C2$.
    • $A4 \to C3$.
    • $A5 \to C4$.
  • $B$: Khi ta lát nền $1$ trong $5$ cách này vào những trường hợp $C$ phù hợp thì nền hàng $n$ sẽ thiếu. Cụ thể:
    • $B1 \to C1 \Rightarrow C2$.
    • $B2 \to C1 \Rightarrow C3$.
    • $B3 \to C2 \Rightarrow C3$.
    • $B4 \to C3 \Rightarrow C2$.
    • $B5 \to B1 \Rightarrow C4$.

  Hãy cùng thử tính toán các trường hợp $n=0,1,2$:

  $n$	Các trường hợp $C$ được tạo ra
  0	$(C1)$
  1	$(C1 \ C1 \ C2 \ C3 \ C4)$
  2	$(C1 \ C1 \ C2 \ C3 \ C4), (C1 \ C1 \ C2 \ C3 \ C4), (C1 \ C3), (C1 \ C2), (C1)$

  ⇒ Ta thấy tại $n=2$ thì có tổng cộng $7$ trường hợp $C1$, nghĩa là có $7$ cách để lát đủ nền $2 \times 2$ bằng các viên $1 \times 1$ và $1 \times 2$.

• Trường hợp 2: $k=1$

  Hiểu được trường hợp $k=0$ thì $k=1$ rất đơn giản.

  Nếu $r=1$ (Ô nằm cột bên phải khi xoay dọc nền), thì ta sẽ chỉ tạo ra $C1$ và $C3$:

  • $A1 \to C1$.
  • $A4 \to C3$.
  • $B2 \to C1$.

  Nếu $r=2$ (Ô nằm cột bên trái khi xoay dọc nền), thì ta sẽ chỉ tạo ra $C1$ và $C2$:

  • $A1 \to C1$.
  • $A3 \to C2$.
  • $B1 \to C1$.

  Tổng kết lại bài toán: Kết quả chính là số trường hợp lát đủ nền ở hàng $n$ (số $C1$ được tạo ra tại hàng $n$).

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

Code

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

const int maxn = 1e5 + 5, m = 1e9 + 7;
ll c1[maxn], c2[maxn], c3[maxn], c4[maxn];
int main()
{
    int n, k;
    cin >> n >> k;
    int r = -1, c = -1;
    if (k == 1)
        cin >> r >> c;
    c1[0] = 1, c2[0] = c3[0] = c4[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        if (i != c)
        {
            c1[i] = ((((2 * (c1[i - 1] % m)) % m + c2[i - 1] % m) % m + c3[i - 1] % m) % m + c4[i - 1] % m) % m;
            c2[i] = (c1[i - 1] % m + c3[i - 1] % m) % m;
            c3[i] = (c1[i - 1] % m + c2[i - 1] % m) % m;
            c4[i] = c1[i - 1] % m;
        }
        else
        {
            if (r == 1)
            {
                c1[i] = (c1[i - 1] % m + c3[i - 1] % m) % m;
                c2[i] = 0;
                c3[i] = c1[i - 1] % m;
            }
            else
            {
                c1[i] = (c1[i - 1] % m + c2[i - 1] % m) % m;
                c2[i] = c1[i - 1] % m;
                c3[i] = 0;
            }
            c4[i] = 0;
        }
    }
    cout << c1[n] % m;
    return 0;
}