2xN почему решается?
temp3 пишет:
2xN почему решается?
квадратиками 2*2 нажимай разом переключается 2*4 прямоугольник. если квадртик прилегает к краю то 3*4. ну и остатки доделать тривиально.
Не, я имел в виду при больших N. Маленькие -- это вырожденный случай.
Но не в этом дело. Я нашел ошибку в своем алгоритме. 
Короче, идея была такой. Рассматривается паркет из крестообразных фигур. Он без пробелов покрывает всю плоскость, а значит плоскость можно инвертировать, нажимая на центральные квадратики каждого креста. Если вырезать какой-то прямоугольник, то пявятся пробелы на краях. Мне показалось, что наложением нечетного числа смещенных паркетов можно решить эту проблему, однако, оказалось, что там есть какие-то ограничения на квадраты.
Попробую найти какой-то другой способ или определить в чем ограничение (тут,имхо, нужно инварианты поискать). Блин, был бы хоть листик в клеточку!
masai пишет:
Не, я имел в виду при больших N. Маленькие -- это вырожденный случай.
Но не в этом дело. Я нашел ошибку в своем алгоритме.
Короче, идея была такой. Рассматривается паркет из крестообразных фигур. Он без пробелов покрывает всю плоскость, а значит плоскость можно инвертировать, нажимая на центральные квадратики каждого креста. Если вырезать какой-то прямоугольник, то пявятся пробелы на краях. Мне показалось, что наложением нечетного числа смещенных паркетов можно решить эту проблему, однако, оказалось, что там есть какие-то ограничения на квадраты.
Попробую найти какой-то другой способ или определить в чем ограничение (тут,имхо, нужно инварианты поискать). Блин, был бы хоть листик в клеточку!
красивая идея. видимо както так она и решается.
как я понял задачу, можно любое поле свести к углу (~3x3x) а там и смотреть получается или нет.
предложили метод поиска нужных нажатий
очень красивый и простой, правда корректность неочевидна, доказывать надо
оттуда же следуют условия на m и n
короче решение
1) любые два нажатия на кнопку коммутируют
ясно что коммутируют любые нажатия на соседние кнопки *проверяется вручную*
а значит коммутируют вообще любые два нажатия
а отсюда значит что в процессе ни одна кнопка не будет нажата дважды
2) строится система m*n линейных уравнений над полем вычетов по модулю два
на каждую кнопку одна переменная, равная либо 0 - кнопка не нажимается, либо 1 - кнопка нажимается
каждое уравнение имеет вид - x_ij+x_(i-1)j+x_i(j-1)+x_(i+1)j+x_i(j+1)=1 где 0<i<N+1 0<j<M+1 - координаты кнопки, если кнопка краевая этих членов в уравнении просто нет
дальше система решается и получаем набор кнопок которые необходимо нажать
в зависимости от M и N система будет либо иметь либо не иметь решения
temp3 пишет:
короче решение
1) любые два нажатия на кнопку коммутируют
ясно что коммутируют любые нажатия на соседние кнопки *проверяется вручную*
а значит коммутируют вообще любые два нажатия
а отсюда значит что в процессе ни одна кнопка не будет нажата дважды
2) строится система m*n линейных уравнений над полем вычетов по модулю два
на каждую кнопку одна переменная, равная либо 0 - кнопка не нажимается, либо 1 - кнопка нажимается
каждое уравнение имеет вид - x_ij+x_(i-1)j+x_i(j-1)+x_(i+1)j+x_i(j+1)=1 где 0<i<N+1 0<j<M+1 - координаты кнопки, если кнопка краевая этих членов в уравнении просто нетдальше система решается и получаем набор кнопок которые необходимо нажать
в зависимости от M и N система будет либо иметь либо не иметь решения
До этого думаю тут много кто догадался, только вот очень уж робское решение получается, неконструктивное, трудоемкость факториальная, а хочется хотя бы полиномиальную.
ну да, надо знать хотя бы что такое поле вычетов по модулю два
решение не робское, но ЧИ да
пункт 1 достаточно тривиальный
пункт 2 - нужны дополнитльные знания
temp3 пишет:
ну да, надо знать хотя бы что такое поле вычетов по модулю два
решение не робское, но ЧИ дапункт 1 достаточно тривиальный
пункт 2 - нужны дополнитльные знания
Робское в том смысле, что в теории решение правильное, а практически реализовывать его при достаточно больших размерах поля вычислительной мощности не хватит.
матрица получится очень хорошей, сходимость при итерационных методах будет практически мгновенной, особенно с учётом, что поле решений заранее известно и тоже очень хорошее
сейчас вычислительных мощностей хватает на куда более сложные задачи
32 16.11.2006 21:47:35 Отредактировано temp1 (16.11.2006 21:48:16)
не говоря уже о том, что сама задачка на практике встретится с очень небольшой вероятностью
хотя кто знает, сейчас и куда более буднично-выглядящие задачи решаются изподвыподвертами
masai пишет:
Не, я имел в виду при больших N. Маленькие -- это вырожденный случай.
Но не в этом дело. Я нашел ошибку в своем алгоритме.
Короче, идея была такой. Рассматривается паркет из крестообразных фигур. Он без пробелов покрывает всю плоскость, а значит плоскость можно инвертировать, нажимая на центральные квадратики каждого креста. Если вырезать какой-то прямоугольник, то пявятся пробелы на краях. Мне показалось, что наложением нечетного числа смещенных паркетов можно решить эту проблему, однако, оказалось, что там есть какие-то ограничения на квадраты.
Попробую найти какой-то другой способ или определить в чем ограничение (тут,имхо, нужно инварианты поискать). Блин, был бы хоть листик в клеточку!
так же в начале подумал. Но неточности на краях сразу заметил
temp3 пишет:
ну да, надо знать хотя бы что такое поле вычетов по модулю два
решение не робское, но ЧИ дапункт 1 достаточно тривиальный
пункт 2 - нужны дополнитльные знания
это какие? что такое линейное уравнение или "по модулю 2"?
temp3 пишет:
матрица получится очень хорошей, сходимость при итерационных методах будет практически мгновенной, особенно с учётом, что поле решений заранее известно и тоже очень хорошее
сейчас вычислительных мощностей хватает на куда более сложные задачи
например?
Arctic пишет:
temp3 пишет:матрица получится очень хорошей, сходимость при итерационных методах будет практически мгновенной, особенно с учётом, что поле решений заранее известно и тоже очень хорошее
сейчас вычислительных мощностей хватает на куда более сложные задачи
например?
матрица будет 5тидиагональной
3 центральные диагонали и по одной отстоящей от центра на n или m "позиций" в зависимости от того, как пронумеруешь
37 20.11.2006 13:19:36 Отредактировано srez (20.11.2006 13:19:48)
если на все кнопки нажать по разу по очереди, то все угловые и центраьлные кнопки поменяют цвет. останутся только боковые. но дальше эту идею добить не смог.
Arctic пишет:
masai пишет:Не, я имел в виду при больших N. Маленькие -- это вырожденный случай.
Но не в этом дело. Я нашел ошибку в своем алгоритме.
Короче, идея была такой. Рассматривается паркет из крестообразных фигур. Он без пробелов покрывает всю плоскость, а значит плоскость можно инвертировать, нажимая на центральные квадратики каждого креста. Если вырезать какой-то прямоугольник, то пявятся пробелы на краях. Мне показалось, что наложением нечетного числа смещенных паркетов можно решить эту проблему, однако, оказалось, что там есть какие-то ограничения на квадраты.
Попробую найти какой-то другой способ или определить в чем ограничение (тут,имхо, нужно инварианты поискать). Блин, был бы хоть листик в клеточку!
так же в начале подумал. Но неточности на краях сразу заметил
Ну, я и не говорил никогда, что я умный. 
Фишка тут вот в чем.
Так как все нажатия коммутируют, и нажатие на кнопку в любом случае "портит" инверсию, то, имхо, можно доказать, что любое решение будет состоять из комбинации смещенных паркетов. Однако, если не нажимать одну и ту же кнопку дважды (из-за того, что нажатия коммутируют это бессмысленно), то таких наложений может быть от одного до пяти.
С одним наложением все ясно -- оно покрывает плоскость и рассмотреные срезом случаи с небольшими размерами сторон. Вполне может быть, что это единстенные допустимые решения. По крайней мере, я не придумал пока, как пятью смещенными покрытиями инвертировать "плохие" квадратики на краях.