Миша ест мёд. Каждую минуту он решает: продолжать есть или начать бежать.
Миша бежит. За одну минуту он перемещается на ≤ s клеток по траве (вверх/вниз/влево/вправо). Через деревья и ульи ходить нельзя.
Пчёлы распространяются. Каждую минуту каждый рой пчёл распространяется на все соседние клетки с травой (4 направления).
Миша не может входить в клетку, где уже есть пчёлы.
Задача
Найти максимальное количество минут T, которое Миша может есть мёд, и при этом успеть добраться до дома.
Наивный подход: перебрать все T?
for (int T = 0; T <= n * n; T++) {
if (canEscape(T))
best = T; // запомнить лучший ответ
}
T
Может добраться?
Как проверить?
0
?
BFS ... O(n²)
1
?
BFS ... O(n²)
...
...
...
n²
?
BFS ... O(n²)
Итого
O(n²) проверок × O(n²) каждая = O(n4) — слишком медленно!
Ключевое наблюдение: монотонность
T=0
✔
T=1
✔
T=2
✔
T=3
✔
T=4
✔
T=5
✘
T=6
✘
T=7
✘
← зелёная зона (можно) →← красная зона (нельзя) →
💡 Ключевая идея
Если Миша может добраться домой, съев T минут, то он точно может добраться, съев T−1 минут.
Потому что у него будет ещё больше времени на побег (пчёлы меньше распространились).
Ответ — последний ✔. Как найти эту границу быстро?
Бинарный поиск по ответу!
Шаг 1: lo=0, hi=7, mid=3
T=0
T=1
T=2
T=3
mid ✔
T=4
T=5
T=6
T=7
canEscape(3) = true → lo = 3
Шаг 2: lo=3, hi=7, mid=5
T=0
T=1
T=2
T=3
T=4
T=5
mid ✘
T=6
T=7
canEscape(5) = false → hi = 4
Шаг 3: lo=3, hi=4, mid=4
T=0
T=1
T=2
T=3
T=4
mid ✔
T=5
T=6
T=7
canEscape(4) = true → lo = 4
lo = hi = 4. Ответ: T = 4
💡 Совет
Вместо O(n²) проверок — всего O(log n²) = O(log n). Итого: O(n² log n) — быстро!
Структура решения: 3 части
Часть 1
Multi-source BFS от всех ульев
Считаем beeTime[][] Когда пчёлы доберутся до каждой клетки
O(n²) — один раз
→
Часть 2
canEscape(T) BFS от Миши
Проверяем: можно ли добраться домой, если ел T минут?
O(n²) за вызов
→
Часть 3
Бинарный поиск на T
Ищем максимум T где canEscape(T) ещё true
O(log n) вызовов Части 2
Часть 1: Multi-source BFS — идея
Обычный BFS
Один источник → одна волна
Multi-source BFS
Много источников → одновременные волны
💡 Ключевая идея
Трюк: кладём ВСЕ стартовые вершины в очередь одновременно с dist = 0. Дальше — обычный BFS. Волна распространяется от всех источников параллельно.
Multi-source BFS: пошагово
Сетка 5×5. У = улей, Д = дерево, М = Миша, Дом = дом
Шаг 0: Все ульи в очередь с beeTime = 0
-1
-1
-1
X
-1
0
-1
-1
-1
-1
-1
X
-1
-1
-1
-1
-1
0
-1
-1
-1
-1
-1
-1
-1
Шаг 1: Соседи ульев → beeTime = 1
1
-1
-1
X
-1
0
1
-1
-1
-1
1
X
1
-1
-1
-1
1
0
1
-1
-1
-1
1
-1
-1
Multi-source BFS: шаг 2
Соседи единичек получают beeTime = 2. Деревья непроходимы.
1
2
-1
X
-1
0
1
2
-1
-1
1
X
1
2
-1
2
1
0
1
2
-1
2
1
2
-1
💡 Обратите внимание
Волна от обоих ульев расходится параллельно. Каждая клетка получает beeTime от ближайшего улья. Клетка Миши (4,0) ещё не достигнута — beeTime = −1.
Multi-source BFS: итог
Все клетки заполнены — каждая содержит время прибытия ближайшего роя пчёл
1
2
3
X
5
0
1
2
3
4
1
X
1
2
3
2
1
0
1
2
3
2
1
2
3
💡 Обратите внимание
Клетки с beeTime = 1 (красные) образуют барьер вокруг ульев. На этой плотной сетке барьер полностью окружает Мишу — ему некуда бежать (ответ = −1).
Multi-source BFS: код
// beeTime[r][c] = когда пчёлы доберутся до (r,c)
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
queue<pair<int,int>> q;
for (каждый улей (r, c)) { // ← ВСЕ ульи сразу!
beeTime[r][c] = 0;
q.push({r, c});
}
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& grid[nr][nc] == GRASS
&& beeTime[nr][nc] == -1) {
beeTime[nr][nc] = beeTime[r][c] + 1;
q.push({nr, nc});
}
}
}
👉 Кладём ВСЕ ульи сразу — единственное отличие от обычного BFS!
👉 Пчёлы распространяются по 1 клетке в минуту
💡 Ключевая идея
Сложность: O(n²) — каждая клетка обрабатывается ровно один раз.
Часть 2: canEscape(T) — может ли Миша убежать?
Определение
canEscape(T) = true, если Миша может добраться из стартовой клетки до дома, при условии что он начинает бежать в момент времени T.
🍯 Миша ест мёд 0 … T
▶
🏃 Миша бежит домой T … ?
🐝 Пчёлы распространяются всё это время →
⚠️ Осторожно
Правило: Миша может войти в клетку (r,c) в момент времени t, только если t < beeTime[r][c].
То есть Миша должен прийти строго раньше пчёл.
canEscape(T): визуализация
Сетка 6×6, улей в (0,0), Миша в (5,0), дом в (5,5), s=1. Числа = beeTime.
canEscape(4) = true ✔
Заблокированы клетки с bt ≤ 4
0
1
2
3
4
5
1
2
3
4
5
6
2
3
4
5
6
7
3
4
5
6
7
8
4
5
6
7
8
9
🐻
→
→
→
→
🏠
t=4<5✔ → 5<6✔ → 6<7✔ → 7<8✔ → 8<9✔ → 9<10✔
canEscape(5) = false ✘
Заблокированы клетки с bt ≤ 5
0
1
2
3
4
5
1
2
3
4
5
6
2
3
4
5
6
7
3
4
5
6
7
8
4
5
6
7
8
9
🐻 bt=5
6
7
8
9
🏠
T=5, bt[5][0]=5 → 5 < 5? Нет! Старт невозможен ✘
💡 Монотонность
Если canEscape(T) = true, то canEscape(T−1) тоже true. Ответ — максимальный T с canEscape(T) = true. Здесь: T* = 4.
canEscape(T=1): BFS от Миши пошагово
Предположим s=1 (Миша: 1 клетка/мин). Та же сетка 5×5.
canEscape(4) = true! Миша опережает пчёл на каждом шаге.
canEscape(T=5): Миша в (5,0) в момент 5, но beeTime[5][0] = 5. 5 < 5?Нет! Пчёлы уже тут.
canEscape(T): код
bool canEscape(int T) {
memset(mishaTime, -1, sizeof(mishaTime));
// Пчёлы уже на стартовой клетке?
if (T >= beeTime[misha_r][misha_c])
return false;
mishaTime[misha_r][misha_c] = T;
queue<pair<int,int>> q;
q.push({misha_r, misha_c});
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
if (r == home_r && c == home_c)
return true; // Добрались до дома!
int t = mishaTime[r][c] + 1;
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& grid[nr][nc] == GRASS
&& mishaTime[nr][nc] == -1
&& t < beeTime[nr][nc]) {
mishaTime[nr][nc] = t;
q.push({nr, nc});
}
}
}
return false;
}
👉 Стартует в момент T (после T минут еды)
👉 Как только достигли дома — сразу true
👉 t < beeTime[nr][nc]
Миша должен прийти СТРОГО раньше пчёл
А как учесть скорость s?
⚠️ Осторожно
В реальной задаче Миша перемещается на до s клеток за одну минуту. Это значит, что за одну минуту Миша может сделать до s шагов BFS.
Подход 1 (простой):
BFS, но время увеличивается на 1 не после каждого шага, а после каждых s шагов. Каждый «слой» содержит все клетки, достижимые за ≤ s шагов.
Подход 2 (элегантный):
Обычный BFS считает расстояние в шагах. Потом: mishaTime[r][c] = T + ceil(dist / s).
💡 Совет
Для первого понимания задачи можно считать s = 1. Концептуально ничего не меняется — просто Миша движется быстрее.
Часть 3: Бинарный поиск — шаблон
Ищем МИНИМУМ x, где f(x) = true
// false false false TRUE TRUE TRUE
// ^--- ищем это
int lo = MIN, hi = MAX;
while (lo < hi) {
int mid = (lo + hi) / 2; // вниз
if (f(mid)) hi = mid;
else lo = mid + 1;
}
// ответ = lo
Наш случай! Ищем МАКСИМУМ x
// TRUE TRUE TRUE false false false
// ^--- ищем это
int lo = MIN, hi = MAX;
while (lo < hi) {
int mid = (lo + hi + 1) / 2; // ВВЕРХ!
if (f(mid)) lo = mid;
else hi = mid - 1;
}
// ответ = lo
⚠️ Осторожно
Почему (lo + hi + 1) / 2?
При lo + 1 = hi формула (lo + hi) / 2 = lo → бесконечный цикл!
Добавляя +1, округляем ВВЕРХ и гарантируем, что mid > lo.
Бинарный поиск для Медведя Миши
// Шаг 0: предвычисляем beeTime[][]
computeBeeTime(); // O(n^2), один раз
// Особый случай
if (!canEscape(0)) {
printf("-1\n");
return;
}
// Бинарный поиск по T
int lo = 0, hi = n * n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (canEscape(mid))
lo = mid;
else
hi = mid - 1;
}
printf("%d\n", lo);
Трассировка (n=6):
lo
hi
mid
canEscape
Действие
0
36
19
false
hi=18
0
18
10
false
hi=9
0
9
5
false
hi=4
0
4
3
true
lo=3
3
4
4
false
hi=3
lo = hi = 3
Ответ: T = 3
💡 Совет
Всего 5 вызовов canEscape вместо 36. log₂(36) ≈ 5.
Полный пример: от начала до ответа
n = 5, s = 2. G=трава, H=дом, M=Миша, T=дерево, B=улей
Этап 1: Сетка → beeTime
G
G
G
G
H
G
G
T
G
G
G
T
G
G
G
G
G
G
B
G
M
G
G
G
G
Этап 2: Бинарный поиск
lo
hi
mid
check
0
25
13
F
hi=12
0
12
7
F
hi=6
0
6
4
T
lo=4
4
6
6
F
hi=5
4
5
5
F
hi=4
lo=hi=4
T=4
Этап 3: canEscape(4) — Миша находит путь домой (s=2: 2 клетки/мин)
Анализ сложности
Часть
Операция
Сложность
Сколько раз
1. Multi-source BFS
BFS по сетке n×n
O(n²)
1 раз
2. canEscape(T)
BFS по сетке n×n
O(n²)
за каждый вызов
3. Бинарный поиск
O(log n²) вызовов
O(n² · log n)
—
Итого: O(n²) + O(n² · 2 log n) = O(n² log n)
Подход
Сложность
n=800
Время
Brute force
O(n4)
4 · 1011
~4000 сек
Бинарный поиск
O(n² log n)
6 · 106
~0.06 сек
↓ в 65 000 раз быстрее! ↓
Паттерн: бинарный поиск по ответу
💡 Ключевая идея: когда использовать?
Задача спрашивает «найти максимум/минимум X»
Вы можете написать функцию check(X): возможно ли достичь X?
Функция монотонна: если check(X) = true, то check(X−1) = true (для макс.) или check(X+1) = true (для мин.)
// Ищем максимум X, где check(X) = true
int lo = MIN_ANSWER, hi = MAX_ANSWER;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (check(mid)) lo = mid;
else hi = mid - 1;
}
// ответ = lo
Вопрос для размышления
Как понять, что задача решается бинпоиском по ответу? Подсказка: ищите фразы «максимальный минимум», «минимальное максимальное», «можно ли уложиться в X?»
Классические задачи на бинарный поиск по ответу
Задача
Что бинпоищем?
Что проверяем?
Медведь Миша (наша)
Макс. T (время еды)
BFS: можно ли убежать?
Коровы на стойла
Макс. min расстояния
Жадно: можно ли разместить k коров?
Разрезать верёвки
Макс. длина куска
Жадно: можно ли получить k кусков?
Агрессивные коровы (SPOJ)
Макс. min расстояния
Жадно
Пираты (IOI 2008)
Мин. max нагрузки
Жадно/DP
Сбор яблок
Макс. время
Жадно: можно ли собрать за T?
💡 Ключевая идея
Если в задаче написано «найти максимальное/минимальное значение» и вы можете написать check(X) — это почти наверняка бинпоиск по ответу.
Типичные ошибки
⚠️ 1. Неправильное округление
// НЕПРАВИЛЬНО (для поиска максимума):
int mid = (lo + hi) / 2; // бесконечный цикл при lo+1=hi!
// ПРАВИЛЬНО:
int mid = (lo + hi + 1) / 2; // гарантируем прогресс
⚠️ 2. Нестрогое неравенство для пчёл
// НЕПРАВИЛЬНО:
if (t <= beeTime[nr][nc]) // одновременно = ужалят!
// ПРАВИЛЬНО:
if (t < beeTime[nr][nc]) // строго раньше
⚠️ 3. Забыть проверить стартовую клетку
// Сначала проверяем T < beeTime[misha_r][misha_c]
⚠️ 4. Забыть особый случай T=0
if (!canEscape(0)) { printf("-1\n"); return; }
Полный код решения
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 805;
int n, s;
char grid[MAXN][MAXN];
int beeTime[MAXN][MAXN];
int mishaTime[MAXN][MAXN];
int misha_r, misha_c, home_r, home_c;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
// ===== ЧАСТЬ 1: Multi-source BFS от пчёл =====
void computeBeeTime() {
memset(beeTime, -1, sizeof(beeTime));
queue<pair<int,int>> q;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 'B') {
beeTime[i][j] = 0;
q.push({i, j});
}
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& grid[nr][nc] != 'T' && grid[nr][nc] != 'B'
&& beeTime[nr][nc] == -1) {
beeTime[nr][nc] = beeTime[r][c] + 1;
q.push({nr, nc});
}
}
}
}
// ===== ЧАСТЬ 2: canEscape(T) =====
bool canEscape(int T) {
memset(mishaTime, -1, sizeof(mishaTime));
if (beeTime[misha_r][misha_c] != -1
&& T >= beeTime[misha_r][misha_c])
return false;
mishaTime[misha_r][misha_c] = T;
queue<pair<int,int>> q;
q.push({misha_r, misha_c});
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (r == home_r && c == home_c) return true;
int t = mishaTime[r][c] + 1;
for (int d = 0; d < 4; d++) {
int nr = r + dx[d], nc = c + dy[d];
if (nr >= 0 && nr < n && nc >= 0 && nc < n
&& grid[nr][nc] != 'T' && grid[nr][nc] != 'B'
&& mishaTime[nr][nc] == -1
&& (beeTime[nr][nc] == -1 || t < beeTime[nr][nc])) {
mishaTime[nr][nc] = t;
q.push({nr, nc});
}
}
}
return false;
}
// ===== ЧАСТЬ 3: Бинарный поиск =====
int main() {
scanf("%d %d", &n, &s);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
scanf(" %c", &grid[i][j]);
if (grid[i][j] == 'M') { misha_r = i; misha_c = j; }
if (grid[i][j] == 'H') { home_r = i; home_c = j; }
}
computeBeeTime();
if (!canEscape(0)) { printf("-1\n"); return 0; }
int lo = 0, hi = n * n;
while (lo < hi) {
int mid = (lo + hi + 1) / 2;
if (canEscape(mid)) lo = mid;
else hi = mid - 1;
}
printf("%d\n", lo);
}
■ Часть 1: строки 13-34■ Часть 2: строки 36-60■ Часть 3: строки 62-78
Учёт скорости s > 1
В нашем коде мы упростили: Миша ходит на 1 клетку за минуту. В реальной задаче Миша может ходить на до s клеток. Как это изменить?
💡 Вариант 1
В canEscape использовать BFS с «минутными слоями». За одну минуту Миша обрабатывает до s уровней BFS. Время увеличивается на 1 только после обработки s уровней.
💡 Вариант 2 (элегантный)
Сначала обычный BFS для подсчёта расстояния в шагах (dist_steps). Потом:
// После обычного BFS, где dist[r][c] = число шагов:
int arrivalTime = T + (dist[r][c] + s - 1) / s;
if (arrivalTime < beeTime[r][c]) {
// Миша может пройти через эту клетку
}
Что мы сегодня изучили
Multi-source BFS — BFS от нескольких источников одновременно. Просто кладём все источники в очередь сразу.
Бинарный поиск по ответу — если можно проверить check(X) и свойство монотонно, бинпоиск находит оптимум.
Шаблон бинпоиска — для максимума: (lo + hi + 1) / 2, для минимума: (lo + hi) / 2.
Комбинация техник — BFS + бинпоиск = мощный инструмент для задач на сетках.
Анализ сложности — O(n² log n) вместо O(n4).
💡 Запомните
Бинарный поиск по ответу — один из 5 самых частых приёмов на IOI. Если вы его освоите, вы сможете решать целый класс задач.
Задачи для самостоятельного решения
#
Задача
Ссылка
Бинпоиск по чему?
check()
1
Разрезать верёвки
e-olymp 3966
Макс. длина куска
Жадность
2
Array Division (CSES 1085)
cses.fi
Мин. max суммы
Жадность
3
Fly (CF 1011C)
codeforces.com
Макс. масса
Жадность
4
Factory Machines (CSES 1620)
cses.fi
Мин. время
Жадность
5
Multiplication Table (CSES 2422)
cses.fi
k-й элемент
Подсчёт: сколько ≤ X?
💡 Совет
Начните с задач 1 и 4 — они самые прямолинейные.
Задача 5 — хитрая, но очень красивая.