โปรแกรม C++ หาจำนวนเด็กน้อยที่สุดและมากที่สุดก่อนเริ่มเกม

คำอธิบายปัญหา

สมมติว่าเรามีอาร์เรย์ A K องค์ประกอบ มีเกม N ผู้เล่นและผู้ควบคุมเกม เกมมี K รอบ รอบที่ i ผู้ควบคุมประกาศจัดกลุ่มคน A[i] คน เหลือจัดกลุ่ม A[i] คนให้มากที่สุด คนที่ไม่มีกลุ่มออกจากเกม อื่นๆ ไปรอบต่อไป รอบอาจไม่มีคนออก หลังรอบ K เหลือ 2 คนชนะ ต้องการหาจำนวนเด็กน้อยที่สุดและมากที่สุดก่อนเริ่มเกม หรือบอกว่าไม่มีค่า N ที่ถูกต้อง

ตัวอย่าง: A = [3, 4, 3, 2] ผลลัพธ์คือ [6, 8] เพราะถ้าเริ่ม 6 คน:

• รอบ 1: 6 คน จัด 2 กลุ่ม 3 คน
• รอบ 2: จัดกลุ่ม 4 และ 2 คน
• รอบ 3: กลุ่ม 1 และ 3 คน คน 1 คนออก
• รอบ 4: 3 คน จัดกลุ่ม 1 และ 2 คน 1 คนออก
• เหลือ 2 คนชนะ

ขั้นตอนการแก้ปัญหา

n := ขนาดของ A
กำหนดอาร์เรย์ a, l, r ขนาด 100010
l := 2, r = 2
สำหรับ i := 1 ถึง n: a[i] := A[i-1]
สำหรับ i := n ถึง 1 ลดทีละ 1:
    x := a[i]
    L := (l + x - 1) / x * x
    R := r / x * x
    ถ้า L > R: คืนค่า -1, 0
    l := L, r := R + x - 1
คืนค่า l, r

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void solve(vector<int> A){
    int n = A.size();
    int l, r, a[100010];
    l = 2, r = 2;
    for (int i = 1; i <= n; i++) a[i] = A[i - 1];
    for (int i = n; i >= 1; i--){
        int x = a[i], L = (l + x - 1) / x * x, R = r / x * x;
        if (L > R){
            cout << "-1, 0";
        }
        l = L, r = R + x - 1;
    }
    cout << l << ", " << r << endl;
    return;
}

int main(){
    vector<int> A = { 3, 4, 3, 2 };
    solve(A);
}

อินพุต

{ 3, 4, 3, 2 }

เอาต์พุต

6, 8