แบบสอบถามเพื่อตรวจสอบว่าสามารถเข้าร่วมกล่องในแวดวงใน C++ Program . ได้หรือไม่

ในปัญหานี้ เราได้รับตัวเลข n ซึ่งหมายถึง n กล่องที่อยู่ขอบวงกลม และมีคิวรี Q แต่ละรายการประกอบด้วยจำนวนเต็มสองตัวคือ a และ b งานของเราคือสร้างโปรแกรมเพื่อแก้ปัญหาเพื่อตรวจสอบว่าสามารถเข้าร่วมกล่องในแวดวงได้หรือไม่

คำอธิบายปัญหา − เพื่อแก้ปัญหาแต่ละคำถาม เราจำเป็นต้องตรวจสอบความเป็นไปได้ของการเชื่อมต่อกล่อง a และกล่อง b ด้วยแท่งในลักษณะที่จุดตัดของกล่องจากแบบสอบถามสุดท้ายจะไม่ถูกรบกวน เราจำเป็นต้องพิมพ์ เป็นไปได้ หรือ เป็นไปไม่ได้ ตามเงื่อนไข

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

n = 6 Q = 3 Queries = {{1, 3}, {2, 5}, {4, 5}}

ผลลัพธ์

Possible
Not possible
Possible

คำอธิบาย

แบบสอบถามเพื่อตรวจสอบว่าสามารถเข้าร่วมกล่องในแวดวงใน C++ Program . ได้หรือไม่

เส้นทึบคือแท่งที่เชื่อมต่อได้ ส่วนเส้นประคือเส้นที่เชื่อมต่อไม่ได้

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการค้นหาวิธีแก้ปัญหาของคิวรีสำหรับแต่ละคิวรี เราจะพบว่ากล่องที่กำหนดกล่อง a และกล่อง b สามารถเชื่อมต่อได้หรือไม่ สำหรับสิ่งนี้ เราจำเป็นต้องเก็บค่าของการสืบค้นล่าสุดเป็นจุดอ้างอิง จากนั้นตรวจสอบว่าการเชื่อมต่อเป็นไปได้หรือไม่

ลองพิจารณากล่อง a และ b ของข้อความค้นหา (i-1) เป็นข้อมูลอ้างอิง ref1 และ ref2 จากนั้นให้หาว่าจุด a และ 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