С помощью N закрашеных квадратов при данных условиях можно закрасить максимум N^2 => S(квадрата)^-2 округлённое в большую сторону м есть искомый ответ, но вот формализовать предпосылку о N^2
Здравствуйте, Pushkin, Вы писали:
P>Завтра скажу, время сбора 9-00 по москве P>Вот прикол будет, если оно неправильное
Пока вы все ещё дрыхнете, воспользуюсь своим географическим положением.
1) Закрашиваемые клетки не могут выйти за рамки минимального прямоугольника,
охватывающего все стартовые клетки.
(Это очевидно из алгоритма закраски)
2) Пусть у нас уже закрашен прямоугольник размера X * Y.
ххххх
ххххх
ххххх
Тогда, с помощью ещё одной стартовой клетки, мы можем увеличить площадь закраски двумя способами:
2.1) Разместив стартовую клетку напротив одной из сторон
ххххх
ххххх С
ххххх
или
ххххх
ххххх
ххххх
С
Располагать вплотную к прямоугольнику — не выгодно, а помещать дальше — бесполезно.
При этом мы получим закрашенный прямоугольник размера (X + 2) * Y или X * (Y + 2)
2.2) Разместив стартовую клетку возле одного из углов
ххххх
ххххх
ххххх
С
Закрашенный прямоугольник будет размером (X + 1) * (Y + 1)
3) Повторяя 2.1 или 2.2, мы сможем с помощью двух стартовых клеток увеличить площадь до
(X + 2) * (Y + 2).
ХХХХХxx
ХХХХХxС
ХХХХХxx
xxxxxxx
xxСxxxx
или
ХХХХХxx
ХХХХХxx
ХХХХХxx
xxxxxСx
xxxxxxС
4) Максимальная площадь, которая может быть закрашена с помощью одной стартовой — это
квадрат 1 * 1.
4.1) Для закраски квадрата N * N, где N — нечётное, нам понадобятся
(N - 1)/2 клеток на каждую сторону, плюс ещё одна начальная
(N - 1)/2 + (N - 1)/2 + 1 = N
4.2) Для закраски квадрата N * N, где N — чётное, мы должны начинать с квадрата 2 * 2, для
закраски которого нужны две стартовые клетки.
Итого
(N - 2)/2 клеток на каждую сторону, плюс ещё две начальных
(N - 2)/2 + (N - 2)/2 + 2 = N
Здравствуйте, mrhru, Вы писали:
M>Пока вы все ещё дрыхнете, воспользуюсь своим географическим положением.
Непорядочный человек
M>3) Повторяя 2.1 или 2.2, мы сможем с помощью двух стартовых клеток увеличить площадь до M>(X + 2) * (Y + 2).
А если через раз 2.1 и 2.2? Получим (X+3)*(Y+1).
И что из этого следует? А фиг его знает — твоё же решение,
ты и должен был рассматривать все случаи.
Короче вот, как я могу пересказать твоё решение, чтобы оно меня устроило (но чур через чёрточку потом ники писать в ссылках )
1) Если закрашен некий прямоугольник, без дополнительной стартовой точки его очевидно нельзя расширить.
2) Стартовая точка может помочь только в 3-х случаях: а) она пристыкована к стороне б) она отстоит от стороны через одну в)она пристыкована к углу.
3) Во всех случаях эта стартовая точка добавит к прямоугольнику либо ряд, либо столбец, либо два ряда, либо два столбца, либо ряд и столбец. Т.е. сумма рядов и столбцов закрашенного прямоугольника вырастет не более чем на 2.
4) Изначально сумма равнялась нулю. Чтобы получить итоговую сумму A+B надо не менее (A+B)/2 стартовых клеток, (округлять, если потребуется, в большую сторону.)
5) Для полноты нужна ещё достаточность. Но она тривиальна — стартовые клетки через одну по периметру (предложено например здесь
Здравствуйте, Pushkin, Вы писали:
P>Ну а теперь на сцену выходит другое решение...
Это может показаться трюком, но на самом деле абсолютно стандартное решение. Во всех задачах такого рода надо прежде всего попытаться увидеть, какая величина не меняется при разовом действии.
В данном случае, так как мы пристыковываем новую клетку не менее чем к двум границам, ясно, что периметр закрашенной области при этом не растёт. Таким образом мы не можем закрасить область периметра P с помощью менее чем P/4 клеток.
В частности для прямоугольника со сторонами A и B потребуется не менее (A+B)/2 стартовых клеток. То, что их достаточно (с округлением вверх) проверяется в лоб.
У меня есть ощущение, что и для любой области ceil(P/4) будет достаточно. Но я не уверен. По крайней мере не могу доказать.
Здравствуйте, Pushkin, Вы писали:
P>У меня есть ощущение, что и для любой области ceil(P/4) будет достаточно. Но я не уверен. По крайней мере не могу доказать.
Здравствуйте, MichaelP, Вы писали:
MP>Здравствуйте, Pushkin, Вы писали:
P>>У меня есть ощущение, что и для любой области ceil(P/4) будет достаточно. Но я не уверен. По крайней мере не могу доказать.
MP> MP>Опровержение: MP>
MP> X
MP>XXX
MP> XXX
MP> X
MP>
Да, одной не хватает
Ну найди сам границу достаточности, если такой умный
A>А по индукции? Для 1*1 очевидно. Если расмотреть N*N, который уже "расскрашен" и добавить один столбец и одну строку, т.е. перейти к (N+1)*(N+1), то очевижно, что хотябы одна клетка в строке и одна в столбце должны быть закрашены. Оптимально сделать это на пересечении строки и столбца. Вот и ограничили снизу
Не совсем так. Общее правило такое: Для того, чтобы закрасить прямоугольник N*M нужно не менее (N+M)/2 зерен(округление вверх). Этого же кол-ва достаточно. Засеиваем из угла по диагонали, потом вдоль края через одну.
X00000000
0X0000000
00X0X0X0X
Для того, чтобы ряд нужно закрасить (будем говорить "контролировать") нужно, чтобы в нем была закрашена (не обязательно первоначально) клетка или закрашены (тоже н обязательно сразу) две клетки в соседних рядах друг напротив друга. Вот так
00000X00000
00000000000
00000X00000
Далее доказательство в общем понятно. Но я пока не знаю, как изложить его иначе как долго и нудно с рассмотрение случаев.
