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

    solution

    Đề bài: [Toán cho CNTT] Phát hiện miền khả thi rỗng

    Miền khả thi rỗng

    Cho hệ ràng buộc aix+biy≤cia_i x + b_i y \le c_iai​x+bi​y≤ci​, x,y≥0x,y\ge0x,y≥0. Nếu không có điểm nào thỏa mãn đồng thời tất cả ràng buộc thì miền khả thi rỗng.

    Với miền đa giác lồi bị chặn, nếu tồn tại ít nhất một đỉnh (giao của hai ràng buộc) khả thi thì miền không rỗng.

    Ví dụ

    x+y≤1x+y\le1x+y≤1 và x+y≥3x+y\ge3x+y≥3 (viết dạng −x−y≤−3-x-y\le-3−x−y≤−3): không có điểm chung nên in EMPTY.

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

      Dòng 1: n. n dòng a b c cho ràng buộc ax+by≤cax+by\le cax+by≤c. Ngầm định x,y≥0x,y\ge0x,y≥0.

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

      1≤n≤201 \le n \le 201≤n≤20; hệ số nguyên trị tuyệt đối ≤100\le 100≤100.

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

      FEASIBLE nếu miền không rỗng, ngược lại EMPTY.

    Ví dụ:

    Đầu vào:

    2
1 1 1
-1 -1 -3

    Đầu ra:

    EMPTY

    Giải thích:

    Can x+y<=1 va x+y>=3 dong thoi: khong the, mien rong.

    Đang tải editor...