Bài 4 (3.0 điểm). Tuần lễ ca nhạc (MUSIC.*) Ở vương quốc Omega tươi đẹp, Quốc Vương tổ chức tuần lễ ca nhạc để kỷ niệm ngày quốc khánh. Đoàn ca nhạc trên toàn vương quốc được mời đến biểu diễn. Ban tổ chức nhận được n tiết mục văn nghệ đặc sắc,

Để giải bài toán này, chúng ta cần tìm cách phân chia các file video sao cho tổng số file được sao chép vào hai USB là lớn nhất mà không vượt quá dung lượng W trên mỗi USB.

Đầu tiên, chúng ta có thể hiểu rằng đây là một bài toán kiểu "knapsack", nơi chúng ta cố gắng tối ưu hóa số lượng item (trong trường hợp này là các file video) mà chúng ta có thể chứa trong hai "cặp balo" (hai USB). Chúng ta sẽ làm lần lượt như sau:

1. Đọc Input:
- Đọc số lượng tiết mục n và dung lượng W từ file MUSIC.INP.
- Đọc kích thước của các video vào danh sách A.

2. Tạo List cho Truyền Dẫn:
- Khởi tạo một danh sách dp với kích thước W+1 để lưu trữ số lượng video tối đa có thể sao chép cho một USB với dung lượng từ 0 đến W.

3. Tính Toán Số Video Tối Đa Cho Một USB:
- Sử dụng thuật toán quy hoạch động (Dynamic Programming) để cập nhật danh sách dp.
- Duyệt qua từng kích thước video. Với mỗi kích thước Ai, ta sẽ duyệt từ W về Ai (để không tính lại bản thân kích thước Ai đã được tính trước đó) và cập nhật dp[j] = max(dp[j], dp[j - Ai] + 1).

4. Xác định Số File Video Còn Lại:
- Có thể tính tổng số file video mà hai USB có thể lưu trữ bằng công thức dp[W] + dp[W] nối tiếp với nhau (xem các USB độc lập), nhưng phải đảm bảo không tính trùng file.

5. Viết Output:
- In ra tổng số file video vừa được tối ưu vào file MUSIC.OUT.

Trong mã giả, ta có thể biểu diễn điều này như sau:

```python
# Đọc dữ liệu từ file
n, W = map(int, input().split())
A = list(map(int, input().split()))

# Khởi tạo mảng dp
dp = [0] * (W + 1)

# Cập nhật số lượng video tối đa cho từng USB
for size in A:
for j in range(W, size - 1, -1):
dp[j] = max(dp[j], dp[j - size] + 1)

# Tổng số tiết mục tối đa trên cả hai USB
max_files = max(dp) * 2

# Ghi kết quả vào file
with open("MUSIC.OUT", "w") as f:
f.write(str(max_files))
```

Giải thích:
- Chúng ta sử dụng mảng dp để ghi nhớ số lượng video tối đa có thể lưu trên USB với dung lượng nhất định. Việc giảm j từ W về Ai đảm bảo rằng mỗi file chỉ được tính một lần cho mỗi USB.
- Bằng cách sử dụng giải pháp động, chúng ta tối ưu hóa không gian và số liệu, giúp tiết kiệm thời gian tính toán.

Kết quả cuối cùng cho biết số lượng tiết mục tối đa mà Tít và Mít có thể mang về.