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