mọi người có thể cho em hướng giải bài này không ạ:
Cho n cái kẹo (n<=1000) chia cho k đứa em (k<=4) sao cho đứa lớn được ít kẹo hơn đứa bé và đứa nào cũng phải có kẹo. Số cách chia hết số kẹo ?
Vd:
Đầu vào : (n và k)
5 2
đầu ra: 2
giải thích
5=1+4=2+3
Bài này cần hướng gì nữa, dùng toán thôi. Tên bài toán là “bài toán chia kẹo”.
Bài toán ra như vậy, thế đứa nào là đứa lớn?
anh đọc kĩ lại đầu bài hộ em với ạ
k = 1, có 1 cách
k = 2, có (n-1)//2 cách, đừng hỏi tại sao, cho đại vài ví dụ rồi tự nhận ra, để giải được bài toán cần phải có quá trình tìm tòi suy nghĩ, làm đủ trăm phương ngàn kế kể cả tính nhẩm không có cơ sở (miễn đúng là được)
k >= 3, ta luôn có số kẹo của 3 người được chia như sau: [1+a1, 2+a2, …, k+ak]
như vậy, phần còn lại n - k*(k+1)/2 gọi là n’, chỉ cần chia thành mảng a với k phần tử như trên sao cho mảng này không giảm (tức a1 <= a2 <= … <= ak)
chỉ cần dùng đệ quy để đếm số cách chia số kẹo còn lại thành k phần như mảng a thôi
gợi ý hàm đệ quy:
ak >= trung bình cộng của cả mảng a, tức ak >= n’/k
sau khi đã chia kẹo vào a[k]
a[k-1] >= trung bình cộng của [k-1 phần tử đầu tiên của mảng a], tức a[k-1] >= (n’ - a[k])/(k-1)
sau khi đã chia kẹo vào a[k-1], làm tương tự
thật ra bài này chỉ cho max(k) = 4, nên có thể giải tay vài ví dụ rồi ra công thức hard code thôi chứ không cần phải làm tổng quát như trên
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?