CF: 158B (Taxi)


Problem link: http://codeforces.com/problemset/problem/158/B

Solution


// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main ()
{
    int n;

    scanf ("%d", &n);

    int freq [4];
    
    memset(freq, 0, sizeof freq);

    int input;

    for ( int i = 0; i < n; i++ ) {
        scanf ("%d", &input);

        freq [input - 1]++;
    }

    int cnt = freq [3];

    cnt += freq [2];

    freq [0] -= freq [2];

    cnt += (freq [1] / 2);

    freq [1] -= (freq [1] / 2 * 2);

    if (freq [1]) {
        cnt++;
        freq [0] -= 2;
    }

    if (freq [0] > 0) {
        cnt += (freq [0] / 4);
        freq [0] -= (freq [0] / 4 * 4);

        if (freq [0] > 0) cnt++;
    }

    printf ("%d\n", cnt);

    return 0;
}

// @END_OF_SOURCE_CODE

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s