Skip to content
TheChatArchiveThe Chat Archive
gpt-4-1106-preview· openaiHugging Face Suzhen/CodeChat

làm bài này bằng c++ Kujoh được thầy Phú giao cho làm một bảng quảng cáo gồm k ô, tại…

  1. User

    làm bài này bằng c++ Kujoh được thầy Phú giao cho làm một bảng quảng cáo gồm k ô, tại bất kì thời điểm nào mỗi ô chỉ gồm một chữ cái. Kujoh muốn bảng này hiện ra một xâu S độ dài n > k. Tuy nhiên do bảng này chỉ có k ô, nên anh ấy sẽ biểu diễn xâu này trong n-k+1 bước. Ở bước thứ i (1 ≤ i ≤ n-k+1) anh ấy sẽ làm cho bảng quảng cáo hiện lên các kí tự Si, Si+1, …, Si+k-1. Năng lượng cần dùng để thay đổi bảng quảng cáo từ bước i sang bước i+1 (1 ≤ i ≤ n-k) bằng số lượng kí tự đang được hiện trên bảng phải thay đổi. Ví dụ từ “aabc” sang “abca” cần 3 năng lượng để thay đổi kí tự tại vị trí thứ 2, 3 và 4. Các bạn hãy giúp Kujoh tính tổng năng lượng cần dùng để biểu diễn toàn bộ xâu S. Dữ liệu: vào từ file BOARD.INP:

    • Dòng đầu tiên gồm 2 số nguyên n và k. (n > k)
    • Dòng thứ hai là một xâu độ dài n gồm các chữ cái latin tiếng Anh từ “a” đến “z”. Kết quả: ghi ra file BOARD.OUT: Gồm một số duy nhất là tổng năng lượng cần dùng. Ví dụ: BOARD.INP BOARD.OUT 6 3 aabbcc 4 Giải thích ví dụ:
    • Ở bước đầu tiên, bảng hiển thị “aab”.
    • Ở bước thứ hai, bảng hiển thị “abb”.
    • Ở bước thứ ba, bảng hiển thị “bbc”.
    • Ở bước cuối cùng, bảng hiển thị “bcc”. Năng lượng để chuyển từ bước 1 sang bước 2 là 1, từ bước 2 sang bước 3 là 2, từ bước 3 sang bước 4 là 1. Tổng cả cần 1 + 2 + 1 = 4 năng lượng. Giới hạn:
    • 1 ≤ k < n ≤ 1000. (60%)
    • 1 ≤ k < n ≤ 106 . (40%) với phương pháp sau Nhận xét: để tính 1 lần chuyển bước cần bao nhiêu năng lượng, ta đếm xem có bao nhiêu cặp kí tự liên tiếp khác nhau trong xâu kí tự đang được biểu diễn trên bảng. Gọi res là kết quả bài toán. Ban đầu đang biểu diễn k kí tự đầu tiên, thì ta tính được cur sẽ là năng lượng cần để chuyển từ bước 1 sang bước 2 là tổng (s[i] != s[i-1]) với i từ 2 đến k+1. Duyệt i từ 2 đến n-k, từ bước i sang bước i+1 ta cần phải kiểm tra thêm kí tự s[i+k-1] với s[i+k] và không cần kiểm tra s[i] và s[i-1] nữa, do đó nếu s[i] != s[i-1] thì cur--, và nếu s[i+k-1] != s[i+k] thì cur++, còn ở giữa ta không cần kiểm tra lại vì trước đó đã kiểm tra rồi. Sau mỗi lần chuyển bước ta lại res += cur. Đpt: O(n).
  2. Assistant

    Dưới đây là đoạn mã C++ thực thi yêu cầu đã cho:

    #include <iostream>
    #include <fstream>
    #include <string>
    
    using namespace std;
    
    int main() {
        ifstream inp("BOARD.INP");
        ofstream out("BOARD.OUT");
        int n, k;
        string s;
    
        // Đọc dữ liệu đầu vào
        inp >> n >> k;
        inp >> s;
    
        // Biến để tính tổng năng lượng
        int totalEnergy = 0;
        // Biến để lưu trữ năng lượng của bước hiện tại
        int curEnergy = 0;
    
        // Tính năng lượng cần thiết để chuyển từ bước đầu tiên sang bước thứ hai
        for (int i = 1; i < k; i++) {
            if (s[i] != s[i - 1]) {
                curEnergy++;
            }
        }
    
        // Duyệt qua từng bước và cập nhật năng lượng
        for (int i = 0; i < n - k; i++) {
            totalEnergy += curEnergy;
            // Nếu kí tự đầu tiên của bước hiện tại và kí tự cuối cùng của bước trước khác nhau
            if (s[i] != s[i + 1]) {
                // Thì giảm năng lượng hiện tại
                curEnergy--;
            }
            // Nếu kí tự cuối cùng của bước hiện tại và kí tự đầu tiên của bước tiếp theo khác nhau
            if (s[i + k - 1] != s[i + k]) {
                // Thì tăng năng lượng hiện tại
                curEnergy++;
            }
        }
        // Đừng quên thêm năng lượng của bước cuối cùng vào tổng
        totalEnergy += curEnergy;
    
        // Xuất kết quả ra file
        out << totalEnergy << endl;
    
        // Đóng file
        inp.close();
        out.close();
    
        return 0;
    }
    

    Trong đoạn mã trên, chúng ta thực hiện đọc dữ liệu đầu vào từ file "BOARD.INP" và sau đó thực hiện tính toán năng lượng cần thiết để thay đổi bảng quảng cáo từ bước này sang bước tiếp theo cho đến khi toàn bộ xâu S được hiển thị. Cuối cùng, kết quả sẽ được ghi ra file "BOARD.OUT".

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.