Học sinh giỏi 12 Thành phố Hồ Chí Minh 2023 - 2024¶

Bài 1: Xếp hạng¶

Đề bài¶

Trong kỳ thi lập trình có N đội tham dự được đánh số từ 1 đến N. Theo quy định của ban tổ chức, số điểm cuối cùng một đội nhận được là hai chỉ số $(a, b)$ lần lượt là số bài tập đội đó giải được và tổng số điểm phạt của tất cả các bài đã giải.

Điểm phạt cho một bài của mỗi đội được tính qua số lần nộp không thành công bài đó. Khi bắt đầu cuộc thi, tất cả các đội có điểm số là (0, 0).

Xét hai đội $X_1$ và $X_2$ lần lượt có điểm số là $(a_1, b_1)$ và $(a_2, b_2)$. Đội $X_1$ được xem là có điểm số tốt hơn đội $X_2$ khi hoặc $a_1 > a_2$ hoặc khi $a_1 = a_2$ và $b_1 < b_2$.

Một đội được xếp hạng $H$ nếu có $H - 1$ đội có điểm số tốt hơn đội đó.

Khi có một đội nộp thành công một bài, ban tổ chức sẽ thông báo cho tất cả các đội biết đội nào đã nộp thành công và điểm phạt cho bài nộp thành công của đội đó.

Bạn là thành viên của đội số 1 và muốn biết thứ hạng của đội mình mỗi khi có đội nộp thành công.

Yêu cầu: hãy viết một chương trình cho biết thứ hạng của đội 1 mỗi khi có đội nộp bài thành công.

Dữ liệu: XEPHANG.INP

Dòng đầu chứa hai số nguyên N, M lần lượt cho biết số đội tham dự và số lần các đội nộp bài thành công.
Mỗi dòng trong M dòng tiếp theo chứa hai số nguyên $T, P (1 \le T \le N; 1 \le P \le 1000)$ cho biết đội $T$ đã nộp một bài thành công và có điểm phạt cho bài nộp này là $P$.

Các lần thông báo được cho theo thứ tự thời gian nộp bài tăng dần.

Kết quả: XEPHANG.OUT

Với mỗi sự kiện nộp bài thành công, hãy xuất một số nguyên trên một dòng cho biết thứ hạng của đội 1 vào ngay sau thời điểm đó.

Ràng buộc:

40% số điểm của bài: $1 \le N, M \le 100$ và mỗi đội giải thành công tối đa một bài.
80% số điểm của bài: $1 \le N, M \le 1000$.
100% số điểm của bài: $1 \le N, M \le 100000$.

Ví dụ:

XEPHANG.INP	XEPHANG.OUT
3 5 2 4 3 2 1 3 1 8 2 7	2 3 2 1 1

Giải thích:

Sự kiện	Điểm đội 1	Điểm đội 2	Điểm đội 3	Hạng đội 1
(2, 4)	(0, 0)	(1, 4)	(0, 0)	2
(3, 2)	(0, 0)	(1, 4)	(1, 2)	3
(1, 3)	(1, 3)	(1, 4)	(1, 2)	2
(1, 8)	(2, 11)	(1, 4)	(1, 2)	1
(2, 7)	(2, 11)	(2, 11)	(1, 2)	1

Bài giải đề xuất¶

Ý tưởng chính là mỗi khi có một đội nộp bài thành công, ta sẽ cập nhật điểm số của đội đó và gọi một hàm để so sánh với đội 1 để xác định thứ hạng của đội 1.

Bước 0: Khai báo cấu trúc dữ liệu để lưu trữ thông tin của mỗi đội

C++Python

struct team
{
    int a;
    int b;

    // Mặc định a và b đều là 0
    team() : a(0), b(0) {}
};

class team:
    def __init__(self, a=0, b=0):
        self.a = a
        self.b = b

Bước 1: Viết hàm so sánh hai đội với nhau

C++Python

// Hàm dùng để so sánh đội T[1] với đội khác
// Trả về True nếu đội khác tốt hơn
bool is_another_team_better(const team& t1, const team& another)
{
    return t1.a < another.a || (t1.a == another.a && t1.b > another.b);
}

class team:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    # Hàm dùng để so sánh đội T[1] với đội khác
    # Trả về True nếu đội khác tốt hơn
    def is_another_team_better(self, another):
        if self.a < another.a or (self.a == another.a and self.b > another.b):
            return True
        return False

Bước 2: Viết hàm xếp hạng

C++Python

// Hàm dùng để xếp hạng đội T[1]
int process()
{
    // Khởi tạo đội T[1] hạng nhất
    int rank = 1;

    // Duyệt từng đội từ 1 đến n
    for (int i = 1; i < n + 1; ++i)
    {
        // Nếu đội T[i] nào đó tốt hơn đội T[1] thì tăng hạng đội T[1]
        if (i != 1 && is_another_team_better(T[1], T[i]))
        {
            rank += 1;
        }
    }

    return rank;
}

class team:
    def __init__(self, a=0, b=0):
        self.a = a
        self.b = b

    # Hàm dùng để so sánh đội T[1] với đội khác
    # Trả về True nếu đội khác tốt hơn
    def is_another_team_better(self, another):
        if self.a < another.a or (self.a == another.a and self.b > another.b):
            return True
        return False

    # Hàm dùng để xếp hạng đội T[1]
    def process(self):
        global T, R

        # Khởi tạo đội T[1] hạng nhất
        rank = 1

        # Duyệt từng đội từ 1 đến n
        for i in range(1, n + 1):
            # Nếu đội T[i] nào đó tốt hơn đội T[1] thì tăng hạng đội T[1]
            if self != 1 and self.is_another_team_better(T[i]):
                rank += 1

        return rank

Bước 3: Vừa đọc dữ liệu input vừa thực hiện xếp hạng

Mỗi khi có đội tốt hơn đội 1, ta sẽ tăng biến rank, là hạng của đội 1, lên 1.

C++Python

    cin >> n >> m;

    // Khởi tạo mảng T chứa dữ liệu của n đội
    T.resize(n + 1);

    int team_id, penalty;
    int r;

    // Duyệt từng lượt nộp bài
    for (int i = 0; i < m; ++i)
    {
        // Đọc mã đội và điểm phạt
        cin >> team_id >> penalty;

        // Ghi nhận điểm số và điểm phạt của đội team_id
        T[team_id].a += 1;
        T[team_id].b += penalty;

        // Xếp hạng cho đội T[1]
        r = process();
        R.push_back(r);
    }

        n, m = map(int, f.readline().split())

        # Khởi tạo mảng T chứa dữ liệu của n đội
        T = [team(0, 0) for _ in range(n + 1)]

        # Duyệt từng lượt nộp bài
        for _ in range(m):
            # Đọc mã đội và điểm phạt
            team_id, penalty = map(int, f.readline().split())

            # Ghi nhận điểm số và điểm phạt của đội team_id
            T[team_id].a += 1
            T[team_id].b += penalty

            # Xếp hạng cho đội T[1]
            r = T[1].process()
            R.append(r)

Mã nguồn¶

Code đầy đủ được đặt tại GitHub.

Bài 2: Chọn cam¶

Đề bài¶

Một băng chuyền có N khay đựng cam được đánh số liên tiếp từ 1 đến $N$.

Mỗi khay chứa hai quả cam, mỗi quả cam được dán nhãn phân loại từ 1 đến 5.

Trong đợt khuyến mãi này, người mua chỉ được chọn mua một loại cam bất kỳ trong một dãy liên tiếp các khay và mỗi khay người mua phải chọn một trong hai quả cam chứa trong khay đó.

Yêu cầu: cho biết phân loại các quả cam trong $N$ khay liên tiếp. Hãy viết một chương trình cho biết số lượng quả cam nhiều nhất một khách hàng có thể mua và loại cam tương ứng.

Dữ liệu: CHONCAM.INP

Dòng đầu chứa một số nguyên $N$.
Mỗi dòng trong $N$ dòng tiếp theo chứa hai số nguyên $A, B (1 \le A, B \le 5)$ cho biết phân loại của 2 quả cam trong lần lượt các khay.

Kết quả: CHONCAM.OUT

Hai số nguyên lần lượt cho biết số lượng quả cam nhiều nhất một khách hàng có thể mua và loại cam tương ứng.

Trong trường hợp có nhiều kết quả giống nhau hãy xuất ra kết quả ứng với loại cam nhỏ nhất.

Ràng buộc:

40% số điểm của bài: $N \le 100$
80% số điểm của bài: $N \le 10000$
100% số điểm của bài: $N \le 100000$

Ví dụ:

CHONCAM.INP	CHONCAM.OUT
2 1 2 3 1	2 1
3 1 2 2 3 4 3	2 2

Bài giải đề xuất¶

Ý tưởng chính là ghi nhận số lượng cam bằng mảng tần số f.

Để kiểm soát tính liên tiếp của cùng một loại cam, ta thực hiện đánh dấu bằng mảng continuous.

Dựa vào loại cam tương ứng trong mảng continuous là true hay false, tức liên tiếp hoặc bị đứt mạch, ta sẽ đếm số cam tăng thêm 1 hoặc đếm bắt đầu lại từ 1.

Bước 0:

Khởi tạo mảng tần số f và mảng đánh dấu continuous.

C++Python

// mảng tần số f lưu số lượng đang xét của các loại cam
vector<int> f(6, 0);

// mảng continuous dùng để đánh dấu tính liên tiếp của loại cam
vector<bool> continuous(6, false);

# mảng tần số f lưu số lượng đang xét của các loại cam
f = [0] * 6

# mảng continuous dùng để đánh dấu tính liên tiếp của loại cam
continuous = [False] * 6

Bước 1:

Viết hàm đánh dấu tính liên tiếp của các loại cam.

C++Python

void mark(int first, int second)
{
    // Đặt lại cho tất cả đều là không liên tiếp
    fill(continuous.begin(), continuous.end(), false);

    // Đánh dấu liên tiếp cho hai loại đang xét
    continuous[first] = true;
    continuous[second] = true;
}

def mark(first, second):
    global continuous

    # Đặt lại cho tất cả đều là không liên tiếp
    continuous = [False] * 6

    # Đánh dấu liên tiếp cho hai loại đang xét
    continuous[first] = continuous[second] = True

Bước 2:

Viết hàm xét và cập nhật số lượng cam nhiều nhất và loại cam tương ứng.

C++Python

void consider(int current_oranges, int current_type)
{
    if (current_oranges == max_oranges)
    {
        // Nếu loại đang xét bằng với giá trị lớn nhất
        // thì lấy loại có nhãn nhỏ nhất
        best_type = min(current_type, best_type);
    }
    else if (current_oranges > max_oranges)
    {
        // Nếu loại đang xét lớn hơn giá trị lớn nhất
        // thì cập nhật giá trị lớn nhất mới và loại mới
        max_oranges = current_oranges;
        best_type = current_type;
    }
}

def consider(current_oranges, current_type):
    global max_oranges, best_type

    if current_oranges == max_oranges:
        # Nếu loại đang xét bằng với giá trị lớn nhất
        # thì lấy loại có nhãn nhỏ nhất
        best_type = min(current_type, best_type)
    elif current_oranges > max_oranges:
        # Nếu loại đang xét lớn hơn giá trị lớn nhất
        # thì cập nhật giá trị lớn nhất mới và loại mới
        max_oranges = current_oranges
        best_type = current_type

Bước 3:

Lần lượt đọc mỗi khay gồm hai trái cam, cập nhật mảng tần số f và đánh dấu tính liên tiếp của các loại cam.

Nếu loại cam đang xét vẫn liên tiếp thì cộng dồn vào mảng tần số f. Ngược lại, không còn liên tiếp, thì đặt lại tần số là 1.

Đồng thời, gọi hàm consider() để cập nhật số lượng cam nhiều nhất.

Cuối mỗi bước lặp, gọi hàm mark() để đánh dấu tính liên tiếp cho tất cả loại cam.

C++Python

    // hai loại cam trên một khay
    int first, second;

    // Duyệt từng khay
    for (int i = 0; i < n; ++i)
    {
        cin >> first >> second;

        // Nếu là loại thứ nhất đang liên tục thì tăng tần số lên 1
        // Ngược lại, không liên tục, thì đếm lại từ đầu, là 1
        if (continuous[first])
            f[first] += 1;
        else
            f[first] = 1;

        // Xét xem đã đạt được nhiều nhất hay chưa
        consider(f[first], first);

        // Nếu là loại cam thứ hai đang liên tục thì tăng tần số lên 1
        // Ngược lại, không liên tục, thì đếm lại từ đầu
        if (continuous[second])
            f[second] += 1;
        else
            f[second] = 1;

        // Xét xem đã đạt được nhiều nhất hay chưa
        consider(f[second], second);

        // Đánh dấu lại tính liên tục cho hai loại này
        mark(first, second);
    }

    with open(input_file, 'r') as fi:
        n = int(fi.readline())

        # Duyệt từng khay
        for i in range(n):
            first, second = map(int, fi.readline().split())

            # Nếu là loại cam thứ nhất đang liên tục thì tăng tần số lên 1
            # Ngược lại, không liên tục, thì đếm lại từ đầu
            if continuous[first]:
                f[first] += 1
            else:
                f[first] = 1

            # Xét xem đã đạt được nhiều nhất hay chưa
            consider(f[first], first)

            # Nếu là loại cam thứ hai đang liên tục thì tăng tần số lên 1
            # Ngược lại, không liên tục, thì đếm lại từ đầu
            if continuous[second]:
                f[second] += 1
            else:
                f[second] = 1

            # Xét xem đã đạt được nhiều nhất hay chưa
            consider(f[second], second)

            # Đánh dấu lại tính liên tục cho từng loại cam
            mark(first, second)

Mã nguồn¶

Code đầy đủ được đặt tại GitHub.

Bài 3: Rút ván¶

Đề bài¶

Trò chơi rút ván thiết kế trên một vùng hình chữ nhật được bao bởi hai đoạn thẳng có độ dài là $A$ và hai đoạn thẳng có độ dài là $B$. Ta có thể xem hai điểm góc chéo nhau của vùng chơi có tọa độ là $(0; 0)$ và $(A; B)$, $1 \le A, B \le 10^9$.

Có $N$ thanh dọc có độ dài $B$, một đầu của thanh dọc thứ $i$ được đặt tại điểm có tọa độ $(a_i; 0)$, đầu còn lại nằm trên điểm $(a_i; B)$, $0 < a_i < A$.

Có $M$ thanh ngang có độ dài $A$, một đầu của thanh ngang thứ $$j$ được đặt tại điểm có tọa độ $(0; b_j)$, đầu còn lại nằm trên điểm $(A; bj), 0 < b_j < B$.

Cách bố trí các thanh dọc, ngang như trên chia hình chữ nhật ban đầu thành $(N + 1)(M + 1)$ khu vực khép kín.

Tại những điểm giao nhau, ta cắt thanh dọc và thanh ngang để tạo ra những đoạn nhỏ hơn.

Nhiệm vụ của người chơi là cần bỏ đi các đoạn sao cho tất cả khu vực trong vùng chơi thông với nhau và tổng độ dài các đoạn bỏ đi là ít nhất. Có thể hiểu rằng khi tất cả khu vực thông nhau thì trong vùng chơi từ một khu vực ta có thể di chuyển đến một khu vực bất kỳ.

Hình minh họa ví dụ bên dưới: cần bỏ các đoạn nét đứt để các khu vực thông nhau.

Yêu cầu: hãy viết một chương trình cho biết tổng độ dài ít nhất các đoạn cần bỏ đi để tất cả khu vực trong vùng chơi thông nhau.

Dữ liệu: RUTVAN.INP

Dòng đầu chứa 4 số nguyên $A, B, N, M$.
Mỗi dòng trong $N$ dòng tiếp theo chứa một số nguyên lần lượt là vị trí của các thanh dọc $a_1, a_2, ..., a_N$.
Mỗi dòng trong $M$ dòng tiếp theo chứa một số nguyên lần lượt là vị trí của các thanh ngang $b_1, b_2, ..., b_M$.

Kết quả: RUTVAN.OUT

Một số nguyên cho biết tổng độ dài ít nhất các đoạn cần bỏ đi để tất cả các khu vực trong vùng chơi thông nhau.

Ràng buộc:

30% số điểm của bài: $0 \le N, M \le 3$
60% số điểm của bài: $0 \le N, M \le 1000$
100% số điểm của bài: $0 \le N, M \le 25000$

Ví dụ:

RUTVAN.INP	RUTVAN.OUT
5 5 2 2 1 3 3 4	10

Bài giải đề xuất¶

Ý tưởng chính:

Nếu như xem mỗi vùng là một đỉnh của đồ thị, mỗi đoạn của thanh (ngang hoặc dọc) là một cạnh của đồ thị, thì cách giải quyết bài toán này tương tự cách xác định cây khung tối thiểu bằng thuật toán Kruskal.

Bước 0:

Khởi tạo mảng Xs và Ys để lưu trữ vị trí của các thanh dọc và thanh ngang, kể cả các đoạn thẳng A và B bao bên ngoài.

C++Python

    // Đọc các hoành độ (thanh dọc)
    Xs.resize(n + 2);

    // Nạp hoành độ đầu tiên là 0
    Xs[0] = 0;

    // Nạp các hoành độ của các thanh dọc
    for (int i = 1; i < n + 1; ++i)
    {
        cin >> Xs[i];
    }

    // Nạp hoành độ cuối cùng là a
    Xs[n + 1] = a;

    // Đọc các tung độ (thanh ngang)
    Ys.resize(m + 2);

    // Nạp tung độ đầu tiên là 0
    Ys[0] = 0;

    // Nạp các tung độ của các thanh ngang
    for (int i = 1; i < m + 1; ++i)
    {
        cin >> Ys[i];
    }

    // Nạp tung độ cuối cùng là b
    Ys[m + 1] = b;

        # Đọc các hoành độ (thanh dọc)
        # Nạp hoành độ đầu tiên là 0
        Xs.append(0)

        # Nạp các hoành độ của các thanh dọc
        for _ in range(n):
            Xs.append(int(f.readline()))

        # Nạp hoành độ cuối cùng là a
        Xs.append(a)

        # Đọc các tung độ (thanh ngang)
        # Nạp tung độ đầu tiên là 0
        Ys.append(0)

        # Nạp các tung độ của các thanh ngang
        for _ in range(m):
            Ys.append(int(f.readline()))

        # Nạp tung độ cuối cùng là b
        Ys.append(b)

Bước 1: Tính độ dài của các đoạn cắt

Lần lượt dựa trên hoành độ và tung độ của các điểm giao nhau, ta sẽ tính độ dài của các đoạn cắt và đưa vào mảng lengths.

C++Python

    // Độ dài của một đoạn được cắt
    int l;

    // Duyệt từng vị trí của các hoành độ (thanh dọc)
    for (int i = 1; i < Xs.size(); ++i)
    {
        // Tính độ dài của một đoạn được cắt
        l = Xs[i] - Xs[i - 1];

        // Thêm độ dài vào mảng lengths
        // Số lần thêm phải bằng với số lượng thanh ngang
        for (int j = 0; j < m; ++j)
        {
            lengths.push_back(l);
        }
    }

    // Duyệt từng vị trí của các tung độ (thanh ngang)
    for (int i = 1; i < Ys.size(); ++i)
    {
        // Tính độ dài của một đoạn được cắt
        l = Ys[i] - Ys[i - 1];

        // Thêm độ dài vào mảng lengths
        // Số lần thêm phải bằng với số lượng thanh dọc
        for (int j = 0; j < n; ++j)
        {
            lengths.push_back(l);
        }

    }

    # Duyệt từng vị trí của các hoành độ (thanh dọc)
    for i in range(1, len(Xs)):
        # Tính độ dài của một đoạn được cắt
        l = Xs[i] - Xs[i - 1]

        # Thêm độ dài vào mảng lengths
        # Số lần thêm phải bằng với số lượng thanh ngang
        for j in range(m):
            lengths.append(l)

    # Duyệt từng vị trí của các tung độ (thanh ngang)
    for i in range(1, len(Ys)):
        # Tính độ dài của một đoạn được cắt
        l = Ys[i] - Ys[i - 1]

        # Thêm độ dài vào mảng lengths
        # Số lần thêm phải bằng với số lượng thanh dọc
        for j in range(n):
            lengths.append(l)

Bước 2: Thực hiện "rút ván"

Thực hiện tương tự thuật toán Kruskal:

Sắp xếp các đoạn cắt theo thứ tự độ dài tăng dần
Tính số vùng ban đầu
Tính tổng độ dài của các đoạn được cắt. Trong đó, số phần tử tham gia tính tổng là số vùng trừ đi 1.

C++Python

    // Sắp xếp mảng lengths tăng dần
    sort(lengths.begin(), lengths.end());

    // Tính số vùng ban đầu
    int region_count = (n + 1) * (m + 1);

    // Tính tổng độ dài của các đoạn được cắt
    // Chỉ lấy số lượng đoạn bằng số vùng trừ đi 1
    total_length = accumulate(lengths.begin(), lengths.begin() + region_count - 1, 0);

    # Sắp xếp mảng lengths tăng dần
    lengths.sort()

    # Tính số vùng ban đầu
    region_count = (n + 1) * (m + 1)

    # Tính tổng độ dài của các đoạn được cắt
    # Chỉ lấy số lượng đoạn bằng số vùng trừ đi 1
    total_length = sum(lengths[0:region_count - 1])

Mã nguồn¶

Code đầy đủ được đặt tại GitHub.

Bao tôi ly cafe 🧋 nhé!