সরাসরি লাইনে N সংখ্যক স্টেশন আছে। প্রতিটি স্টেশনের সমান নন-নেগেটিভ রেডিয়েশন পাওয়ার (radiation power) আছে। প্রতিটি স্টেশন নিচের উপায়ে আপনার পাশের স্টেশনগুলোর রেডিয়েশন পাওয়ার বাড়ায়।
মান লেইয়া স্টেশন i-এর রেডিয়েশন পাওয়ার R। এটি (i-1)তম স্টেশনের রেডিয়েশন পাওয়ার R-1 দিয়ে বাড়াবে, (i-2)তম স্টেশনের R-2 দিয়ে বাড়াবে, এবং (i+1)তম স্টেশনের R-1 দিয়ে, (i+2)তম স্টেশনের R-2 দিয়ে বাড়াবে। এইভাবে চলবে। উদাহরণস্বরূপ, অ্যারে Arr = [1, 2, 3] হলে আউটপুট হবে ৩, ৪, ৪। নতুন রেডিয়েশন হবে [1 + (2-1) + (3-2), 2 + (1-1) + (3-1), 3 + (2-1)] = [3, 4, 4]
আইডিয়া সহজ। প্রতিটি স্টেশন i উপরে উল্লিখিতভাবে পাশের স্টেশনগুলোর রেডিয়েশন বাড়াবে, যতক্ষণ না ইফেক্টিভ রেডিয়েশন নেগেটিভ হয়।
উদাহরণ
#include <iostream> using namespace std; class pump { public: int petrol; int distance; }; int findStartIndex(pump pumpQueue[], int n) { int start_point = 0; int end_point = 1; int curr_petrol = pumpQueue[start_point].petrol - pumpQueue[start_point].distance; while (end_point != start_point || curr_petrol < 0) { while (curr_petrol < 0 && start_point != end_point) { curr_petrol -= pumpQueue[start_point].petrol - pumpQueue[start_point].distance; start_point = (start_point + 1) % n; if (start_point == 0) return -1; } curr_petrol += pumpQueue[end_point].petrol - pumpQueue[end_point].distance; end_point = (end_point + 1) % n; } return start_point; } int main() { pump PumpArray[] = {{4, 6}, {6, 5}, {7, 3}, {4, 5}}; int n = sizeof(PumpArray)/sizeof(PumpArray[0]); int start = findStartIndex(PumpArray, n); if(start == -1) cout<<"No solution"; else cout<<"Index of first petrol pump : "<<start; }আউটপুট
Index of first petrol pump : 1
