Số chính phương ít nhất để biểu diễn n
Mọi số nguyên dương đều viết được thành tổng các số chính phương, nhưng số lượng số chính
Tiến độ của tôi ở bài này
Điểm và code bạn nộp được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: cpp-basics, loops.
Nội dung đề bài
Mô tả bài toán
Mọi số nguyên dương đều viết được thành tổng các số chính phương, nhưng số lượng số chính phương cần dùng lại thay đổi. Chọn số chính phương lớn nhất trước là cách làm tham lam rất dễ mắc và nó sai ngay ở những số nhỏ nhất định.
Yêu cầu
Cho số nguyên dương n, hãy tìm số lượng số chính phương nhỏ nhất có tổng đúng bằng n. Các số chính phương được dùng là 1, 4, 9, 16, ... và mỗi giá trị được dùng bao nhiêu lần cũng được. In ra số lượng nhỏ nhất đó.
Quy ước nộp bài
Nộp tệp solution.cpp đọc n từ stdin và ghi kết quả ra stdout. Chỉ in một số nguyên trên một dòng, không kèm chữ hay dấu cách thừa.
Input
- Một dòng duy nhất chứa số nguyên n (1 <= n <= 100).
Output
- Một số nguyên trên một dòng là số số chính phương ít nhất cần dùng.
Ràng buộc
- Mỗi số chính phương được dùng không hạn chế số lần.
- Chỉ cần in số lượng, không cần in cách phân tích.
- Thời gian cho mỗi bộ dữ liệu là 1 giây.
Ví dụ 1
Input
12
Output
3
Ví dụ 2
Input
13
Output
2
Giải thích
Ta có 12 = 4 + 4 + 4, dùng 3 số chính phương; cách tham lam 12 = 9 + 1 + 1 + 1 cần tới 4 số. Vậy in ra:
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.
