Bỏ qua

Olympic 10 Thành phố 2016 - 2017

Bài 1: Đặt cân

Đề bài

Cho \(n\) quả cân có khối lượng lần lượt là \(P[1], P[2], \cdots, P[n]\) và một cái cân có hai đĩa.

Yêu cầu: Tìm số cách đặt lên hai đĩa một số quả cân nào đó từ \(n\) quả cân trên sao cho cân thăng bằng.

Đầu vào: DATCAN.INP

  • Dòng đầu là số \(n\).
  • Dòng tiếp theo là các khối lượng của các quả cân.

Đầu ra: DATCAN.OUT

Một số nguyên duy nhất là số cách đặt cân. Nếu không có cách nào thì ghi số 0.

Ví dụ:

DATCAN.INP DATCAN.OUT
5
1 2 3 4 5		 7

Cách giải đề xuất

Ý tưởng chính

1. Thay vì theo dõi tổng khối lượng của từng đĩa, ta có thể theo dõi mức chênh lệch khối lượng giữa chúng.

Gọi $d[i][j]là số cách chọn một số quả cân bất kỳ từiquả cân đầu tiên sao cho chênh lệch khối lượng của hai đĩa làj`.

Ta có:

d[i][j] = d[i - 1][j] + d[i - 1][j - p[i]] + d[i - 1][j + p[i]]

Trong đó:

  • i là quả cân đang xét.
  • j là mức độ chệnh lệch giữa hai đĩa, nằm trong phạm vi [-total, +total], với total là tổng khối lượng của n quả cân.
  • + p[i] là đặt quả cân i lên đĩa trái.
  • - p[i] là đặt quả cân i lên đĩa phải.

2. Sau khi duyệt hết n quả cân, d[n][total] sẽ là số cách đặt cân sao cho hai đĩa thăng bằng.

Ta phải trừ đi 1 để bỏ đi cách mà hai đĩa không có quả cân nào.

Tiếp theo, ta phải chia 2, vì hai đĩa cân là đối xứng, đặt a quả cân lên đĩa trái và b quả cân lên đĩa phải cũng giống như đặt a lên đĩa phải và b lên đĩa trái.

Như vậy, result = (d[n][total] - 1) / 2

3. Quan sát công thức trên, ta thấy để tính toán ở bước i, ta chỉ cần truy xuất bước i - 1. Các giá trị trước đó từ bước 0 đến i - 2 là không cần thiết.

Do đó, thay vì dùng bảng có n hàng (để i chạy từ 0 đến n - 1), ta chỉ cần hai hàng, đồng nghĩa hai mảng:

  • Mảng prev_d[j] tương đương hàng i - 1, tức bước trước đó.
  • Mảng d[j] tương đương hàng i, tức bước hiện tại đang xét.
Viết chương trình

1. Khởi tạo mảng prev_d dùng để lưu số cách ở bước trước đó.

39
40
41
42
43
// Khởi tạo mảng prev_d để lưu số cách ở bước trước đó
vector<lli> prev_d(2 * total + 1, 0);

// Chưa đặt quả cân nào lên đĩa, tính là 1 cách
prev_d[total] = 1;

39
40
41
42
43
    # Khởi tạo mảng prev_d để lưu số cách ở bước trước đó
    prev_d = [0] * (2 * total + 1)

    # Chưa đặt quả cân nào lên đĩa, tính là 1 cách
    prev_d[total] = 1

2. Điền giá trị vô bảng quy hoạch.

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
    // Duyệt từng quả cân
    for (int i = 0; i < n; ++i)
    {
        int w = p[i];

        // Khởi tạo mảng d để lưu số cách ở bước hiện đang xét
        vector<lli> d(2 * total + 1, 0);

        // Duyệt từng mức độ chênh lệch khối lượng của hai đĩa
        for (int j = 0; j < 2 * total + 1; ++j)
        {
            if (prev_d[j] > 0)
            {
                // Trường hợp 0: không đặt thêm quả cân
                d[j] += prev_d[j];

                // Trường hợp 1: đặt quả cân w lên đĩa trái
                if (j + w < 2 * total + 1)
                    d[j + w] += prev_d[j];

                // Trường hợp 2: đặt quả cân w lên đĩa phải
                if (j - w >= 0)
                    d[j - w] += prev_d[j];
            }
        }

        // Cập nhật mảng d để chuẩn bị cho lần lặp tiếp theo
        prev_d = d;
    }

45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
    # Duyệt từng quả cân
    for i in range(n):
        w = p[i]

        # Khởi tạo mảng d để lưu số cách ở bước hiện đang xét
        d = [0] * (2 * total + 1)

        # Duyệt từng mức độ chênh lệch khối lượng của hai đĩa
        for j in range(2 * total + 1):
            if prev_d[j] > 0:            
                # Trường hợp 0: không đặt thêm quả cân
                d[j] += prev_d[j]

                # Trường hợp 1: đặt quả cân w lên đĩa trái
                if j + w < 2 * total + 1:
                    d[j + w] += prev_d[j]

                # Trường hợp 2: đặt quả cân w lên đĩa phải
                if j - w >= 0:
                    d[j - w] += prev_d[j]           

        # Cập nhật mảng d để chuẩn bị cho lần lặp tiếp theo
        prev_d = d

3. Tính số cách thỏa yêu cầu bài toán.

74
    result = (prev_d[total] - 1) / 2;

69
    result = (prev_d[total] - 1) // 2

Mã nguồn

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

Bài 2: Đổ xí ngầu

Đề bài

Bờm yêu thích chơi những trò chơi với các con số và đã mua 3 viên xí ngầu về.

Các viên xí ngầu này có lần lượt \(S1, S2, S3\) mặt. Các mặt được đánh số từ \(1 \rightarrow S1, 1 \rightarrow S2, 1 \rightarrow S3\).

Bờm liên tục đổ xí ngầu và mỗi lần ghi nhận một số nguyên là tổng giá trị của 3 mặt xí ngầu đổ được. Mục đích của Bờm là tìm ra tổng giá trị nào xuất hiện nhiều nhất.

Yêu cầu: Cho số mặt của 3 xí ngầu, hãy xác định xem tổng giá trị nào xuất hiện nhiều nhất. Nếu có nhiều hơn 1 giá trị xuất hiện nhiều nhất thì ghi ra giá trị nhỏ nhất. Giả sử xác suất xuất hiện của các mặt xí ngầu là như nhau.

Đầu vào: DOXINGAU.INP

3 số nguyên cách nhau bởi dấu cách: \(S1, S2, S3 (2 \le S1 \le 20; 2 \le S2 \le 20; 2 \le S3 \le 40)\).

Đầu ra: DOXINGAU.OUT

Số nguyên nhỏ nhất là tổng giá trị xuất hiện nhiều lần nhất.

Ví dụ:

DOXINGAU.INP DOXINGAU.OUT
3 2 3 5

Giải thích:

Đây là tất cả các trường hợp có thể xảy ra.

1 1 1 -> 3
1 1 2 -> 4
1 1 3 -> 5
1 2 1 -> 4
1 2 2 -> 5
1 2 3 -> 6
2 1 1 -> 4
2 1 2 -> 5
2 1 3 -> 6
2 2 1 -> 5
2 2 2 -> 6
2 2 3 -> 7
3 1 1 -> 5
3 1 2 -> 6
3 1 3 -> 7
3 2 1 -> 6
3 2 2 -> 7
3 2 3 -> 8

Trong đó, 5 và 6 xuất hiền nhiều lần nhất, mỗi số là 5 lần. Vậy kết quả là 5.

Cách giải đề xuất

Ý tưởng chính

1. Các ràng buộc về số mặt trên mỗi viên xí ngầu khá nhỏ, chỉ tối đa 20, 20 và 40. Do đó, ta chỉ cần vét cạn để tìm ra tổng xuất hiện thường xuyên nhất.

2. Để lưu số lần xuất hiện của mỗi tổng, ta sử dụng mảng tần số counter.

Số phần tử tối đa của counter là 20 + 20 + 40 + 1 = 81.

Viết chương trình

1. Dùng ba vòng lặp để vét cạn các mặt của ba viên xí ngầu: cập nhật tần số của tổng trong mảng counter.

2. Tìm chỉ số của phần tử lớn nhất trong counter, đây chính là tổng xuất hiện nhiều nhất.

26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
    // Khởi tạo mảng tần số
    counter.resize(s1 + s2 + s3 + 1, 0);

    // Duyệt từng mặt của từng xí ngầu
    for (int i = 1; i <= s1; ++i)
    {
        for (int j = 1; j <= s2; ++j)
        {
            for (int k = 1; k <= s3; ++k)
            {
                // Tăng số lần xuất hiện của tổng thêm 1
                counter[i + j + k]++;
            }
        }
    }

    // Tìm vị trí của phần tử lớn nhất
    auto it = max_element(counter.begin(), counter.end());

    // Lấy chỉ số của phần tử lớn nhất, cũng chính là tổng của 3 xí ngầu
    result = distance(counter.begin(), it);

32
33
34
35
36
37
38
39
40
41
42
43
    # Khởi tạo mảng tần số
    counter = [0] * (s1 + s2 + s3 + 1)

    # Duyệt từng mặt của từng xí ngầu
    for i in range(1, s1 + 1):
        for j in range(1, s2 + 1):
            for k in range(1, s3 + 1):
                # Tăng số lần xuất hiện của tổng thêm 1
                counter[i + j + k] += 1

    # Lấy chỉ số của phần tử lớn nhất, cũng chính là tổng của 3 xí ngầu
    result = counter.index(max(counter))

Mã nguồn

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

Tags

Bao tôi ly cafe 🧋 nhé!