Bài toán lớp học múa

Bài toán lớp học múa

Lớp học múa khiêu vũ dạ hội của giáo sư Padegras có n học sinh nam và nữ ghi tên. Giáo sư cho tất cả học sinh xếp thành một hàng dọc và chọn một nhóm các học sinh liên tiếp nhau cho buổi học đầu tiên với yêu cầu là số học sinh nam và nữ phải bằng nhau.

Hãy xác định, giáo sư Padegras có bao nhiêu cách lựa chọn khác nhau cho buổi học đầu tiên.

Dữ liệu: Vào từ file văn bản DANCE.INP:

• Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 10⁶),
• Dòng thứ 2 chứa xâu độ dài n bao gồm các ký tự từ tập {a, b} xác định dòng xếp hàng, a là nam,

b – nữ.

Kết quả: Đưa ra file văn bản DANCE.OUT một số nguyên – số cách lựa chọn.

Thuật toán

Để giải quyết bài toán này, ta có thể sử dụng kỹ thuật quy hoạch động.

Gọi f(i) là số cách lựa chọn cho buổi học đầu tiên khi chỉ xét đến i học sinh đầu tiên trong hàng. Ta có thể tính f(i) dựa trên f(i-1).

Nếu số học sinh nam và nữ tại vị trí i-1 bằng nhau, ta có thể thêm học sinh i vào để tạo thành một nhóm mới, số lượng nam và nữ trong nhóm mới vẫn bằng nhau. Vì vậy, f(i) sẽ tăng thêm f(i-2).

Nếu số học sinh nam và nữ tại vị trí i-1 không bằng nhau, ta không thể thêm học sinh i vào để tạo thành một nhóm mới. Vì vậy, f(i) = f(i-1).

Với trường hợp ban đầu, ta có f(0) = 1 và f(1) = 0 (do không thể tạo ra nhóm có số lượng nam và nữ bằng nhau với chỉ một học sinh).

Cuối cùng, kết quả cần tìm sẽ là f(n).

Độ phức tạp thời gian và không gian của thuật toán là O(n), do ta cần duyệt qua tất cả các học sinh trong hàng một lần.

Cài đặt bài toán với Python

with open('DANCE.INP', 'r') as f:
    n = int(f.readline().strip())
    line = f.readline().strip()

# Khởi tạo f
f = [1, 0] + [0] * (n - 1)

# Tính f
count_a = count_b = 0
for i in range(2, n+1):
    if line[i-2] == 'a':
        count_a += 1
    else:
        count_b += 1
    if count_a == count_b:
        f[i] = f[i-2]
    else:
        f[i] = f[i-1]

# Ghi kết quả vào file
with open('DANCE.OUT', 'w') as f:
    f.write(str(f[n]))

Cài đặt bài toán với C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    string line;
    ifstream fin("DANCE.INP");
    fin >> n >> line;
    fin.close();

    vector<long long> f(n + 1);
    f[0] = 1; f[1] = 0;
    int count_a = 0, count_b = 0;
    for (int i = 2; i <= n; i++) {
        if (line[i - 2] == 'a') count_a++;
        else count_b++;
        if (count_a == count_b) f[i] = f[i - 2];
        else f[i] = f[i - 1];
    }

    ofstream fout("DANCE.OUT");
    fout << f[n];
    fout.close();
    return 0;
}