Truy vấn kiểm tra có thể nối các hộp trên vòng tròn trong C++

Mô tả bài toán

Có n hộp đặt trên đường tròn. Q truy vấn, mỗi truy vấn cho hai hộp a, b. Kiểm tra có thể nối a và b bằng một que thẳng mà không cắt que đã nối từ truy vấn trước đó. Trả về "Possible" hoặc "Not Possible".

Ví dụ: n=6, truy vấn {{1,3},{2,5},{4,5}} → Possible, Not Possible, Possible.

Giải pháp

Giữ lại cặp tham chiếu (ref1, ref2) từ truy vấn trước. Với truy vấn mới (a,b) (giả sử a

Ví dụ minh họa (C++)

#include <iostream>
using namespace std;

int printSolution(int n, int a, int b, int ref1, int ref2, int lastConn) {
    if (lastConn == 0 && a != b) return 1;
    if (a > b) swap(a,b);
    if (ref1 > ref2) swap(ref1,ref2);
    if (ref1 < a && a < b && b < ref2) return 1;
    if ((ref1 <= a && a <= ref2) && (ref2 <= b && b <= n)) return 0;
    if ((ref1 <= b && b <= ref2) && (ref2 <= a && a <= n)) return 0;
    return 0;
}

void solveAllQueries(int n, int q, int query[][2]) {
    int lastConn = printSolution(n, query[0][0], query[0][1], 0, 0, 0);
    lastConn ? cout << "Possible\n" : cout << "Not Possible\n";
    for (int i = 1; i < q; i++) {
        lastConn = printSolution(n, query[i][0], query[i][1], query[i-1][0], query[i-1][1], lastConn);
        lastConn ? cout << "Possible\n" : cout << "Not Possible\n";
    }
}

int main() {
    int n = 6, Q = 3;
    int query[3][2] = {{1,3},{2,5},{4,5}};
    solveAllQueries(n, Q, query);
    return 0;
}

Đầu ra

Possible
Not Possible
Possible