CodeForces/Problem158B.java at master · raymondcho/CodeForces · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package CodeForces;

import java.util.*;

public class Problem158B
{
	public static int findMinTaxi(int[] groups)
	{
		int count = 0;
		int g1 = 0;
		int g2 = 0;
		int g3 = 0;
		for (int i = 0; i < groups.length; i++)
		{
			if (groups[i] == 4)
			{
				count++;
			}
			else if (groups[i] == 1)
			{
				g1++;
			}
			else if (groups[i] == 2)
			{
				g2++;
			}
			else if (groups[i] == 3)
			{
				g3++;
			}
			else
			{}
		}

		if (g3 == g1)
		{
			count = count + g3;
			g3 = 0;
			g1 = 0;
		}
		else if (g3 > g1)
		{
			count = count + g1;
			g3 = g3 - g1;
			g1 = 0;

		}
		else  // (g3 < g1)
		{
			count = count + g3;
			g1 = g1 - g3;
			g3 = 0;

		}

		if (g2 % 2 == 0)
		{
			count = count + (g2/2);
			g2 = 0;
		}
		else
		{
			count = count + (g2/2);
			g2 = 1;
		}

		count = count + g3;
		g3 = 0;

		while (g1 > 0 && g2 > 0)
		{
			if (g2 > 0 && g1 > 1)
			{
				count++;
				g2--;
				g1 = g1 - 2;
			}
			else
			{
				count++;
				g2--;
				g1--;
			}
		}

		count = count + g2;
		g2 = 0;

		count = count + (g1/4);
		if (g1 % 4 != 0)
		{
			count ++;
		}
		g1 = 0;

		return count;
	}

	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int[] groups = new int[n];
		for (int i = 0; i < n; i++)
		{
			groups[i] = scan.nextInt();
		}
		scan.close();
		System.out.println(findMinTaxi(groups));
	}
}