Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Độ sâu phạm vi lớn nhất

    Trong quá trình biên dịch, mỗi khối lệnh { ... } mở ra một phạm vi (scope) mới lồng bên trong phạm vi bao quanh nó, và trình biên dịch quản lý các phạm vi này bằng một ngăn xếp phạm vi (scope stack) trong bảng ký hiệu. Toàn bộ chương trình được coi là nằm trong một khối gốc có độ sâu bằng 111.

    Cho nnn lệnh, mỗi lệnh thuộc một trong ba dạng sau:

    • BEGIN: mở một khối con mới (độ sâu hiện tại tăng thêm 111);
    • END: đóng khối con đang mở gần nhất (độ sâu hiện tại giảm đi 111); dữ liệu vào đảm bảo lệnh này không bao giờ được thực hiện khi đang ở khối gốc (độ sâu 111);
    • DECL x: khai báo một biến tên xxx vào bảng ký hiệu của khối đang mở (độ sâu hiện tại), không ảnh hưởng tới độ sâu.

    Gọi DDD là độ sâu lớn nhất mà chương trình từng đạt tới trong suốt quá trình thực hiện tuần tự nnn lệnh trên (kể cả khi không có lệnh nào, D=1D=1D=1 vì khối gốc luôn tồn tại). Hãy tính DDD và số lệnh DECL được thực hiện đúng vào những thời điểm độ sâu hiện tại bằng DDD.

    Ví dụ: với 6 lệnh DECL a, BEGIN, DECL b, BEGIN, DECL c, END, độ sâu lớn nhất đạt được là D=3D=3D=3 (ngay sau lệnh BEGIN thứ hai), và chỉ có đúng một lệnh DECL (là DECL c) được thực hiện ở độ sâu 333. Kết quả in ra là 3 1.

    • Định dạng đầu vào:

      Dòng đầu tiên chứa số nguyên nnn (0≤n≤20000 \le n \le 20000≤n≤2000) — số lệnh. nnn dòng tiếp theo, mỗi dòng là một lệnh BEGIN, END, hoặc DECL x (với xxx là một chuỗi chữ cái/chữ số không chứa khoảng trắng).

    • Định dạng đầu ra:

      In ra một dòng gồm hai số nguyên DDD và CCC cách nhau bởi một khoảng trắng.

    Ví dụ:

    Đầu vào:

    0

    Đầu ra:

    1 0

    Đầu vào:

    6
DECL a
BEGIN
DECL b
BEGIN
DECL c
END

    Đầu ra:

    3 1

    Đang tải editor...