Một máy ATM hiện có n (n<=25) tờ tiền mệnh giá t1,t2,t3,...,tn. Một người khách cần rút số tiền S. Hãy cho biết cần bao nhiêu mỗi loại để người khách rút ít tờ nhất với số tiền đúng bằng S

Để giải bài toán này, chúng ta có thể sử dụng phương pháp quy hoạch động (Dynamic Programming) để tìm cách rút ít tờ tiền nhất với số tiền chính xác bằng S. Dưới đây là hướng dẫn giải chi tiết:

1. **Đọc dữ liệu đầu vào:**
- Đọc số lượng mệnh giá `n` và số tiền cần rút `S`.
- Đọc danh sách các mệnh giá tiền.

2. **Tạo một mảng DP để lưu trữ thông tin tối ưu:**
- Tạo một mảng `dp` với kích thước `S + 1`. Mỗi phần tử `dp[i]` sẽ lưu trữ số tờ ít nhất cần rút để có tổng tiền bằng `i`.
- Tạo một mảng `count` để lưu trữ số lượng tờ rút của từng mệnh giá cho mỗi tổng tiền.

3. **Khởi tạo mảng:**
- Gán giá trị `dp[0] = 0` (không cần rút tờ nào để có 0 đồng) và các phần tử còn lại của `dp` sẽ là một số lớn (ví dụ: `inf` hoặc `max_value`).
- Gán mảng `count` để theo dõi số tờ của mỗi mệnh giá.

4. **Thuật toán quy hoạch động:**
- Duyệt qua từng mệnh giá tiền. Với mỗi mệnh giá, kiểm tra tất cả các giá trị từ mệnh giá đó đến S để cập nhật giá trị trong mảng `dp`.
- Nếu `dp[j - ti] + 1 < dp[j]`, cập nhật `dp[j]` và lưu lại số tờ rút.

5. **Kết quả:**
- Nếu `dp[S]` vẫn là giá trị lớn (không thể rút được số tiền), in ra `-1`.
- Ngược lại, in ra số tờ cần rút và mảng số tờ của từng mệnh giá.

Dưới đây là mã giả thuật toán này bằng Python:

```python
def atm_withdrawing(n, S, denominations):
dp = [float('inf')] * (S + 1)
count = [[0] * n for _ in range(S + 1)]
dp[0] = 0 # Không rút tiền nào để có 0 đồng

for i in range(n):
t = denominations[i]
for j in range(t, S + 1):
if dp[j - t] + 1 < dp[j]: # Tìm cách rút ít tờ nhất
dp[j] = dp[j - t] + 1
count[j] = count[j - t][:]
count[j][i] += 1 # Cập nhật số tờ mệnh giá t

if dp[S] == float('inf'):
print(-1)
else:
print(dp[S])
print(' '.join(map(str, count[S])))

# Nhập dữ liệu
n, S = map(int, input().split())
denominations = list(map(int, input().split()))

# Gọi hàm và in kết quả
atm_withdrawing(n, S, denominations)
```

### Ví dụ
Đối với đầu vào:
```
12 365
5 100 20 10 20 200 50 50 100 50 10 500
```

Kết quả sẽ là:
```
5
5 200 100 50 10
```

### Ghi chú
- Hãy chú ý rằng thuật toán này có độ phức tạp O(n * S), điều này là ổn với n ≤ 25 và S có thể đạt đến giá trị lớn (mặc dù không được định rõ trong đề bài).