Codeforces - Taxi (/problemset/problem/158/B)

Solution.java

import java.io.*;
import java.util.*;
import java.math.*;

public class Solution
{
	BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer tokenizer=null;

	public static void main(String[] args) throws IOException
	{
		new Solution().execute();
	}

	void debug(Object...os)
	{
		System.out.println(Arrays.deepToString(os));
	}

	int ni() throws IOException
	{
		return Integer.parseInt(ns());
	}

	long nl() throws IOException
	{
		return Long.parseLong(ns());
	}

	double nd() throws IOException
	{
		return Double.parseDouble(ns());
	}

	String ns() throws IOException
	{
		while (tokenizer == null || !tokenizer.hasMoreTokens())
			tokenizer = new StringTokenizer(br.readLine());
		return tokenizer.nextToken();
	}

	String nline() throws IOException
	{
		tokenizer=null;
		return br.readLine();
	}


	//Main Code starts Here
	int totalCases, testnum;

	// number of groups
	int n;
	// number of groups with 1,2,3,4 number of people
	int arr[];

	void execute() throws IOException
	{
		totalCases = 1;
		for(testnum = 1; testnum <= totalCases; testnum++)
		{
			if(!input())
				break;
			solve();
		}
	}

	void solve() throws IOException
	{
		int count = 0;

		// all groups of 4 will need 1 car each
		count += arr[3];

		// all groups of 3 will need 1 car each
		count += arr[2];

		// groups of 1 can be clubbed with above group of 3
		// the left will remain if more than group of 3
		arr[0] -= Math.min(arr[0], arr[2]);

		// groups of 2 can go together (2 at a time), so /2
		count += arr[1]/2;

		// if odd number of 2 groups 1 will be left
		arr[1] = arr[1] % 2;


		if (arr[1] == 0) {
			// if no group of 2 left then only need for rest of group of 1
			count += (arr[0] + 3)/4;
		} else {
			// if 1 group of 2 left then only need for 1 group of 2 + rest of group of 1
			count += (arr[0] + 2 + 3)/4;
		}
		System.out.println(count);
	}

	boolean input() throws IOException
	{
		n = ni();
		arr = new int[4];
		for (int i = 0; i < n; i++) {
			arr[ni() - 1]++;
		}
		return true;
	}
}