Nội dung Bài tập
- Mã:
-
MINIGAME40.3:
TRATIEN
- Tên:
- Trả tiền
- Dạng thi:
- oi
- Thang điểm:
- 30 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- admin
Nước X sử dụng hệ thống 20 loại tiền xu, trong đó các xu có mệnh giá là một số chính phương từ 12 đến 202:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400.
Với hệ thống này, để trả 10 xu ta có 4 cách:
- Trả 10 đồng 1 xu
- Trả 6 đồng 1 xu và 1 đồng 4 xu
- Trả 2 đồng 1 xu và 2 đồng 4 xu
- Trả 1 đồng 1 xu và 1 đồng 9 xu
Nhiệm vụ của bạn là xác định xem có bao nhiêu cách trả một số tiền cho trước ở nước X và cho biết một cách trả phải dùng ít đồng xu nhất.
Input:
Ghi số tiền nguyên dương không lớn hơn 666 xu.
Output:
• Dòng 1: Ghi số cách trả số tiền.• Dòng 2: Ghi số đồng xu tối thiểu phải trả• Các dòng tiếp theo, mỗi dòng ghi hai số a, b cách nhau ít nhất một dấu cách: cho biết sẽ có a đồng xu loại mệnh giá b2 trong phương án tối ưu (dùng ít đồng xu nhất)(Lưu ý: ghi theo thứ tự tăng dần giá trị của loại xu)
Ví dụ 1:
Input Output
Ví dụ 2:
Input Output
Ví dụ 3:
Input Output
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...