Editorial for Maxi Taxi

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Editorialist: PHPeasant, Tommoa

Maxi Taxi requires you to find how many taxis are needed to cart our compatriots to Cameron Hall. The main observation to make is that we only need the number of taxis and not a specific solution. This suggests we could simply try to fill as many taxis as possible in a greedy fashion; which is correct. We can trivially fill as many cars as groups of four as possible. We match groups of threes with as many groups of ones as possible. Then twos with twos, twos with ones and finally ones with ones. Any remaining group will ride in their own car.

An example implementation in C++14 is given below:

#include <bits/stdc++.h>

using namespace std;

int main() {

    int N;
    cin >> N;

    array<int, 4> cars = { 0, 0, 0, 0 };
    for (int i = 0; i < N; ++i) {
        int t;
        cin >> t;
    cars[3] += cars[2];
    cars[0] = max(0, cars[0] - cars[2]);
    cars[3] += cars[1] >> 1;
    if ((cars[1]) & 1) {
        cars[3] += 1;
        cars[0] = max(0, cars[0] - 2);
    cars[3] += (cars[0] >> 2) + (cars[0] % 4 > 0);

    cout << cars[3] << '\n';


There are no comments at the moment.