Nhận xét 1: Kết quả không bao giờ vượt quá ~\sum a_i~, do ta có thể giữ nguyên sức mạnh là ~1~ rồi làm mọi bài tập.

Nhận xét 2: Một kỹ năng sẽ không được luyện tập quá ~17~ lần. Nếu một kỹ năng được luyện tập đến lần thứ ~17~, chi phí sẽ là ~17! > 10^{15}~, trái Nhận xét 1.

Vì vậy, ta chỉ thực hiện luyện tập tối đa ~17 \times m~ lần. Ta duy trì một hàng đợi ưu tiên để tìm ra chi phí nhỏ nhất cho một lần nâng sức mạnh lên một đơn vị.

Nhận xét 3: Cách tối ưu nhất luôn là thực hiện luyện tập mọi kỹ năng, rồi mới làm bài tập.

Bây giờ, ta cần tính nhanh chi phí để làm ~n~ bài tập khi sức mạnh hiện tại là ~s~. Dễ thấy có hai cách:

• Cách ~1~: Duyệt qua mọi bài tập, độ phức tạp ~O~ ~(n)~.
• Cách ~2~: Nhận thấy cứ mỗi ~s~ đơn vị, chi phí làm bài tập mới thay đổi một lần. Vì vậy, có thể tính nhanh trong độ phức tạp ~O~ (~\frac {10^9}{s} \times log~).

Ta sẽ tìm ra cách tối ưu hơn và thực hiện nó.

Code mẫu cho phần xử lý này:

int get_ceil (int a, int b){
    int res = a / b;
    return res + (res * b < a);
}

// O (n)
long long get_cost_loop (long long s){
    long long cost = 0;
    for (int i = 0; i < n; i++) cost += get_ceil (a[i], s);
    return cost;
}

// O (10^9 / s * log (n))
long long get_cost_skip (long long s){
    int i = 0;
    long long cost = 0;
    while (i < n){
        long long r = a[i];
        if (r % s) r += s - (r % s);
        int next_i = upper_bound (a + i + 1, a + n, r) - a;
        cost += (r / s) * (next_i - i);
        i = next_i;
    }
    return cost;
}