Mô tả
Xưởng in Ánh Sáng chuyên nhận đặt in biên lai cho các lễ hội văn hóa tại Hội An. Khách hàng đặt hàng theo dạng combo: một combo sẽ tự động nhân đôi số lượng. Cụ thể, nếu lễ hội đặt n phần, xưởng sẽ sản xuất tổng cộng n! = 1 * 2 * ... * n biên lai, gọi là "đơn hàng". Mỗi đơn hàng có màu ngẫu nhiên: hoặc là tờ giấy trắng, hoặc là tờ giấy hồng.
May mắn thay, máy in có quy luật: số tờ trắng luôn nhiều hơn số tờ hồng theo cấp số nhân lũy thừa của 5. Do đó, để đóng gói đẹp mắt, xưởng cần ghép mỗi tờ trắng với đúng một tờ hồng thành một "cặp biên lai". Những tờ trắng thừa ra sẽ được cất đi dùng cho lần sau.
Nhiệm vụ của bạn là: cho biết số lượng phần n mà lễ hội đặt, hãy tính xem xưởng in có thể ghép được tối đa bao nhiêu cặp biên lai từ n! đơn hàng này?
Đầu vào
- Một dòng chứa số nguyên dương
n(1 ≤ n ≤ 10^9), là số phần của lễ hội đặt.
Đầu ra
- In ra một số nguyên duy nhất là số cặp biên lai tối đa có thể ghép được.
Ràng buộc
- 1 ≤ n ≤ 10^9.
- Đảm bảo kết quả luôn nằm trong phạm vi số nguyên 64-bit.
- KHÔNG được tính trực tiếp
n!(gây tràn số ngay cả với int64 khi n > 20).
Ví dụ
Ví dụ 1:
- Đầu vào:
5 - Đầu ra:
1 - Giải thích:
5! = 120đơn hàng. Trong đó số tờ hồng là5/5 = 1. Số tờ trắng là5/2 + 5/4 = 2 + 1 = 3. Vì chỉ có 1 tờ hồng nên ghép được tối đa 1 cặp.
Ví dụ 2:
- Đầu vào:
25 - Đầu ra:
6 - Giải thích:
25!. Số tờ hồng là25/5 + 25/25 = 5 + 1 = 6. Số tờ trắng là . Có 6 tờ hồng nên ghép được tối đa 6 cặp.