/*
После окончания уроков n групп школьников вышли на улицу и собрались ехать
домой к Поликарпу на празднование его дня рождения.
Известно, что i-ая группа состоит из si друзей (1≤si≤4),
которые не хотят расставаться по пути к Поликарпу.
Решено ехать на такси. Каждая машина может вместить не более четырех пассажиров.
Какое минимальное количество машин потребуется школьникам,
если каждая группа должна целиком находиться в одной из машин такси
(но одна машина может вмещать более чем одну группу)?
Входные данные
В первой строке записано целое число n (1≤n≤105) — количество групп школьников.
Вторая строка содержит последовательность целых чисел s1,s2,...,sn (1≤si≤4).
Числа записаны через пробел, si — количество ребят в i-ой группе.
Выходные данные
Выведите единственное число — минимальное необходимое количество такси,
чтобы отвезти всех ребят к Поликарпу.
*/
import java.util.Arrays;
class Main {
public static void main(String[] args) {
System.out.println("Hello World!");
int[] arr = new int[5];
for (int i = 0; i < arr.length; i++)
arr[i] = (int) Math.round(Math.random() * 3 + 1);
Arrays.sort(arr);
int count = 1;
int taxi = 0;
for (int i = 0; i < arr.length; i++) {
if ((taxi + arr[i]) <= 4) {
taxi += arr[i];
arr[i] = 5;
}
else {
for (int j = i + 1; j < arr.length; j++) {
if (taxi + arr[j] <= 4) {
taxi += arr[j];
arr[j] = 5;
}
}
count += 1;
taxi = arr[i];
}
}
System.out.println(Arrays.toString(arr));
System.out.println(count);
}
}
