0.Bánh Chưng


Submit solution

Points: 3 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Nhân dịp năm mới, trường UTC tổ chức cho sinh viên tham gia hoạt động ngoại khóa đó chính là nấu bánh chưng.

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 \le N \le 10^5)\).
  • Dòng thứ 2 chứa một dãy \(N\) số nguyên \(a_1, a_2, ..., a_N\). 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ứ \(i\).

Output

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

Example

Input 1

5
1 2 4 3 3

Output 1

4

Input 2

8
2 3 4 4 2 1 3 1

Output 2

5

Input 3

3
2 3 3

Output 3

3

Comments


  • 0
    quangIt1_k62  commented on Sept. 20, 2022, 10:31 p.m.

    :)


  • 0
    NguyenNgocDuy_CNTT4_K62  commented on Nov. 3, 2021, 11:33 a.m.

    :)


  • 1
    TICHPX  commented on Oct. 6, 2021, 11:34 p.m.

    code tham khảo Python

    if __name__ == '__main__':
        d = [0] * 5
        input()
        for x in map(int, input().split()): d[x] = d[x] + 1
        res = d[4] + d[3] + d[2] // 2
        d[1] -= d[3]
        if d[2] % 2 > 0:   res, d[1] = res + 1, d[1] - 2;
        if d[1] > 0: res += (d[1] + 3) // 4
        print(res)

    • 0
      ga123  commented on Oct. 7, 2021, 1:35 a.m.

      :3?


  • 0
    Manh_CNTT1_201210225  commented on Sept. 22, 2021, 11:23 a.m.

    :)


  • -2
    hhiep_CNTT1_K61  commented on Aug. 22, 2021, 5:37 a.m.

    :)


  • 0
    Hoan_CNTT_VA2_K61  commented on Aug. 13, 2021, 11:34 a.m.

    :)


  • 1
    duong123  commented on Sept. 14, 2020, 10:16 a.m.

    ai bị sai ở test 24 không mn?


  • -3
    culuamanh01  commented on Jan. 15, 2020, 11:17 p.m.

    ;))))


  • -4
    GauCon  commented on Dec. 5, 2019, 7:00 p.m.

    :)


  • 0
    TheDemonTuan  commented on Aug. 4, 2019, 10:18 a.m.

    :)


  • -2
    Vinh_TDH  commented on Aug. 3, 2019, 9:38 a.m. edited

    ))


  • 1
    Lamkz  commented on March 3, 2019, 11:04 p.m.

    :)


  • 0
    thanhnd  commented on Jan. 14, 2019, 1:56 a.m. edit 3

    :)