Cho mảng A kích thước K. Trò chơi K vòng. Vòng i: chia thành nhóm A[i] trẻ. Dư thoát ra. Sau vòng K còn đúng 2 trẻ. Tìm min và max số trẻ ban đầu N.
Ví dụ
Với A=[3,4,3,2], đầu ra [6,8]. N=6: vòng1: 2 nhóm 3; vòng2: 2 nhóm 4,2; vòng3: 1 nhóm 3, 1 dư; vòng4: 1 nhóm 2, 1 dư → còn 2.
Giải thuật
Duyệt ngược từ vòng K về 1. Giữ khoảng [l, r] số trẻ có thể có trước vòng i. Khởi tạo l=r=2. Vòng i: L = ceil(l/A[i])*A[i], R = floor(r/A[i])*A[i] + A[i]-1. Nếu L > R impossible. Cập nhật l=L, r=R.
Mã 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"; return; }
l = L, r = R + x - 1;
}
cout << l << ", " << r << endl;
}
int main() {
vector<int> A = { 3, 4, 3, 2 };
solve(A);
}
Đầu vào / Đầu ra
Input: { 3, 4, 3, 2 }
Output: 6, 8