Skip to content

2024-2025 Lâm Đồng

Câu 1: Tam giác

Đề bài

Cho toạ độ bốn điểm A, B, C và M trên hệ trục toạ độ Oxy.

Điểm M được gọi là thuộc tam giác ABC nếu M nằm trên các cạnh hoặc miền trong của tam giác ABC.

Yêu cầu: xác định điểm M có thuộc tam giác ABC hay không.

Input: file TAMGIAC.INP

Gồm bốn dòng, mỗi dòng có hai số thực cách nhau một khoảng trắng lần lượt là toạ độ của các điểm A, B, C, M.

Output: file TAMGIAC.OUT

Gồm một số duy nhất 0 hoặc 1: nếu M thuộc tam giác ABC thì kết quả là 1, ngược lại là 0.

Ví dụ:

TAMGIAC.INP TAMGIAC.OUT
0.0 5.0
0.0 0.0
5.0 0.0
2.0 3.0		 1

Bài giải đề xuất

Ý tưởng chính là kiểm tra xem tổng diện tích của ba tam giác con ABM, BCM và CAM có bằng diện tích tam giác cha ABC hay không.

Bước 1: Viết hàm tính diện tích tam giác

Diện tích tam giác được tính theo công thức:

\[S = \frac{1}{2} |x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2)|\]
44
45
46
47
double area(point a, point b, point c)
{
    return abs((a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2.0);
}

30
31
def area(a, b, c):
    return abs((a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y)) / 2)

Bước 2: Kiểm tra diện tích

Viết hàm kiểm tra nếu tổng diện tích ba tam giác con bằng diện tích tam giác cha thì M thuộc tam giác ABC.

Vì dữ liệu là số thực nên ta không thể so sánh bằng == mà cần so sánh với một ngưỡng nhỏ \(\epsilon\) (epsilon). Trong đó, đặt \(\epsilon = 10^-9\).

40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
void process()
{
    // Tính diện tích tam giác ABC
    double abc = area(A, B, C);

    // Tính diện tích ba tam giác ABM, ACM, BCM
    double abm = area(A, B, M);
    double acm = area(A, C, M);
    double bcm = area(B, C, M);

    freopen(output_file, "w", stdout);

    // Nếu tổng diện tích ba tam giác con bằng diện tích tam giác ABC thì M thuộc tam giác ABC
    if (abs(abc - abm - acm - bcm) < eps)
        cout << 1;
    else
        cout << 0;
}

33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def process():
    global A, B, C, M

    # Tính diện tích tam giác ABC
    abc = area(A, B, C)

    # Tính diện tích ba tam giác ABM, ACM, BCM
    abm = area(A, B, M)
    acm = area(A, C, M)
    bcm = area(B, C, M)

    # Nếu tổng diện tích ba tam giác con bằng diện tích tam giác ABC thì M thuộc tam giác ABC
    if abs(abc - abm - acm - bcm) < eps:
        result = 1
    else:
        result = 0

    with open(output_file, 'w') as f:
        f.write(str(result))

Mã nguồn

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

Câu 2: Xây tháp

Đề bài

Tại vương quốc A, có một nàng công chúa xinh đẹp được rất nhiều người yêu mến, nên vào dịp sinh nhật trăng tròn của mình, công chúa được tặng n món quà hình hộp chữ nhật. Các hộp quà được tặng lần lượt theo thứ tự từ 1 đến n.

Vì quy cách tặng quà nên các hộp quà này có cùng độ dài và độ cao, chỉ khác nhau ở độ rộng (gọi độ rộng là r). Mỗi hộp quà được sơn bởi một trong hai màu xanh hoặc đỏ.

Người hầu của công chúa được giao nhiệm vu nhận quà nên cần phải thực hiện xếp chúng thành tháp quà cao nhất có thể, theo yêu cầu sau:

  • Mỗi tầng chỉ xếp một hộp quà.
  • Không xoay chiều các hộp quà.
  • Đặt hộp quà thứ i lên trên hộp quà thứ j thì độ rộng của hộp quà i phải nhỏ hơn độ rộng của hộp quà j.
  • Hai hộp quà xếp chồng kề nhau phải có màu sắc khác nhau.

Yêu cầu: hãy chọn nhiều nhất các hộp quà để xếp chúng thành tháp quà thoả mãn các điều kiện trên.

Input: file XAYTHAP.INP

  • Dòng đầu tiên ghi số \(n (n \le 500000)\)

  • Dòng tiếp theo ghi \(n\) số \(r_1, r_2, ..., r_n (-10^9 \le r_i \le 10^9)\). Trong đó \(r_i > 0\) là khối màu đỏ, \(r_i < 0\) là khối màu xanh, \(| ri |\) là độ rộng của hộp quà thứ \(i\).

Output: file XAYTHAP.OUT

Gồm một số nguyên là số lượng hộp quà nhiều nhất có thể xây được.

Ví dụ:

XAYTHAP.INP XAYTHAP.OUT
5
7 -2 6 9 -3		 2
11
-9 2 5 18 17 -15 4		 5

Bài giải đề xuất

Bước 0: Đọc dữ liệu từ file .inp

Tạo mảng một chiều G để lưu thông tin các hộp quà. Mỗi phần tử là một cặp giá trị \((r, color)\).

35
36
37
38
39
40
41
42
    int x;
    for (int i = 0; i < n; ++i)
    {
        cin >> x;

        G[i].r = abs(x);
        G[i].color = x > 0 ? 1 : 0;
    }

28
29
30
31
32
33
34
    G = [gift(0, 0) for _ in range(n)]

    X = list(map(int, f.readline().split()))

    for i in range(n):
        G[i].r = abs(X[i])
        G[i].color = 1 if X[i] > 0 else 0

Bước 1: Sắp xếp mảng G theo thứ tự độ rộng giảm dần.

48
49
50
51
52
    // Sắp xếp hộp quà theo thứ tự độ rộng giảm dần
    sort(G.begin(), G.end(), [](const gift& a, const gift& b)
    {
        return a.r > b.r;
    });

40
41
    # Sắp xếp hộp quà theo thứ tự độ rộng giảm dần
    G.sort(key=lambda x: x.r, reverse=True)

Bước 2: Điền bảng quy hoạch động

Khởi tạo mảng hai chiều D. Trong đó, D[i][c] là số hộp quà nhiều nhất tại vị trí i và có màu c.

Giả sử ta đang đứng ở hộp quà j. D[j][c] lưu số hộp quà nhiều nhất tính từ hộp đầu tiên đến hộp thứ j và có màu c.

Bây giờ ta xét hộp quà i tiếp theo sau j xem có thể đặt hộp quà i lên hộp quà j hay không.

Điều kiện để hộp quà i được đặt lên hộp quà j là:

1. Độ rộng của hộp quà i nhỏ hơn độ rộng của hộp quà j.

2. Màu của hộp quà i khác màu của hộp quà j.

Nếu thỏa mãn điều kiện trên thì ta cập nhật lại số hộp quà nhiều nhất tại vị trí i.

54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
    // Khởi tạo D với n phần tử
    D.resize(n, vector<int>(2, 0));

    // Duyệt từng hộp quà i
    for (int i = 0; i < n; ++i)
    {
        // Màu của hộp quà i
        int color_of_i = G[i].color;

        // Nếu chọn hộp quà i thì số hộp quà nhiều nhất tại vị trí i là 1
        D[i][color_of_i] = 1;

        // Duyệt từng hộp quà j trước đó
        for (int j = 0; j < i; ++j)
        {
            // Nếu hộp quà j có độ rộng nhỏ hơn hộp quà i và màu của hộp quà j khác màu của hộp quà i
            if (G[i].r < G[j].r)
                if (G[j].color != color_of_i)
                {
                    // thì cập nhật số hộp quà nhiều nhất tại vị trí i
                    D[i][color_of_i] = max(D[i][color_of_i], D[j][1 - color_of_i] + 1);
                }
        }

        // Nếu số hộp quà nhiều nhất tại vị trí i lớn hơn max_gift thì cập nhật max_gift
        max_gift = max(max_gift, D[i][color_of_i]);
    }

43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
    # Khởi tạo mảng D với n phần tử
    D = [[0] * 2 for _ in range(n)]

    # Duyệt từng hộp quà i
    for i in range(n):
        # Màu của hộp quà i
        color_of_i = G[i].color

        # Nếu chọn hộp quà i thì số hộp quà nhiều nhất tại vị trí i là 1
        D[i][color_of_i] = 1

        # Duyệt từng hộp quà j trước đó
        for j in range(i):
            # Nếu hộp quà j có màu khác với hộp quà i và hộp quà j có độ rộng nhỏ hơn hộp quà i
            if G[i].r < G[j].r:
                if G[j].color != color_of_i:
                    # thì cập nhật số hộp quà nhiều nhất tại vị trí i
                    D[i][color_of_i] = max(D[i][color_of_i], D[j][1 - color_of_i] + 1)

        # Nếu số hộp quà nhiều nhất tại vị trí i lớn hơn max_gift thì cập nhật max_gift
        max_gift = max(max_gift, D[i][color_of_i])

Mã nguồn

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

Câu 3: Xâu đối xứng

Đề bài

Cho một xâu S tối đa \(10^6\) ký tự.

Xâu con của xâu S là một dãy các ký tự liên tiếp nhau trong S.

Xâu đối xứng là xâu đọc từ trái qua phải hay đọc từ phải qua trái đều giống nhau, chẳng hạn như các xâu 'a', 'abba', 'abcdcba'.

Yêu cầu: tìm số nguyên k là độ dài của xâu con đối xứng dài nhất trong xâu S.

Input: file XDXUNG.INP

Xâu S.

Output: file XDXUNG.OUT

Một số nguyên k là độ dài của xâu con đối xứng dài nhất của xâu S.

Ví dụ:

XDXUNG.INP XDXUNG.OUT
Abcbcadk % 3
abcccccbbbbdddkh 7

Bài giải đề xuất

Bài toán này có thể giải bằng thuật toán Manacher hoặc quy hoạch động.

Phần trình bày dưới đây dùng quy hoạch động. Ý tưởng chính là: một chuỗi được xem là đối xứng khi ký tự đầu tiên và ký tự cuối cùng giống nhau và chuỗi con còn lại bên trong cũng là đối xứng.

Bước 0 Khởi tạo

Khởi tạo mảng hai chiều D có kích thước n x n với n là độ dài của xâu s.

Trong đó, D[i][j] lưu giá trị true hoặc false biểu thị chuỗi con s[i..j] là đối xứng hay không (bắt đầu từ i và kết thúc tại j).

Vì chuỗi con gồm một ký tự là đối xứng nên D[i][i] = 1.

Nếu hai ký tự liên tiếp giống nhau thì chuỗi con hai ký tự này cũng là đối xứng, nên D[i][i + 1] = 2.

30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
    // Khởi tạo mảng D
    int n = s.length();
    D.resize(n, vector<bool>(s.size(), false));

    // Khởi tạo D[i][i] cho tất cả chuỗi con có độ dài bằng 1
    for (int i = 0; i < n; ++i)
    {
        D[i][i] = true;
    }

    // Khởi tạo D[i][i+1] cho tất cả chuỗi con có độ dài bằng 2 với hai ký tự giống nhau
    for (int i = 0; i < n - 1; ++i)
    {
        D[i][i + 1] = (s[i] == s[i + 1]);
    }

24
25
26
27
28
29
30
31
32
33
34
    # Khởi tạo mảng D
    n = len(s)
    D = [[False] * n for _ in range(n)]

    # Khởi tạo D[i][i] cho tất cả chuỗi con có độ dài bằng 1
    for i in range(n):
        D[i][i] = True

    # Khởi tạo D[i][i+1] cho tất cả chuỗi con có độ dài bằng 2
    for i in range(n-1):
        D[i][i+1] = s[i] == s[i+1]

Bước 1: Điền bảng quy hoạch động

Lần lượt xét các chuỗi con có độ dài từ 3 trở lên.

Điều kiện để các chuỗi con này đối xứng là:

1. Ký tự đầu tiên i và ký tự cuối j phải giống nhau.

2. Chuỗi con nằm giữa s[i+1..j-1] phải là đối xứng.

Nếu thỏa mãn hai điều kiện trên thì ta cập nhật lại độ dài chuỗi con đối xứng dài nhất.

46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
    // Duyệt từng độ dài, với độ dài từ 3 trở lên
    for (int length = 3; length <= n; ++length)
    {
        // Duyệt từng vị trí i, là vị trí bắt đầu của chuỗi con
        for (int i = 0; i < n - length + 1; ++i)
        {
            // j là vị trí kết thúc của chuỗi con
            int j = i + length - 1;

            // Nếu ký tự đầu và cuối của chuỗi con giống nhau và chuỗi con bên trong là đối xứng
            if (s[i] == s[j])
                if (D[i + 1][j - 1] == true)
                {
                    // thì chuỗi con [i..j] cũng là đối xứng
                    D[i][j] = true;

                    // Cập nhật lại max_len nếu độ dài chuỗi con đối xứng đang xét lớn hơn max_len
                    max_len = max(max_len, length);
                }
        }
    }

36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
    # Duyệt từng độ dài, với độ dài từ 3 trở lên
    for length in range(3, n + 1):

        # Duyệt từng vị trí i, là vị trí bắt đầu của chuỗi con
        for i in range(n - length + 1):
            # j là vị trí kết thúc của chuỗi con
            j = i + length - 1

            # Nếu ký tự đầu và cuối của chuỗi con giống nhau và chuỗi con bên trong là đối xứng
            if s[i] == s[j] and D[i+1][j-1]:
                # thì chuỗi con [i..j] cũng là đối xứng
                D[i][j] = True

                # Cập nhật lại max_len nếu độ dài chuỗi con đối xứng đang xét lớn hơn max_len
                max_len = max(max_len, length)

Mã nguồn

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

Câu 4: Bữa tiệc

Đề bài

Công ty XYZ có N người được tổ chức theo sơ đồ hình cây: node K là cha của node L nghĩa là K là cấp trên của L. Ông giám đốc là gốc. Nhân viên thứ \(i\) có độ vui vẻ \(h_i (-128 < h_i < 127)\).

Ông giám đốc muốn tổ chức một bữa tiệc có tổng độ vui vẻ là lớn nhất và nếu có một nhân viên nào đó đi dự thì sẽ không có cấp trên trực tiếp của anh ta. Đương nhiên ông giám đốc phải có mặt.

Yêu cầu: hãy giúp ông giám đốc tìm độ vui vẻ lớn nhất.

Input: file BUATIEC.INP:

  • Dòng đầu ghi số nguyên dương \(N (1 < N < 2025)\)
  • Dòng thứ hai ghi \(N\) số \(h_1, h_2, ..., h_N (-128 < h_i < 127)\)
  • \(N - 1\) dòng còn lại ghi hai số \(L\) và \(K\).

Output: file BUATIEC.OUT

Một số nguyên là tổng độ vui vẻ lớn nhất tìm được.

Ví dụ:

BUATIEC.INP BUATIEC.OUT
7
1 1 1 1 1 1 1
2 1
3 1
4 2
6 2
5 3
7 3		 5

Bài giải đề xuất

Ý tưởng chính là sử dụng quy hoạch động.

Để lưu dữ liệu input, ta dùng danh sách kề adj (adjacent list), với adj[k] chứa các đỉnh (nhân viên) cấp dưới của k.

Mảng hai chiều D có kích thước n x 2 với n là số nhân viên, bao gồm giám đốc.

Trong đó:

  • D[i][0] là tổng độ vui vẻ lớn nhất khi không chọn nhân viên i - D[i][1] là tổng độ vui vẻ lớn nhất khi chọn nhân viên i.

Để điền bảng quy hoạch động, ta duyệt từ gốc đến lá theo kỹ thuật duyệt DFS.

Bước 1: Viết hàm duyệt bằng DFS và điền bảng quy hoạch động

50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
void dfs(int k)
{
    // Khởi tạo khi chọn node k
    D[k][1] = H[k];

    // Duyệt từng con của node k
    for (int l : adj[k])
    {
        // Gọi đệ quy
        dfs(l);

        // Nếu chọn k thì không thể chọn con của k
        D[k][1] += D[l][0];

        // Nếu không chọn k thì có thể chọn hoặc không chọn con của k
        D[k][0] += max(D[l][0], D[l][1]);
    }
}

37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def dfs(k):
    global D, H

    # Khởi tạo khi chọn node k
    D[k][1] = H[k]

    # Duyệt từng con của node k
    for l in adj.get(k, []):
        # Gọi đệ quy
        dfs(l)

        # Nếu chọn k thì không thể chọn con của k
        D[k][1] += D[l][0]

        # Nếu không chọn k thì có thể chọn hoặc không chọn con của k
        D[k][0] += max(D[l][0], D[l][1])

Bước 2: Gọi hàm dfs() với node truyền vào là 1, ứng với giám đốc.

72
73
74
75
76
77
78
79
    // Khởi tạo D gồm n+1 hàng và 2 cột
    D.resize(n + 1, vector<int>(2, 0));

    // Gọi hàm dfs từ node 1 (giám đốc)
    dfs(1);

    // Tổng độ vui vẻ lớn nhất
    int result = D[1][1];

58
59
60
61
62
63
64
65
    # Khởi tạo D gồm n+1 hàng và 2 cột
    D = [[0, 0] for _ in range(n + 1)]

    # Gọi hàm dfs từ node 1 (giám đốc)
    dfs(1)

    # Tổng độ vui vẻ lớn nhất
    result = D[1][1]

Mã nguồn

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