Чтобы решить эту задачу, давайте проанализируем движение жуков и определим, сколько клеток остается непосещенными.
- У нас есть поле размером 10 × 12. Это означает, что всего клеток на поле 10 * 12 = 120.
- Жуки начинаются в левой верхней клетке (1, 1) и должны добраться до правой нижней клетки (10, 12).
- Каждый жук может перемещаться только вправо или вниз. Чтобы добраться от (1, 1) до (10, 12), жуку нужно сделать 9 шагов вниз и 11 шагов вправо, в сумме 20 шагов.
Теперь будем рассматривать, сколько клеток будет посещено жуками на их пути.
- Все жуки начнут с одной и той же клетки – (1, 1). Когда один из жуков начнет двигаться, он пройдет по всем клеткам, которые находятся на пути от (1, 1) до (10, 12).
- Эти клетки можно обозначить координатами, которые будут посещены, причем каждый жук будет следовать одной и той же траектории, только их пути могут немного различаться из-за выбора направления (вправо или вниз).
- Если мы посмотрим на путь, который могут пройти жуки, то они покроют следующие клетки: от (1, 1) до (10, 12), то есть клетку (i, j) для всех 1 ≤ i ≤ 10 и 1 ≤ j ≤ 12.
На самом деле, любые клетки, которые находятся на пути до (10, 12), включают:
- Все клетки в первой строке (с (1, 1) до (1, 12)), что дает 12 клеток.
- Все клетки в первой колонке (с (1, 1) до (10, 1)), что дает 10 клеток.
- Но клетка (1, 1) считается дважды, ее нужно вычесть.
Таким образом, общее количество посещенных клеток:
- 12 + 10 - 1 = 21 клетка.
Теперь мы можем найти, сколько клеток не было посещено:
Количество непосещённых клеток = Общее количество клеток - Посещённые клетки = 120 - 21 = 99.
Таким образом, наименьшее количество клеток, не посещённых ни одним жуком, составляет 99.