Số chữ số 0 cuối cùng tối đa trong tích tập con kích thước K C++

Cho mảng Arr[] kích thước N và số K. Tìm số chữ số 0 cuối cùng (trailing zeros) lớn nhất trong tích của các tập con kích thước K.

Số chữ số 0 cuối của một số = min(số ước 2, số ước 5) trong phân tích thừa số nguyên tố.

Ví dụ

Input: Arr[] = {5, 20, 2}, K = 2
Output: 2
Giải thích: Các tập con size 2: {5,20}→100 (2 zeros), {20,2}→40 (1 zero), {5,2}→10 (1 zero). Max = 2.

Input: Arr[] = {60, 40, 25}, K = 2
Output: 3

Thuật toán Quy hoạch động (Dynamic Programming)

Vì chỉ quan tâm số lượng ước 2 và 5, ta dùng DP:

• dp[i][j] = số ước 2 tối đa khi chọn i phần tử có tổng ước 5 = j.
• Khởi tạo dp[0][0] = 0, còn lại = -1 (chưa đạt được).
• Với mỗi phần tử x, đếm cnt2, cnt5. Cập nhật DP ngược từ K-1 về 0.
• Kết quả: max over j của min(j, dp[K][j]).

Chương trình C++

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

const int MAX5 = 100; // Giới hạn tổng ước 5 (đủ cho N≤100, mỗi số ≤10^9 có ≤13 ước 5)

int maxTrailingZeros(int arr[], int N, int K) {
    vector> dp(K + 1, vector(MAX5 + 5, -1));
    dp[0][0] = 0;
    
    for (int idx = 0; idx < N; idx++) {
        int x = arr[idx];
        int cnt2 = 0, cnt5 = 0;
        while (x % 2 == 0) { cnt2++; x /= 2; }
        while (x % 5 == 0) { cnt5++; x /= 5; }
        
        for (int i = K - 1; i >= 0; i--) {
            for (int j = 0; j <= MAX5; j++) {
                if (dp[i][j] != -1 && j + cnt5 <= MAX5) {
                    dp[i + 1][j + cnt5] = max(dp[i + 1][j + cnt5], dp[i][j] + cnt2);
                }
            }
        }
    }
    
    int ans = 0;
    for (int j = 0; j <= MAX5; j++)
        if (dp[K][j] != -1)
            ans = max(ans, min(j, dp[K][j]));
    return ans;
}

int main() {
    int arr[] = {60, 40, 25};
    int N = 3, K = 2;
    cout << maxTrailingZeros(arr, N, K); // Output: 3
    return 0;
}

Kết quả

3