সমস্যা বিবরণ
Nটি মন্স্টার দেওয়া আছে, প্রতিটি মন্স্টার-এর ইনিশিয়াল হেলথ h[i] যা একটি ইন্টিজার। একটি মন্স্টার জীবিত থাকে যদি এর হেলথ ০-এর চেয়ে বড় হয়।
প্রতি টার্নে একটি র্যান্ডম মন্স্টার অন্য একটি র্যান্ডম মন্স্টারকে কিল করে, আক্রমণ করা মন্স্টার-এর হেলথ আক্রমণকারী মন্স্টার-এর হেলথের পরিমাণ কমে যায়। এই প্রসেসটি এক মন্স্টার বাঁচা থাকার পর্যন্ত চলবে। লাস্ট বাঁচা মন্স্টার-এর মিনিমাম পসিবল হেলথ কত হবে?
উদাহরণ
যদি ইনপুট অ্যারে = {2, 14, 28, 56} হয়, তবে আউটপুট হবে ২ কারণ শুধু প্রথম মন্স্টার বাকি ৩টি মন্স্টারকে আক্রমণ করলে লাস্ট মন্স্টার-এর ফাইনাল হেলথ ২ হবে, যা মিনিমাম।
অ্যালগরিদম
নিচের GCD ফর্মুলা ব্যবহার করে ফাইনাল আন্সার বের করা যায় −
H(min) = gcd(h1, h2, …, hn)
উদাহরণ
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int getPossibleHealth(int* health, int n) {
int currentGcd = gcd(health[0], health[1]);
for (int i = 2; i < n; ++i) {
currentGcd = gcd(currentGcd, health[i]);
}
return currentGcd;
}
int main() {
int health[] = { 4, 6, 8, 12 };
int n = sizeof(health) / sizeof(health[0]);
cout << "Possible final health = " << getPossibleHealth(health, n) << endl;
return 0;
}
আউটপুট
যখন আপনি উপরের প্রোগ্রাম কম্পাইল ও এক্সিকিউট করবেন। এটি নিচের আউটপুট জেনারেট করবে:
Possible final health = 2
