2023-2024 Thành phố Hồ Chí Minh¶

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.

Bước 0: Khởi tạo

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
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
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

// Hàm dùng để đánh dấu tính liên tiếp của loại cam
void mark(int first, int second)
{
    // Đặt tất cả phần tử trong mảng continuous đều là false
    fill(continuous.begin(), continuous.end(), false);

    // Đánh dấu liên tiếp
    continuous[first] = true;
    continuous[second] = true;
}

# Hàm dùng để đánh dấu tính liên tiếp của loại cam
def mark(first, second):
    global continuous

    # Đặt tất cả phần tử trong mảng continuous đều là False
    continuous = [False] * 6

    # Đánh dấu liên tiếp
    continuous[first] = continuous[second] = True

Bước 2: Cập nhật mảng tần số f

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.

Gọi hàm mark() để đánh dấu tính liên tiếp cho tất cả loại cam.

C++Python

    // Biến lưu hai loại cam trên một khay
    int first, second;

    // Duyệt từng khay
    for (int i = 0; i < n; ++i)
    {
        // Đọc hai loại cam trong khay i
        first = trays[i][0];
        second = trays[i][1];

        // 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;

        // 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;

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

    # Duyệt từng khay
    for i in range(n):
        # Đọc hai loại cam trong khay i
        first = trays[i][0];
        second = trays[i][1];

        # 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;

        # 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;

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

Bước 3: In kết quả

Dựa vào mảng tần số f để in ra giá trị và chỉ số của phần tử tương ứng cần tìm.

C++Python

    // Tìm loại cam có tần số lớn nhất
    vector<int>::iterator max_f = max_element(f.begin(), f.end());

    // Tìm số lượng của loại cam có tần số lớn nhất
    int orange_type = max_f - f.begin();
    int orange_count = *max_f;
    cout << orange_count << ' ' << orange_type;

    # Tìm số lượng của loại cam có tần số lớn nhất
    orange_count = max(f)

    # Tìm loại cam có tần số lớn nhất
    orange_type = f.index(orange_count)

    with open(output_file, 'w') as f_out:
        f_out.write(f'{orange_count} {orange_type}')

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.