в граф. Найти для
в граф. Найти для него минимальное связное доминирующее множество.
о95_4 Очевидно, что при L>M или K<2 решений нет. Предположим, что M>L. За две поездки перевозится K-1 представитель этого сообщества. Если (K-1) кратно (M+L-1), то требуется на одну поездку меньше, в противном случае - на одну больше.
Примеры. 1. M=9, L=8, K=5. (9,8,1)? (6,6,0)? (7,6,1)? (4,4,0)? (5,4,1)? (2,2,0)? (3,2,1)? (0,0,0). Итого, семь поездок.
Тесты.
M L K Ответ
4 4 2 нет решения
5 5 3 11
8 7 3 13
5 5 5 5
73 73 4 143
91 44 4 89
10000 9999 3 19997
10000 9998 4 13331
2. M=7, L=5, K=3. (7,5,1)? (5,4,0)? (6,4,1)? (4,3,0)? (5,3,1)? (3,2,0)? (4,2,1)? (2,1,0)? (3,1,1)? (1,0,0)? (2,0,1)? (0,0,0). Итого, одиннадцать поездок.
4. 3. M=6, L=5, K=6. (6,5,1)? (3,2,0)? (3,3,1)? (0,0,0).
Не рассмотрен случай M=L(особый). Его следует рассматривать отдельно для каждого значения K. Пусть K=2. Если M>3, то решений нет. Действительно, при любом способе перевозки возникает ситуация, в которой количество
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
