Cần giúp đỡ thuật toán xếp nhóm

[qg2406]

Ai có thể gợi ý cho e trường hợp thuật toán này k, em nghĩ mãi k biết các xếp cùng nhóm

Các sinh viên được chia ra làm nhiều nhóm nhỏ. mỗi nhóm có không quá 4 thành viên.

Sau khi bánh đã chín, tất cả mọi người được hưởng thành quả những chiếc bánh mình làm ra.

Mỗi chiếc bánh chưng được chia cho tối đa là 4 người ăn.

Vì các nhóm rất đoàn kết nên họ muốn ăn bánh cùng với thành viên nhóm của mình.

Lưu ý: 1 chiếc bánh chưng có thể chia cho nhiều hơn 1 nhóm ăn (ví dụ: 2 nhóm 2 người có thể ăn chung 1 bánh)

Bạn hãy giúp người quản lý tính số bánh chưng tối thiểu cần thiết để chia đủ cho tất cả mọi người đều được ăn.

Input:

• Dòng đầu tiên chứa số nguyên N (1<=N<=10^5).
• Dòng thứ 2 chứa một dãy N số nguyên a1,a2,…aN. các số nguyên cách nhau ít nhất 1 khoảng trống. Với a[i] là số thành viên của nhóm thứ ii.

Output:

• 1 số nguyên duy nhất là số lượng bánh chưng tối thiểu.

[rogp10]

Nhóm 4 người => auto 1 chiếc
còn lại thì bạn giảm xuống từng nấc rồi thử gom lại

[qg2406]

Mình chưa hiểu ý của bạn lắm

[Nobita1]

Bài này mình hiểu thì, nhóm 4 người auto 1 chiếc bánh, nhóm 3 người với nhóm 1 người ghép vào với nhau auto 1 chiếc, các nhóm 2 người ghép vào với nhau auto 1 chiếc:

Lúc này các trường hợp còn lại có thể là: nhóm 3 người và nhóm 2 người hoặc nhóm 1 người và nhóm 2 người: thì trường hợp 1 là 2 chiếc, trường hợp 2 là 1 chiếc

[SITUVN.gcd]

• Gom nhóm 4 người trước.
• Gom nhóm 3 và bắt cặp với các nhóm 1. Có thể còn dư vài nhóm 1 hoặc vài nhóm 3 chưa bắt cặp.
• Gom nhóm 2 và bắt cặp với nhóm 2. Có thể còn dư 1 nhóm 2.
• Các nhóm dư còn lại bắt cặp với nhau cho đủ 4 hoặc ít hơn:
  • Nếu dư vài nhóm 1:
    • Duy nhất 1 nhóm (2 + 1 + 1) hoặc (2 + 1) hoặc (2).
    • 4 nhóm 1.
    • Ít hơn 3 nhóm 1.
  • Nếu dư vài nhóm 3: Không thể bắt cặp giữa 2 và 3.
    • Vài nhóm 3.
    • Duy nhất 1 nhóm 2.

Các trường hợp không nhất thiết xảy ra đồng loạt.