Задача
На олимпиаду по информатике прибыло $n$ команд, каждая из которых состоит из $a_i$ мальчиков и $b_i$ девочек $(1 ≤ i ≤ n)$. Для проживания имеются одинаковые комнаты по $m$ мест в каждой. Какое наименшее количество комнат достаточно для размещения участников олимпиады, если мальчиков с девочками селить вместе запрещено?
Входные данные
Первая строка содержит числа $n$ и $m$. Каждая следующая из $n$ строк содержит пару чисел $a_i$ , $b_i$ $(1 ≤ i ≤ n)$. Все числовые значения целые неотрицательные и не превышают $100$.
Выходные данные
Вывести наименьшее необходимое количество комнат.
Тесты
| № | Входные данные | Выходные данные |
| 1 | 2 3 2 1 3 2 |
3 |
| 2 | 3 5 5 8 2 3 6 1 |
6 |
| 3 | 2 2 1 1 1 3 |
3 |
| 4 | 4 2 1 3 5 1 2 7 3 1 |
12 |
| 5 | 7 2 5 6 3 4 2 5 1 3 9 3 8 7 6 4 |
33 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> #include <cmath> using namespace std; int main() { int n, m, a, b, k = 0, l = 0; cin >> n >> m; while (n--) { cin >> a >> b; k += a; l += b; } cout << (k + m - 1) / m + (l + m - 1) / m ; return 0; } |
Решение задачи
Для решения задачи найдём общее количество мальчиков и девочек, затем по отдельности посчитаем в каком количестве комнат они поместятся, но когда мы целочисленно делим количество детей на вместимость одной комнаты, мы определяем какое количество комнат будет заполнено полностью. Но, если количество детей не кратно количеству комнат, то полученный ответ должен быть на единицу больше. Для этого к количеству детей добавим ещё ровно столько, сколько нужно для того, чтобы ответ стал больше на единицу, то есть $m$, но на один меньше, чтобы при количестве детей кратном ответ был прежний. А после сложим полученные значения.