<시간/>
이 문제에서 원의 가장자리에 있는 n개의 상자를 나타내는 숫자 n이 주어집니다. 그리고 각각 두 개의 정수, 및 b로 구성된 Q 쿼리가 있습니다. 우리의 임무는 서클에서 상자를 결합하는 것이 가능한지 확인하기 위해 쿼리를 해결하는 프로그램을 만드는 것입니다.
문제 설명 − 각 쿼리를 풀기 위해 마지막 쿼리의 상자 교차가 방해되지 않는 방식으로 상자 a와 상자 b를 막대로 연결할 가능성을 확인해야 합니다. 가능을 인쇄해야 합니다. 또는 불가능 조건에 따라.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
n = 6 Q = 3 Queries = {{1, 3}, {2, 5}, {4, 5}} 출력
Possible
Not possible
Possible
설명
실선은 연결할 수 있는 막대이고 점선은 연결할 수 없는 선입니다.
솔루션 접근 방식
문제에 대한 간단한 해결책은 각 쿼리에 대한 쿼리의 솔루션을 찾는 것입니다. 주어진 box box와 box b가 연결될 수 있는지 여부를 찾을 것입니다. 이를 위해서는 마지막 쿼리의 값을 참조점으로 유지한 다음 연결이 가능한지 확인해야 합니다.
상자 a를 살펴보겠습니다. 그리고 b 쿼리(i-1)를 참조 ref1 및 ref2로 사용합니다. 그런 다음 점과 b가 막대의 반대쪽에 있는지 찾으십시오.
이를 위해 두 가지 조건을 확인합니다.
조건 1 - if (ref1
조건 2 - if (ref1
두 경우 모두 결과가 불가능합니다.
다음은 당사 솔루션의 작동을 설명하는 프로그램입니다.
예시
#include <iostream>
using namespace std;
int printSolutoin(int n, int a, int b, int ref1, int ref2, int lastConn){
if(lastConn == 0 && a != b)
return 1;
int temp;
if(a > b){
temp = a;
a = b;
b = temp;
}
if(ref1 > ref2){
temp = ref1;
ref1 = ref2;
ref2 = temp;
}
if( ( ref1 < a && a < b && b < ref2) )
return 1;
if( (ref1 <= a <= ref2) && (ref2 <= b <= n) ) return 0;
else if( (ref1 <= b <= ref2) && (ref2 <= a <= n) )
return 0;
return 0;
return 1;
}
void solveAllQueries(int n, int q, int query[][2]){
int lastConn = printSolutoin(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 = printSolutoin(n, query[i][0], query[i][1], query[i - 1][0], query[0][1], lastConn);
lastConn?cout<<"Possible\n":cout<<"Not Possible\n";
}
}
int main() {
int n = 6;
int Q = 3;
int query[Q][2] = {{1, 3}, {2, 5}, {4, 5}};
return 0;
} 출력
Possible
Not possible
Possible
