Bài CANDY - Chia kẹo An là anh cả trong gia đình với K đứa em nhỏ. Là một người rất có trách nhiệm, luôn thương yêu các em của mình nên An luôn cố gắng làm những gì tốt nhất cho các em. Một hôm, đi công tác xa về, biết các em mình đều rất thích ăn kẹo, An ghé qua cửa hàng bánh kẹo Hải Hà lớn nhất thủ đô, chọn mua một gói kẹo ngon nhất trong phạm vi túi tiền mình có. Gói kẹo An mua có N cái kẹo và An dự định sẽ chia hết cho K đứa. Tuy nhiên, An phải chia làm sao cho đứa lớn hơn luôn ít kẹo hơn đứa bé hơn và đứa nào cũng phải có kẹo. Yều cầu: Bạn hãy giúp An tính xem có bao nhiêu cách có thể để An chia hết kẹo cho K em của mình. Dữ liệu vào: Từ tệp văn bản CANDY.INP có cấu trúc: • Chứa 2 số nguyên dương N và K là số lượng kẹo trong gói và số em của An. Kết quả: Ghi ra tệp văn bản CANDY.OUT một số nguyên duy nhất là số lượng cách có thể để An chia N cái kẹo cho K em.
cho em Ý TƯỞNG bài này với được không ạ? mong ac trả lời.em cám ơn
Dựa vào yêu cầu bài toán, ta có thể giải quyết bài toán này bằng phương pháp quay lui đệ quy. Ý tưởng cơ bản như sau:
1. Để đảm bảo rằng đứa lớn hơn luôn ít kẹo hơn đứa bé hơn, ta có thể sắp xếp mảng K em theo thứ tự tăng dần.
2. Sử dụng một hàm đệ quy để chia kẹo cho các em:
- Với mỗi em, ta thử tất cả các số kẹo có thể chia được từ 1 đến N, đồng thời giới hạn số kẹo không được vượt quá số kẹo hiện có và số kẹo của em trước đó. Sau đó, ta đệ quy chia kẹo cho các em tiếp theo.
- Khi đã chia hết kẹo cho K em, ta kiểm tra xem có phải cách chia kẹo hợp lệ theo yêu cầu của bài toán không.
- Nếu hợp lệ, tăng biến đếm số lượng cách chia lên.
3. Kết quả cuối cùng là số lượng cách chia kẹo hợp lệ.
---------
def count_ways(N, K, candies, current_index, current_count, current_sum):
# Đã chia hết kẹo cho K em
if current_index == K:
# Kiểm tra xem cách chia có hợp lệ không
if current_sum == N:
return 1
else:
return 0
# Đệ quy chia kẹo cho em tiếp theo
ways = 0
for i in range(1, candies[current_index] + 1):
if current_sum + i <= N and current_count + i <= candies[current_index]:
ways += count_ways(N, K, candies, current_index + 1, current_count + i, current_sum + i)
return ways
# Đọc dữ liệu từ file input
with open('CANDY.INP', 'r') as file:
N, K = map(int, file.readline().split())
# Đọc số lượng kẹo của từng em
candies = []
for _ in range(K):
candies.append(int(file.readline()))
# Gọi hàm đệ quy để tính số lượng cách chia kẹo hợp lệ
ways = count_ways(N, K, candies, 0, 0, 0)
# Ghi kết quả vào file output
with open('CANDY.OUT', 'w') as file:
file.write(str(ways))
