Mô tả bài toán

Bài toán yêu cầu xây dựng công cụ kiểm tra độ chính xác của độ phức tạp thời gian được声明者 cho các đoạn mã giả sử dụng ngôn ngữ A++. Ngôn ngữ này chỉ hỗ trợ một cấu trúc lặp với cú pháp chuẩn hóa:

F i x y
    <thân_vòng_lặp>
E

Câu lệnh F i x y khai báo biến đếm i, khởi tạo giá trị khởi đầu là x, và thực thi khối lệnh bên trong miễn là i <= y. Sau mỗi bước lặp, i tự động tăng 1. Tham số x và y có thể là số nguyên dương hoặc ký tự đặc biệt n (biểu thị kích thước dữ liệu đầu vào, luôn được giả định lớn hơn 100). Câu lệnh E đánh dấu ranh giới kết thúc khối lệnh và giải phóng phạm vi của biến i.

Yêu cầu chính là so sánh độ phức tạp thực tế với giá trị声明者, đồng thời phát hiện các lỗi cấu trúc như mất cân bằng cặp F và E, hoặc khai báo trùng biến trong cùng một phạm vi lồng nhau. Lưu ý quan trọng: lỗi cú pháp vẫn phải được báo cáo ngay cả khi chúng xuất hiện trong các khối lệnh bị bỏ qua do điều kiện lặp không thỏa mãn.

Định dạng dữ liệu

Đầu vào: Dòng đầu chứa số nguyên dương T (số lượng bộ test). Mỗi test bắt đầu bằng số dòng lệnh L và chuỗi biểu diễn độ phức tạp mong đợi (dạng O(1) hoặc O(n^k)). Tiếp theo là L dòng mã lệnh tương ứng.

Đầu ra: In ra T dòng kết quả. Trả về Yes nếu khớp, No nếu sai lệch, và ERR nếu phát hiện lỗi cú pháp.

Chiến thuật giải quyết

Để xử lý hiệu quả cấu trúc lồng nhau, ta sử dụng mô hình ngăn xếp (Stack) kết hợp với bộ đếm trạng thái. Các thành phần trọng tâm bao gồm:

• Quản lý phạm vi biến: Một mảng boolean hoặc tập hợp được dùng để theo dõi các biến đang sống trong các vòng lặp cha. Khi gặp F, kiểm tra trùng lặp trước khi đưa vào ngăn xếp; khi gặp E, giải phóng biến tương ứng.
• Xử lý trạng thái chặn (Skip State): Khi điều kiện khởi tạo thỏa mãn x > y, vòng lặp hiện tại và mọi vòng lặp con bên trong sẽ không được thực thi. Ta duy trì một biến đếm activeSkip để đánh dấu vùng bị chặn. Trong vùng này, việc tính độ sâu vẫn bị tạm ngưng nhưng trình phân tích vẫn phải duyệt qua các dòng lệnh để đảm bảo cân bằng cấu trúc và phát hiện lỗi cú pháp.
• Tính toán độ phức tạp: Độ phức tạp thực tế tương đương với độ sâu lồng nhau tối đa của các vòng lặp được thực thi. Mỗi khi đi vào vòng lặp hợp lệ và không bị chặn, ta tăng chiều sâu hiện tại và cập nhật giá trị lớn nhất tìm được.

Thuật toán sẽ duyệt tuyến tính qua các dòng lệnh, cập nhật ngăn xếp biến, điều chỉnh bộ đếm chặn và độ sâu. Sau khi hoàn thành việc đọc hết L dòng, ta đối chiếu độ sâu tối đa với số mũ được声明者 để đưa ra kết luận cuối cùng.

Triển khai mã nguồn

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

void processTestCase() {
    int lineCount;
    string claimedComplexity;
    cin >> lineCount >> claimedComplexity;

    int targetExponent = 0;
    if (claimedComplexity.find('n') != string::npos) {
        size_t caretIdx = claimedComplexity.find('^');
        size_t closeIdx = claimedComplexity.find(')');
        targetExponent = stoi(claimedComplexity.substr(caretIdx + 1, closeIdx - caretIdx - 1));
    }

    vector<char> scopeStack;
    bool varInUse[26] = {false};
    int openLoopCount = 0;
    int skipLevel = 0;
    int currentDepth = 0;
    int maxDepth = 0;
    bool hasSyntaxError = false;

    auto evaluateLine = [&](const string& rawLine) {
        if (hasSyntaxError) return;
        
        istringstream stream(rawLine);
        string cmd;
        stream >> cmd;

        if (cmd == "F") {
            openLoopCount++;
            char varName;
            string startVal, endVal;
            stream >> varName >> startVal >> endVal;

            if (varInUse[varName - 'a']) {
                hasSyntaxError = true;
                return;
            }
            scopeStack.push_back(varName);
            varInUse[varName - 'a'] = true;

            if (skipLevel == 0) {
                bool willBlock = false;
                if (startVal == "n") willBlock = true;
                else if (endVal == "n") willBlock = false;
                else willBlock = (stoi(startVal) > stoi(endVal));

                if (willBlock) {
                    skipLevel = 1;
                } else {
                    currentDepth++;
                    if (currentDepth > maxDepth) maxDepth = currentDepth;
                }
            } else {
                skipLevel++;
            }
        } else if (cmd == "E") {
            if (openLoopCount == 0) {
                hasSyntaxError = true;
                return;
            }
            openLoopCount--;
            if (!scopeStack.empty()) {
                varInUse[scopeStack.back() - 'a'] = false;
                scopeStack.pop_back();
            }

            if (skipLevel > 0) {
                skipLevel--;
            } else {
                currentDepth--;
            }
        }
    };

    string buffer;
    getline(cin, buffer);
    for (int i = 0; i < lineCount; ++i) {
        string line;
        getline(cin, line);
        evaluateLine(line);
    }

    if (openLoopCount != 0 || hasSyntaxError) {
        cout << "ERR" << endl;
    } else if (maxDepth == targetExponent) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int testCases;
    cin >> testCases;
    while (testCases--) {
        processTestCase();
    }
    return 0;
}