Maxi Taxi

Submit solution

Points: 1
Time limit: 1.0s
Haskell 20.0s
Memory limit: 256M
Haskell 1G

Problem type
Allowed languages
C, C++, Haskell, Java, Python

After The Backstreet Boys' Reunion Concert finally finished, all the Cam-Hallers wanted to return to their beloved nest. It has been so long since anyone has driven anywhere they all decided to take taxis (ride-sharing companies have long gone bankrupt). We know that the \(i\)-th group consists of \(1 \leq f_i \leq 4\) friends who will only travel together. Each taxi can carry at most four people. What is the minimum number of cars needed if each group should ride in the same taxi (one taxi can take more than one group if they fit)?

Input Specification

Two lines. The first contains an integer \(1 \leq n \leq 10^6\) - the number of groups. The second line contains a sequence of \(n\) space-separated integers \(f_1, f_2, ...,f_n (1 \leq f_i \leq 4)\) - the number of children in the \(i\)-th group.

Output Specification

The minimal number of taxis needed to get all the Cam-Hallers to Cameron Hall.

Sample Input 1

1 1 2 4 3 3

Sample Output 1


Sample Input 2

1 1 4 4 2 3 2

Sample Output 2



For the last sample we can sort the Cam-Hallers as follows:

  • The third group (four)
  • The fourth group (four)
  • The fifth and seventh group (two and two)
  • The first and sixth group (one and three)
  • The second 'group' (one)


  • 0
    PHPeasant  commented on Sept. 10, 2020, 6:09 p.m.

    Bounds have been increased to \(10^6\).