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

    solution

    Đề bài: [Toán rời rạc] Đếm dòng đúng trong bảng chân trị

    Cho một biểu thức logic chứa các biến (mỗi biến là một chữ cái thường). Bảng chân trị liệt kê mọi tổ hợp giá trị 0/10/10/1 của các biến. Hãy đếm số dòng (tổ hợp) làm biểu thức nhận giá trị 111 (đúng).

    Các biến được lấy là tập các chữ cái thường xuất hiện trong biểu thức.

    Quy ước: biến là một chữ cái thường (a..z), hằng 0/1. Toán tử: ! (phủ định, NOT), & (và, AND), | (hoặc, OR), -> (kéo theo, IMP). Độ ưu tiên từ cao đến thấp: !, &, |, ->. Phép -> kết hợp phải. Có thể dùng dấu ngoặc ( ). Phép kéo theo p→qp \to qp→q chỉ sai khi p=1,q=0p=1, q=0p=1,q=0.

    Ví dụ: a|b có 2 biến, 4 dòng; số dòng đúng là 3 (chỉ a=b=0a=b=0a=b=0 cho 0).

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

      Một dòng: biểu thức logic.

    • Ràng buộc đầu vào:

      Số biến phân biệt ≤16\le 16≤16, độ dài biểu thức ≤200\le 200≤200.

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

      Một dòng: số dòng của bảng chân trị làm biểu thức đúng.

    Ví dụ:

    Đầu vào:

    a|b

    Đầu ra:

    3

    Giải thích:

    4 tổ hợp; chỉ $(a,b)=(0,0)$ cho 0, ba tổ hợp còn lại cho 1 → 3.

    Đang tải editor...