Đề thực hành số 1

BÀI 1: CHINH PHỤC HỌC BỔNG

Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 256 MB

Mô tả bài toán

Bạn A đang lên kế hoạch học tập để đạt học bổng của trường Đại học Công nghệ Thông tin (UIT) ở học kỳ thứ $m$ . Điểm tổng kết được tính trên thang điểm 10. Ở học kỳ đầu tiên (kỳ 1), điểm tổng kết của A là một số thực $x$ .

Dựa vào lịch học, A lập ra một danh sách dự đoán phong độ của bản thân cho các học kỳ tiếp theo (từ kỳ 2 đến kỳ $m$ ). Trạng thái phong độ sẽ quyết định công thức tính điểm của kỳ đó dựa trên điểm của kỳ ngay trước nó:

Trạng thái 1 (Phong độ tốt): Điểm của kỳ này sẽ có xu hướng tăng cao. Cụ thể, điểm mới bằng trung bình cộng có trọng số giữa điểm kỳ trước (nhân hệ số 2) và điểm tuyệt đối 10.0: Điểm kỳ hiện tại = (Điểm kỳ trước * 2.0 + 10.0) / 3.0.

Trạng thái 0 (Phong độ không tốt): Điểm của kỳ này sẽ bị sụt giảm 20% so với kỳ trước: Điểm kỳ hiện tại = Điểm kỳ trước * 0.8.

Yêu cầu: Cho biết kỳ mục tiêu $m$ , điểm kỳ đầu tiên $x$ , điểm chuẩn học bổng của kỳ mục tiêu là $y$ , và danh sách trạng thái phong độ từ kỳ 2 đến kỳ $m$ . Hãy viết chương trình tính điểm của bạn A ở học kỳ thứ $m$ (làm tròn đến 2 chữ số thập phân) và xác định xem A có đủ điểm để đạt học bổng hay không.

Đầu vào (Input)

Dòng thứ nhất chứa 1 số nguyên $m$ và 2 số thực $x$ , $y$ cách nhau bởi khoảng trắng.
Dòng thứ hai chứa $m - 1$ số nguyên (chỉ nhận giá trị 0 hoặc 1), biểu diễn trạng thái phong độ lần lượt của kỳ 2, kỳ 3, ..., kỳ $m$ .
Điều kiện: $2 \le m \le 20$ ; $0.0 \le x, y \le 10.0$ .

Đầu ra (Output)

Dòng đầu tiên in ra điểm số dự đoán của A ở học kỳ thứ $m$ , được làm tròn chính xác 2 chữ số thập phân.
Dòng thứ hai in ra YES nếu điểm số dự đoán lớn hơn hoặc bằng $y$ , ngược lại in ra NO.

Ví dụ

Input

4 8.0 8.5
1 0 1

Output

7.96
NO

Giải thích

Học kỳ 1 (Chưa có trạng thái): Điểm = 8.0.
Học kỳ 2 (Trạng thái 1): Điểm = (8.0 * 2.0 + 10.0) / 3.0 = 8.666...
Học kỳ 3 (Trạng thái 0): Điểm = 8.666... * 0.8 = 6.933...
Học kỳ 4 (Trạng thái 1): Điểm = (6.933... * 2.0 + 10.0) / 3.0 = 7.955...

Làm tròn 2 chữ số thập phân, điểm ở kỳ 4 là 7.96.

Vì 7.96 < 8.5 (điểm chuẩn $y$ ), nên kết quả in ra là NO.

Code mẫu (Đệ quy)

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

vector<int> states;

double calc(int n, double x) {
    if (n == 1) return x;

    double prev = calc(n - 1, x);

    if (states[n - 2] == 1)
        return (prev * 2 + 10) / 3;
    else
        return prev * 0.8;
}

int main() {
    int m;
    double x, y;
    cin >> m >> x >> y;

    states.resize(m - 1);
    for (int i = 0; i < m - 1; i++) cin >> states[i];

    double res = calc(m, x);

    cout << fixed << setprecision(2) << res << endl;
    cout << (res >= y ? "YES" : "NO");
}

Code mẫu (Không đệ quy)

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

int main() {
    int m;
    double x, y;
    cin >> m >> x >> y;

    vector<int> states(m - 1);
    for (int i = 0; i < m - 1; i++) cin >> states[i];

    double score = x;

    for (int i = 0; i < m - 1; i++) {
        if (states[i] == 1)
            score = (score * 2 + 10) / 3;
        else
            score = score * 0.8;
    }

    cout << fixed << setprecision(2) << score << endl;
    cout << (score >= y ? "YES" : "NO");
}

BÀI 2: SÚNG MÁY CANON

Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 256 MB

Mô tả bài toán

Trong một trò chơi đấu thẻ bài, bạn đang úp lá bài bẫy trứ danh có tên là Súng máy Canon. Để kích hoạt lá bẫy này, hệ thống yêu cầu bạn thực hiện chính xác một chuỗi hành động:

Bước 1: Chọn ra 1 quái thú Xyz và 1 quái thú Synchro sao cho tổng số sao của chúng bằng đúng số sao của quái thú chủ lực trên sân đối phương.
Bước 2: Chọn tiếp 1 quái thú Xyz khác trong danh sách còn lại của bạn. Quái thú này bắt buộc phải có số sao bằng đúng với quái thú Xyz đã chọn ở Bước 1.
Bước 3: Tổng số sao của cả ba quái thú được chọn làm vật tế phải bằng đúng tổng số lượng lá bài hiện tại trong trận đấu.

Trong game, mọi quái thú đều phải có số sao từ 1 đến 12. Hệ thống của trò chơi cung cấp cho bạn các thông số sau:

$N$ : Tổng số lá bài trong trận đấu.
$M$ : Số sao của quái thú chủ lực đối phương.
$K$ : Số lượng lá bài bạn đang có thể sử dụng làm nguyên liệu vật tế.

Danh sách $K$ lá bài của bạn. Mỗi lá bài được định nghĩa bởi 2 thuộc tính: Loại quái thú (0: Xyz, 1: Synchro, 2: Khác) và Số sao (từ 1 đến 12).

Yêu cầu: Cho trước thông số $N$ , $M$ và danh sách $K$ lá bài bạn đang có, hãy kiểm tra xem bạn có thể kích hoạt Súng máy Canon hay không.

Đầu vào (Input)

Dòng đầu tiên: số nguyên $T$ là số lượng test case (1 ≤ T ≤ 1000).
Với mỗi test case:
- Dòng 1: Ba số nguyên $N$ , $M$ , $K$ ( $1 \le N \le 36$ ; $1 \le M \le 12$ ; $1 \le K \le 100$ ).
- Dòng 2: Loại lá bài lần lượt của $K$ lá bài (0: Xyz, 1: Synchro, 2: Khác).
- Dòng 3: Số sao lần lượt của $K$ lá bài.

Đầu ra (Output)

In ra YES nếu có thể kích hoạt, ngược lại NO.

Ví dụ

Input

Output

YES
NO
NO

Giải thích

STT	Input	Output	Giải thích
1	$N=5, M=4$	YES	Chọn 2 Xyz sao 1 và 1 Synchro sao 3
2	$N=5, M=4$	NO	Thiếu 2 Xyz cùng số sao
3	$N=36, M=12$	NO	Giá trị sao không hợp lệ

Hướng dẫn giải

Dựa vào mô tả bài toán, ta thiết lập được hệ phương trình:

(1) $x + y = M$ (Bước 1)

(2) $x + y + x = N$ (Bước 2 & 3) $\Leftrightarrow$ $2x + y = N$

Lấy (2) trừ (1) ta được: $x = N - M$ .

Thay vào (1) ta được: $y = 2M - N$ .

Lưu ý : Hệ thống yêu cầu 1 quái thú Xyz đầu tiên và 1 quái thú Xyz khác làm lõi năng lượng mang cùng số sao $x$ . Tức là trong $K$ nguyên liệu, ta cần ít nhất 2 quái thú Xyz mang số sao $x$ và 1 quái thú Synchro mang số sao $y$ . Ta phải sử dụng mảng tần số để đếm chính xác số lượng từng loại lá bài.

Thuật toán giải:

Tính $x$ và $y$ từ $N$ và $M$ . Nếu một trong hai giá trị không thuộc đoạn [1, 12], in NO.
Duyệt qua $K$ lá bài, dùng mảng count_xyz[13] và count_synchro[13] đếm số lượng nguyên liệu hiện có.
Kiểm tra điều kiện: if (count_xyz[x] >= 2 && count_synchro[y] >= 1) thì in YES, ngược lại in NO.

Code mẫu (C++)

#include <iostream>
#include <vector>
using namespace std;

void solve() {
    long long N;
    int M, K;
    cin >> N >> M >> K;

    vector<int> type(K), stars(K);
    for (int i = 0; i < K; i++) cin >> type[i];
    for (int i = 0; i < K; i++) cin >> stars[i];

    long long x_req = N - M;
    long long y_req = 2LL * M - N;

    if (x_req < 1 || x_req > 12 || y_req < 1 || y_req > 12) {
        cout << "NO\n";
        return;
    }

    int x = (int)x_req;
    int y = (int)y_req;

    int count_xyz[13] = {0};
    int count_synchro[13] = {0};

    for (int i = 0; i < K; i++) {
        if (type[i] == 0) count_xyz[stars[i]]++;
        else if (type[i] == 1) count_synchro[stars[i]]++;
    }

    if (count_xyz[x] >= 2 && count_synchro[y] >= 1) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while (T--) solve();
}

BÀI 3: MẢNH GHÉP LINH DỊ

Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 256 MB

Mô tả bài toán

Thế giới của A bị một thế lực linh dị bí ẩn xâm lấn, đem lại nguồn sức mạnh kì lạ mà con người có thể hấp thụ để trở nên mạnh mẽ. Đáng tiếc, những sức mạnh này không ở trạng thái hoàn chỉnh mà bị chia tách thành các phần khác nhau rải rác ở khắp mọi nơi, gọi là các “mảnh ghép linh dị”.

Các yếu tố linh dị được biểu diễn bằng các kí tự 'a', 'b', 'c', 'd', 'e', 'f', 'g'. Một mảnh ghép linh dị gồm có phần đầu và phần đuôi, được tạo thành từ hai trong các yếu tố linh dị trên (Ví dụ: "ab", "ba", "bc", "ag", "gc",... là các mảnh ghép linh dị).

Hấp thụ mảnh ghép linh dị sẽ tạo ra một chuỗi năng lượng mới trong cơ thể. Để tránh mất cân bằng sức mạnh trong cơ thể, việc hấp thụ một mảnh ghép linh dị mới cần tuân theo quy luật khắt khe như sau: yếu tố linh dị phần đuôi của chuỗi năng lượng trong cơ thể phải giống với yếu tố linh dị phần đầu của mảnh ghép cần hấp thụ.

Ví dụ: Nếu A đã hấp thụ hai mảnh ghép là "ab" và "ba", cậu tạo ra chuỗi năng lượng "aba" trong cơ thể. Sau đó, cậu có thể hấp thụ tiếp mảnh "ab" (có thể dùng một loại mảnh ghép lại nhiều lần), tạo thành chuỗi năng lượng "abab".

Giả sử chuỗi năng lượng chứa sức mạnh linh dị hoàn chỉnh mà A mong muốn là chuỗi $s$ . Hãy giúp A tính toán xem cậu cần phải tìm và hấp thụ tối thiểu bao nhiêu loại mảnh ghép linh dị khác nhau để có thể tạo ra chuỗi năng lượng đó.

Đầu vào (Input)

Dòng đầu tiên chứa một số nguyên $t$ ( $1 \le t \le 10^4$ ) — số lượng test cases.

Tiếp theo là mô tả của các test cases:

Dòng thứ nhất của mỗi test case chứa một số nguyên $n$ ( $2 \le n \le 50$ ) — độ dài của chuỗi sức mạnh $s$ .
Dòng thứ hai của mỗi test case chứa một chuỗi $s$ có độ dài $n$ , chỉ bao gồm các ký tự 'a', 'b', 'c', 'd', 'e', 'f', 'g'.

Đầu ra (Output)

In ra $t$ số nguyên, mỗi số là đáp án cho một test case tương ứng nằm trên một dòng. Đáp án là số lượng tối thiểu các loại mảnh ghép linh dị mà A cần phải hấp thụ.

Ví dụ

Input:

4
4
abab
7
abacaba
6
aaaaaa
5
babdd

Output:

Giải thích

STT	Input	Output	Giải thích
1	`4` `abab`	2	Chuỗi năng lượng được tạo từ các mảnh: "ab", "ba", "ab". Có 2 loại khác nhau là "ab" và "ba".
2	`7` `abacaba`	4	Các mảnh liên tiếp: "ab", "ba", "ac", "ca", "ab", "ba". Có 4 loại khác nhau: "ab", "ba", "ac", "ca".
3	`6` `aaaaaa`	1	Chỉ dùng một loại mảnh ghép duy nhất là "aa" lặp lại nhiều lần.
4	`5` `babdd`	4	Các mảnh liên tiếp: "ba", "ab", "bd", "dd". Có 4 loại khác nhau.

Hướng dẫn giải

Bài toán yêu cầu tìm số lượng tối thiểu các loại mảnh ghép cần thiết. Vì một loại mảnh ghép có thể sử dụng lại vô hạn lần, bài toán thực chất là: Đếm số lượng các chuỗi con độ dài 2 khác nhau xuất hiện trong chuỗi $s$ .

Thuật toán:

Sử dụng một Set (tập hợp) để lưu trữ các chuỗi con.
Duyệt qua chuỗi s từ đầu đến kế cuối, cắt mỗi cặp ký tự liên tiếp s[i]s[i+1] và thêm vào Set.
Kết quả là kích thước của Set.

Code mẫu (C++)

#include <iostream>
#include <string>
#include <unordered_set>

using namespace std;

void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;

    unordered_set<string> unique_fragments;
    for (int i = 0; i < n - 1; ++i) {
        unique_fragments.insert(s.substr(i, 2));
    }

    cout << unique_fragments.size() << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

BÀI 4: CÒ CẦU THỦ

Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 256 MB

Mô tả bài toán

Trên thị trường chuyển nhượng của tựa game đá bóng trực tuyến, việc “săn” những cầu thủ quốc dân chất lượng hoặc các mùa thẻ hiếm là vô cùng khó khăn. Bạn là một "cò" cầu thủ khét tiếng, chuyên nhận các hợp đồng săn cầu thủ trên thị trường.

Hôm nay, bạn nhận được $N$ đơn đặt hàng từ các HLV khác nhau. Đơn hàng thứ $i$ yêu cầu bạn săn một cầu thủ cụ thể. Nếu thành công, bạn sẽ nhận được tiền công là $p_i$ triệu BP. Tuy nhiên, thị trường biến động rất nhanh, đơn hàng thứ $i$ chỉ có hiệu lực trong vòng $d_i$ giờ tới (tính từ thời điểm hiện tại).

Biết rằng, thao tác canh cầu thủ để chốt đơn mất rất nhiều thời gian, nên trong mỗi một giờ, bạn chỉ có thể hoàn thành $1$ đơn hàng. Bạn có thể thực hiện đơn hàng thứ $i$ ở bất kỳ giờ nào từ $1$ đến $d_i$ .

Yêu cầu: Hãy lựa chọn và sắp xếp thứ tự thực hiện các đơn hàng sao cho tổng số tiền công (BP) bạn thu về là lớn nhất.

Đầu vào (Input)

Dòng đầu tiên chứa số nguyên dương $N$ ( $1 \le N \le 100000$ ) — số lượng đơn đặt hàng.
$N$ $N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $d_i, p_i$ $d_{i}, p_{i}$ :
- $1 \le d_i \le 100000$ (thời hạn)
- $1 \le p_i \le 10^9$ (tiền công)

Đầu ra (Output)

In ra một số nguyên duy nhất là tổng tiền công lớn nhất (triệu BP) mà bạn có thể kiếm được.

Ví dụ

Input 1

Output 1

Input 2

Output 2

Giải thích

STT	Input	Output	Giải thích
1	`4` `4 20` `1 10` `1 40` `1 30`	60	Có 3 đơn deadline = 1, chọn đơn có profit lớn nhất (40). Đơn (4,20) làm sau → tổng = 60
2	`5` `2 100` `1 19` `2 27` `1 25` `3 15`	142	Sắp xếp và chọn tối ưu: (1,25), (2,100), (3,15) → tổng = 142

Hướng dẫn giải

Đây là bài toán tối ưu hóa điển hình sử dụng tham lam + hàng đợi ưu tiên (priority_queue).

Ý tưởng

Sắp xếp các đơn hàng theo deadline tăng dần.
Dùng Min-Heap để lưu tiền công các đơn đã chọn.
Duyệt từng đơn:
- Thêm tiền công vào heap.
- Nếu số đơn đã chọn > deadline hiện tại → loại bỏ đơn có tiền công nhỏ nhất.

Chạy tay thuật toán

Sử dụng dữ liệu Ví dụ 2:

$N = 5$
Các đơn hàng $(D_i, P_i)$ $(D_{i}, P_{i})$ :
- $(2, 100)$
- $(1, 19)$
- $(2, 27)$
- $(1, 25)$
- $(3, 15)$

Bước 1: Sắp xếp theo $D_i$ tăng dần

Đơn A: $(1, 19)$
Đơn B: $(1, 25)$
Đơn C: $(2, 100)$
Đơn D: $(2, 27)$
Đơn E: $(3, 15)$

Bước 2: Duyệt và xử lý với Min-Heap

Bước	Đơn xét	Thao tác Heap	Trạng thái Heap (Tiền công)	Giải thích
1	A(1, 19)	Push 19	[19]	Size (1) ≤ Deadline (1). Hợp lệ.
2	B(1, 25)	Push 25, Pop 19	[25]	Size (2) > Deadline (1). Loại bỏ đơn rẻ nhất (19).
3	C(2, 100)	Push 100	[25, 100]	Size (2) ≤ Deadline (2). Hợp lệ.
4	D(2, 27)	Push 27, Pop 25	[27, 100]	Size (3) > Deadline (2). Loại bỏ đơn rẻ nhất (25).
5	E(3, 15)	Push 15	[15, 27, 100]	Size (3) ≤ Deadline (3). Hợp lệ.

Bước 3: Kết quả

Tổng tiền công lớn nhất:

15 + 27 + 100 = 142

( triệu BP )

Code mẫu (C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct Order {
    int deadline;
    long long profit;
};

bool compareOrders(Order a, Order b) {
    return a.deadline < b.deadline;
}

void solve() {
    int n;
    cin >> n;

    vector<Order> orders(n);
    for (int i = 0; i < n; i++) {
        cin >> orders[i].deadline >> orders[i].profit;
    }

    sort(orders.begin(), orders.end(), compareOrders);

    priority_queue<long long, vector<long long>, greater<long long>> min_heap;

    for (int i = 0; i < n; i++) {
        min_heap.push(orders[i].profit);

        if (min_heap.size() > orders[i].deadline) {
            min_heap.pop();
        }
    }

    long long total = 0;
    while (!min_heap.empty()) {
        total += min_heap.top();
        min_heap.pop();
    }

    cout << total << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solve();
    return 0;
}

BÀI 1: CHINH PHỤC HỌC BỔNG​

Mô tả bài toán​

Đầu vào (Input)​

Đầu ra (Output)​

Ví dụ​

Giải thích​

Code mẫu (Đệ quy)​

Code mẫu (Không đệ quy)​

BÀI 2: SÚNG MÁY CANON​

Mô tả bài toán​

Đầu vào (Input)​

Đầu ra (Output)​

Ví dụ​

Giải thích​

Hướng dẫn giải​

Code mẫu (C++)​

BÀI 3: MẢNH GHÉP LINH DỊ​

Mô tả bài toán​

Đầu vào (Input)​

Đầu ra (Output)​

Ví dụ​

Giải thích​

Hướng dẫn giải​

Code mẫu (C++)​

BÀI 4: CÒ CẦU THỦ​

Mô tả bài toán​

Đầu vào (Input)​

Đầu ra (Output)​

Ví dụ​

Giải thích​

Hướng dẫn giải​

Ý tưởng​

Chạy tay thuật toán​

Code mẫu (C++)​

BÀI 1: CHINH PHỤC HỌC BỔNG

Mô tả bài toán

Đầu vào (Input)

Đầu ra (Output)

Ví dụ

Giải thích

Code mẫu (Đệ quy)

Code mẫu (Không đệ quy)

BÀI 2: SÚNG MÁY CANON

Mô tả bài toán

Đầu vào (Input)

Đầu ra (Output)

Ví dụ

Giải thích

Hướng dẫn giải

Code mẫu (C++)

BÀI 3: MẢNH GHÉP LINH DỊ

Mô tả bài toán

Đầu vào (Input)

Đầu ra (Output)

Ví dụ

Giải thích

Hướng dẫn giải

Code mẫu (C++)

BÀI 4: CÒ CẦU THỦ

Mô tả bài toán

Đầu vào (Input)

Đầu ra (Output)

Ví dụ

Giải thích

Hướng dẫn giải

Ý tưởng

Chạy tay thuật toán

Code mẫu (C++)