Giúp đỡ ý tưởng bài tập đếm số cách đặt bi vào hộp

#1

Có n viên bi giống nhau trong m cái hộp, mỗi chiếc hộp không chứa quá k viên bi. Thứ tự đặt các hộp không quan trọng (Tức là nếu hộp 1 chứa 1 viên bi, hộp 2 chứa 2 viên bi hay là hộp 1 chứa 2, hộp 2 chứa 1 thì đều được tính là 1 cách).
Yêu cầu: Cho các số nguyên n, m và k. Hãy xác định số cách đặt khác nhau n viên bi vào m cái hộp sao cho mỗi hộp không quá k viên bi.
Input: 1 dòng duy nhất nhập vào 3 số n, m, k.
Ouput: Ghi là số duy nhất là số cách tìm được.
Ràng buộc:

  • Có 40% test tương ứng với 40% điểm thỏa mãn điều kiện: n, m, k <= 8
  • Có 40% test tương ứng với 40% điểm thỏa mãn điều kiện: 8 < n, m, k <= 50
  • Có 20% test tương ứng với 20% điểm thỏa mãn điều kiện: 50 < n, m, k <= 200

Ví dụ:

  • Input:
    4 3 2
  • Output:
    2

Giải thích:
Số cách có thể thực hiện thỏa mãn đề bài: bỏ vào lần lượt 3 bình với số kẹo lần lượt là 1; 1; 2 hoặc 2; 2.

Lại nhờ mọi người giúp tiếp @@. Bài này em có thể xử lý được subtask 1, nhưng subtask 2 và 3 thì không biết như nào cả, nhờ mọi người đưa ý tưởng ạ. Em cảm ơn nhiều

1 Like
#2
  1. Ý tưởng hiện tại của bạn?
  2. Bài làm (nếu có).
#3
  1. Hiện tại thì em đang suy nghĩ cách làm cho subtask 2, theo em thì nên quay lui + chia tập hợp + điều kiện để loại bỏ các trường hợp không cần thiết (đang trong quá trình suy nghĩ). Còn với subtask 3 thì em có suy nghĩ đến QHĐ, nhưng mà vẫn chưa có tiến triển gì cả.
  2. Code của em chỉ đang mới hoàn thiện subtask 1, subtask có thể chiều hoặc tối gì đó em sẽ cập nhật thêm.
#4

Code của subtask 1: Here
Sơ qua về cách làm: Mình quay lui, dùng 1 mảng a[] để lưu lại số lượng viên bi có thể bỏ được vào m bình (Giả sử mình có 4 viên bi, 3 bình, 1 viên bỏ vào bình 1, 2 viên bỏ vào bình 2, 1 viên còn lại bỏ vào bình 3, thì mình sẽ lưu thành a[1] = 2, a[2] = 1. Tức là với n viên bi, sẽ có a[i] bình được bỏ vào mỗi bình i viên bi theo cách chọn này). Sau đó đẩy mảng này vào unordered_map nếu chưa xuất hiện cách nào như vậy, kết quả đưa ra là mp.size().
Ai còn cảm thấy cách này thực sự chưa tối ưu thì rất mong nhận được sự giúp đỡ từ mọi người.

#5

Bài này chắc phải QHĐ 3 chiều dp[n, m, k] với m là số hộp đã sử dụng.

2 Likes
#6

chắc là f(n, m, k) = f(n - k, m - 1, k) + f(n, m, k - 1) :upside_down_face:

2 Likes
#7

Sao nghe nó cứ khó như nào ấy nhỉ
@rogp10 @tntxtnt hai anh có tài liệu tham khảo hay gì không @@

#8

:rofl: Who gave you this exercise? It’s high mathematics. You can consult HERE

2 Likes
#9

oh my lord, this exercise is in a exam to select excellent students in 2014-2015 for students in grades 10-11. Now i can say that i am unable to solve subtask 3. :smile:

1 Like
#10

quy hoạch động thôi, tìm công thức đệ quy là ra :upside_down_face:

gọi f(n, m, k) là số cách đặt n viên bi vào m hộp, mỗi hộp tối đa k viên bi. Ta có 2 cách đặt bi vào 1 hộp: hoặc là đặt k viên bi, hoặc là ko đặt viên bi nào vào hộp này. Ko nên đặt k’ (0 < k’ < k) viên bi vì khi đệ quy nó sẽ bị trùng :V :V

nếu đặt k viên bi vào 1 hộp thì hộp này coi như đã đầy, vậy trường hợp này bài toán trở thành tìm f(n - k, m - 1, k) là còn đặt n-k viên bi vào m-1 hộp, tối đa k viên bi mỗi hộp.

nếu ko đặt viên bi nào thì thoạt nhìn bài toán trở thành f(n, m-1, k) nhưng như vậy sẽ có trường hợp trùng :V ví dụ đặt k viên bi vào 2 hộp tối đa k viên mỗi hợp thì f(k, 2, k) thành f(k, 1, k) sẽ cho ra k,0 sẽ bị trùng với f(0, 1, k) là 0,k. Vậy để tránh bị trùng thì phải giảm k xuống. Giảm 1 để xét hết mọi trường hợp đặt x viên bi vào hộp với x <= k. Mà giảm k thì ko cần giảm số hộp nữa vì hộp trống vẫn có thể bị trùng :V Chuyển bài toán thành f(n, m, k - 1) thì bảo đảm số lượng bi sẽ tăng dần nên ko có trường hợp trùng.

vậy ta có công thức đệ quy f(n, m, k) = f(n - k, m - 1, k) + f(n, m, k - 1)

tìm thêm mấy base cases là trường hợp m=0,1 hay n > m*k v.v… nữa là được :V

6 Likes
#11

Very well explained.

1 Like
#12

Vậy là quy hoạch động 3 chiều à anh :thinking:

#13

chứ còn gì nữa :hocho: 201*201*201 ~ 8 triệu < 1s được mà

2 Likes
#14

ok anh, để em nghiên cứu thử :pray:

#15

Bây giờ quay lại thì ok đúng rồi, cảm ơn anh nhiều
Nhưng mà có cách hay quá trình nào để suy nghĩ ra công thức không anh, chứ hỏi bài suốt thì tư duy cũng không mở mang lên được mấy @@

#16

chắc làm nhiều rồi quen thôi :V toy chắc làm hơn 50 bài mới hơi hơi quen đó :V :V hên xui mò đúng hướng hay ko nữa :hocho:

2 Likes
#17

có link dạng bài nào tương tự không anh, cho em xin với @@

#18

em vô leetcode rồi lọc bài dp thôi, ví dụ: https://leetcode.com/problemset/?page=1&topicSlugs=dynamic-programming&difficulty=MEDIUM

ơ lọc mấy cái easy trước làm quen rồi chơi medium :V

1 Like
#20

Sao bạn, copy câu này làm gì @babymon1

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?