Никак не могу написать код для следующей , (25 ) желательно на с++ или на паскале заранее < 3 : после окончания уроков n групп школьников вышли на улицу и собрались ехать домой к поликарпу на празднование его дня рождения. известно, что i-ая группа состоит из si друзей (1 ≤ si ≤ 4), которые не хотят расставаться по пути к поликарпу. решено ехать на такси. каждая машина может вместить не более четырех пассажиров. какое минимальное количество машин потребуется школьникам, если каждая группа должна целиком находиться в одной из машин такси (но одна машина может вмещать более чем одну группу)? входные данные в первой строке записано целое число n (1 ≤ n ≤ 105) — количество групп школьников. вторая строка содержит последовательность целых чисел s1, s2, sn (1 ≤ si ≤ 4). числа записаны через пробел, si — количество в i-ой группе. выходные данные выведите единственное число — минимальное необходимое количество такси, чтобы отвезти всех к поликарпу.

Ответы

ArtemkaRus71 24.12.2023 18:20

Код для решения данной задачи на C++:

```cpp
#include

int main() {
int n; // количество групп школьников
std::cin >> n; // ввод количества групп

int s[n]; // массив, содержащий количество друзей в каждой группе

for (int i = 0; i < n; i++) {
std::cin >> s[i]; // ввод количества друзей в каждой группе
}

int count[5] = {0}; // массив для подсчета групп с определенным количеством друзей

for (int i = 0; i < n; i++) {
count[s[i]]++; // подсчет групп с определенным количеством друзей
}

int taxis = count[4]; // количество такси, в которых поместятся группы из 4 друзей

int threes = std::min(count[3], count[1]); // количество такси, в которых поместятся группы из 3 друзей и отдельные друзья
count[3] -= threes; // уменьшение счетчика групп из 3 друзей
count[1] -= threes; // уменьшение счетчика отдельных друзей

taxis += threes; // добавление такси для групп из 3 друзей и отдельных друзей

int twos = count[2] / 2; // количество такси, в которых поместятся пары друзей
count[2] -= twos * 2; // уменьшение счетчика пар друзей

taxis += twos; // добавление такси для пар друзей

int ones = count[1] / 4; // количество такси для отдельных друзей
count[1] -= ones * 4; // уменьшение счетчика отдельных друзей

if (count[1] > 0) {
ones++; // если остались отдельные друзья, требуется еще одно такси
}

taxis += ones; // добавление такси для отдельных друзей

std::cout << taxis << std::endl; // вывод количества такси

return 0;
}
```

Объяснение решения:

1. Мы считываем количество групп школьников и количество друзей в каждой группе.
2. Создаем массив `count`, который будет подсчитывать количество групп с определенным количеством друзей. Инициализируем его нулями.
3. Проходимся по каждой группе и увеличиваем счетчик для соответствующего количества друзей.
4. Далее мы начинаем определять количество такси, которые понадобятся для каждого типа групп:
- Группы из 4 друзей могут поместиться в отдельные такси, поэтому мы добавляем количество таких групп в `taxis`.
- Группы из 3 друзей и отдельные друзья могут поместиться вместе в одно такси, поэтому мы определяем количество таких такси как минимум из количества групп из 3 друзей и количества отдельных друзей. Затем мы уменьшаем счетчики соответствующих групп.
- Пары друзей могут поместиться вместе в одно такси, поэтому мы определяем количество таких такси как количество пар друзей, деленное на 2. Затем мы уменьшаем счетчик пар друзей.
- Отдельные друзья могут быть размещены вместе в одно такси, если их количество не превышает 4. Поэтому мы определяем количество таких такси как количество отдельных друзей, деленное на 4. Затем мы уменьшаем счетчик отдельных друзей.
5. Если остались отдельные друзья (количество не делится на 4 без остатка), мы увеличиваем количество такси для отдельных друзей на 1.
6. Выводим количество такси.

ПОКАЗАТЬ ОТВЕТЫ

Другие вопросы по теме Информатика