Giả sử chúng ta có hai số n và k. Chúng ta có số lượng không giới hạn đồng xu có giá trị từ 1 đến n. Chúng ta muốn lấy một số giá trị nào đó có tổng là k. Chúng ta có thể chọn nhiều đồng xu cùng giá trị để có tổng k. Chúng ta phải đếm số đồng xu tối thiểu cần để có tổng k.
Ví dụ, nếu đầu vào là n = 6; k = 16, thì đầu ra sẽ là 3, vì (2 * 6) + 4.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
c := (n + k - 1) / n return c
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include<bits/stdc++.h> using namespace std; int solve(int n, int k){ int c=(n+k-1)/n; return c; } int main(){ int n = 6; int k = 16; cout << solve(n, k) << endl; }Đầu vào
6, 16
Đầu ra
3