คำชี้แจงปัญหา
ให้มอนสเตอร์ N ตัว มอนสเตอร์แต่ละตัวมีพลังชีวิตเริ่มต้น h[i] ซึ่งเป็นจำนวนเต็ม สัตว์ประหลาดจะมีชีวิตอยู่หากพลังชีวิตของมันมากกว่า 0
ในแต่ละเทิร์น มอนสเตอร์แบบสุ่มจะฆ่ามอนสเตอร์แบบสุ่มอีกตัวหนึ่ง ซึ่งเป็นมอนสเตอร์ที่ถูกโจมตี พลังชีวิตของมันจะลดลงตามจำนวนพลังชีวิตของมอนสเตอร์ที่โจมตี กระบวนการนี้จะดำเนินต่อไปจนกว่าจะเหลือมอนสเตอร์ตัวเดียว ค่าพลังชีวิตขั้นต่ำที่เป็นไปได้ของมอนสเตอร์ตัวสุดท้ายที่เหลืออยู่คือเท่าใด
ตัวอย่าง
หากอาร์เรย์อินพุตเป็น {2, 14, 28, 56} เอาต์พุตจะเป็น 2 เพราะเมื่อมีมอนสเตอร์ตัวแรกเท่านั้นที่โจมตีมอนสเตอร์ 3 ตัวที่เหลือ พลังชีวิตของมอนสเตอร์ตัวสุดท้ายจะเป็น 2 ซึ่งน้อยที่สุด
อัลกอริทึม
เราสามารถรับคำตอบสุดท้ายโดยใช้สูตร GCD ด้านล่าง -
H(นาที) =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
