Решение задачи: Битые пиксели на мониторе

БИТЫЕ ПИКСЕЛИ

Условие задачи:

Алина очень аккуратно относится к своему рабочему месту, и тем неприятнее тот факт, что недавно на ее мониторе появились сразу два битых пикселя! Алина сразу записала характеристики монитора и повреждений, чтобы в дальнейшем сообщить их ремонтной службе. По ходу этого процесса Алина выяснила что в высоту ее монитор составляет \(n\) пикселей, а в ширину \(m\) пикселей. Первый битый пиксель появился на расстоянии \(a\) пикселей от верха экрана и \(b\) пикселей от левого края экрана. Второй же битый пиксель появился на расстоянии \(c\) пикселей от верха экрана и \(d\) пикселей от левого края экрана.

Но следующий факт, который заметила Алина был хуже всех предыдущих: каждый день все пиксели соседние к битым пикселям по стороне и по углу также становятся битыми! По этой причине Алина решила незамедлительно отнести монитор в ремонт, а по дороге ей стало интересно, через сколько дней все пиксели на ее мониторе стали бы битыми. Помогите ей найти ответ на этот вопрос.

Таблица входных данных:

Формат выходных данных:

Выведите одно целое число — через сколько дней все пиксели на мониторе стали бы битыми.

Решение:

Эта задача описывает процесс распространения "битых" пикселей на мониторе. Каждый день битыми становятся все пиксели, соседние по стороне и по углу к уже битым пикселям. Это означает, что область битых пикселей расширяется на 1 пиксель во всех направлениях каждый день.

Изначально у нас есть два битых пикселя. Пусть их координаты будут \((a, b)\) и \((c, d)\), где \(a\) и \(c\) — расстояние от верха экрана (строка), а \(b\) и \(d\) — расстояние от левого края экрана (столбец).

Монитор имеет размеры \(n\) (высота) на \(m\) (ширина).

Через \(k\) дней область битых пикселей вокруг каждого изначального битого пикселя расширится на \(k\) пикселей во все стороны. Это означает, что каждый изначальный битый пиксель \((x, y)\) будет "центром" квадрата битых пикселей размером \((2k+1) \times (2k+1)\).

Нам нужно найти минимальное количество дней \(k\), при котором весь монитор станет битым. Это произойдет, когда область, покрытая битыми пикселями, достигнет всех четырех границ монитора.

Рассмотрим расстояние от каждого изначального битого пикселя до каждой из четырех границ монитора:

• До верхней границы: \(x - 1\)
• До нижней границы: \(n - x\)
• До левой границы: \(y - 1\)
• До правой границы: \(m - y\)

Для каждого из двух начальных битых пикселей \((a, b)\) и \((c, d)\) мы должны найти максимальное расстояние до любой из границ. Это будет количество дней, за которое этот пиксель "достигнет" самой дальней границы, если бы он был единственным битым пикселем.

Для первого пикселя \((a, b)\):

Максимальное расстояние до границы: \(max(a-1, n-a, b-1, m-b)\)

Для второго пикселя \((c, d)\):

Максимальное расстояние до границы: \(max(c-1, n-c, d-1, m-d)\)

Однако, поскольку битые пиксели распространяются от двух точек одновременно, и эти области могут пересекаться, нам нужно найти минимальное количество дней, за которое весь монитор будет покрыт. Это означает, что каждая точка на мониторе должна быть достигнута хотя бы одним из распространяющихся "фронтов".

Проще всего представить это так: каждый день "фронт" битых пикселей расширяется на 1 пиксель. Если у нас есть два начальных битых пикселя, то через \(k\) дней они будут центрами двух квадратов со стороной \(2k+1\). Нам нужно найти такое минимальное \(k\), чтобы объединение этих двух квадратов покрыло весь монитор.

Это эквивалентно тому, чтобы найти максимальное из расстояний от любой точки монитора до ближайшего из двух начальных битых пикселей. Пусть \(P_1 = (a, b)\) и \(P_2 = (c, d)\) - координаты двух начальных битых пикселей.

Для любой точки \((x, y)\) на мониторе, расстояние до \(P_1\) по "чебышевской" метрике (максимум из разностей координат) равно \(max(|x-a|, |y-b|)\). Аналогично для \(P_2\).

Количество дней, за которое точка \((x, y)\) станет битой, равно \(min(max(|x-a|, |y-b|), max(|x-c|, |y-d|))\).

Нам нужно найти максимальное из этих значений для всех точек \((x, y)\) на мониторе. Это будет ответ.

Максимальное расстояние до границы для любого пикселя на мониторе будет определяться одной из четырех угловых точек монитора, или одной из точек, лежащих на границе, но наиболее удаленных от обоих начальных пикселей.

Рассмотрим 4 угловые точки монитора:

1. Верхний левый угол: \((1, 1)\)
2. Верхний правый угол: \((1, m)\)
3. Нижний левый угол: \((n, 1)\)
4. Нижний правый угол: \((n, m)\)

Для каждой из этих угловых точек, а также для самих начальных битых пикселей, мы можем рассчитать, сколько дней потребуется, чтобы "достичь" этой точки.

Для точки \((x, y)\) количество дней \(k\) равно \(max(min(|x-a|, |x-c|), min(|y-b|, |y-d|))\) - это не совсем корректно, так как распространение идет по "чебышевской" метрике.

Правильный подход: Для каждой точки \((x, y)\) на мониторе, количество дней, чтобы она стала битой, равно \(min(max(|x-a|, |y-b|), max(|x-c|, |y-d|))\).

Нам нужно найти максимальное значение этой функции по всему монитору. Это максимальное значение будет достигаться в одной из "крайних" точек монитора.

Рассмотрим 4 "угла" монитора:

1. \((1, 1)\)
2. \((1, m)\)
3. \((n, 1)\)
4. \((n, m)\)

Для каждой из этих точек вычислим количество дней, за которое она станет битой:

Для точки \((x, y)\):

\(k(x, y) = \min(\max(|x-a|, |y-b|), \max(|x-c|, |y-d|))\)

Нам нужно найти \(max(k(1,1), k(1,m), k(n,1), k(n,m))\).

Давайте проверим эту логику на примере.

Пример 1:

\(n=3, m=3, a=1, b=1, c=3, d=3\)

Первый пиксель: \((1, 1)\)

Второй пиксель: \((3, 3)\)

Угловые точки:

• \((1, 1)\): \(k(1,1) = \min(\max(|1-1|, |1-1|), \max(|1-3|, |1-3|)) = \min(\max(0,0), \max(2,2)) = \min(0, 2) = 0\)
• \((1, 3)\): \(k(1,3) = \min(\max(|1-1|, |3-1|), \max(|1-3|, |3-3|)) = \min(\max(0,2), \max(2,0)) = \min(2, 2) = 2\)
• \((3, 1)\): \(k(3,1) = \min(\max(|3-1|, |1-1|), \max(|3-3|, |1-3|)) = \min(\max(2,0), \max(0,2)) = \min(2, 2) = 2\)
• \((3, 3)\): \(k(3,3) = \min(\max(|3-1|, |3-1|), \max(|3-3|, |3-3|)) = \min(\max(2,2), \max(0,0)) = \min(2, 0) = 0\)

Максимальное из этих значений: \(max(0, 2, 2, 0) = 2\).

Давайте проверим вручную для \(n=3, m=3\):

День 0: битые пиксели \((1,1)\) и \((3,3)\)

День 1: От \((1,1)\) битыми становятся \((1,1), (1,2), (2,1), (2,2)\) От \((3,3)\) битыми становятся \((3,3), (2,3), (3,2), (2,2)\) Объединение: \((1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3)\)

Остался небитым только \((1,3)\) и \((3,1)\).

День 2: От \((1,1)\) область расширяется до \((1,1)-(3,3)\) От \((3,3)\) область расширяется до \((1,1)-(3,3)\) Весь монитор становится битым. Ответ: 2.

Моя формула \(k(x, y) = \min(\max(|x-a|, |y-b|), \max(|x-c|, |y-d|))\) дает 2 для \((1,3)\) и \((3,1)\). Для \((1,3)\): \(k(1,3) = \min(\max(|1-1|, |3-1|), \max(|1-3|, |3-3|)) = \min(\max(0,2), \max(2,0)) = \min(2,2) = 2\). Для \((3,1)\): \(k(3,1) = \min(\max(|3-1|, |1-1|), \max(|3-3|, |1-3|)) = \min(\max(2,0), \max(0,2)) = \min(2,2) = 2\). Максимальное из всех \(k(x,y)\) на мониторе будет 2.

Таким образом, алгоритм следующий:

1. Для каждой из четырех угловых точек монитора \((1,1), (1,m), (n,1), (n,m)\) вычислить количество дней, за которое она станет битой.
2. Количество дней для точки \((x, y)\) равно \(k(x, y) = \min(\max(|x-a|, |y-b|), \max(|x-c|, |y-d|))\).
3. Ответ — это максимальное из этих четырех значений.

Давайте применим этот алгоритм к каждому тесту.

Расчеты для каждого теста:

Тест 1: \(n=3, m=3, a=1, b=1, c=3, d=3\)

• \((1,1)\): \(\min(\max(|1-1|,|1-1|), \max(|1-3|,|1-3|)) = \min(0, 2) = 0\)
• \((1,3)\): \(\min(\max(|1-1|,|3-1|), \max(|1-3|,|3-3|)) = \min(2, 2) = 2\)
• \((3,1)\): \(\min(\max(|3-1|,|1-1|), \max(|3-3|,|1-3|)) = \min(2, 2) = 2\)
• \((3,3)\): \(\min(\max(|3-1|,|3-1|), \max(|3-3|,|3-3|)) = \min(2, 0) = 0\)

Ответ: \(\max(0, 2, 2, 0) = 2\)

Тест 2: \(n=5, m=5, a=1, b=1, c=3, d=3\)

• \((1,1)\): \(\min(\max(|1-1|,|1-