Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
СОЦИОН. » Юный техник » олимпиадная задачка
Чтобы отправить ответ, вы должны войти или зарегистрироваться
паркетность из коммутируемости никак не следует
Может и так. Но решение в любом случае должно покрывать всю фигуру, имхо, это можно сделать лишь паркетом либо наложением нескольких паркетов (или чем-то, эквивалентным наложению паркетов). Может я и не прав, я в этой теме ни одного утверждения не доказывал. 
для тренировок
http://www.var.ru/bz/js/floor.html
а паркет вестимо будет, ведь замощение идёт одинаковыми фигурами
вопрос о разрешимости задачи для данных m и n эквивалентен вопросу о разрешимости над полем z2 линейного уравнения m*n-переменных вида
AE0....0 = 1
EAE0...0 = 1
0EAE0..0 = 1
0...0EAE = 1
0....0EA = 1где E - еденичные блоки размера mxm или nxn в зависимости от введёной нумерации, количество блоков соотв. наоборот n или m
A - трёхдиагональная матрица с еденицами на 3ёх центральных диагоналях
ответ:
Обосновать того, что ответ всегда есть?
ну попробуй
я пока над этим не думал
Ну ты следовательно просто усложнил задачу на порядок... Я бы не назвал это решением.
temp3 пишет:ну попробуй
я пока над этим не думалНу ты следовательно просто усложнил задачу на порядок... Я бы не назвал это решением.
я привёл её к более формальному виду, который допускает использование традиционных методов
усложнил или нет - это недоказуемо
в таком виде как задачка на олимпиаду по информатике вполне решаема
а по математике - не знаю
srez пишет:temp3 пишет:ну попробуй
я пока над этим не думалНу ты следовательно просто усложнил задачу на порядок... Я бы не назвал это решением.
я привёл её к более формальному виду, который допускает использование традиционных методов
усложнил или нет - это недоказуемов таком виде как задачка на олимпиаду по информатике вполне решаема
а по математике - не знаю
Ну че доказуемо или нет, в первом виде решение более менее понятно, остались мелочи, перебором решаемые несложно. А в этом виде я хз, что дальше делать... то есть глобальный затык. Ахрененная матрица с жуткими формулами.
Ну это как свести простенькую геометрическую задачу, расписать ее в координатах в формулы. Получить ахренненые нелинейные композиции синусов, тангесов корней бешенных. И сказать, что решение вона, получите. *)
Да и все же я не понял, собственно ответ на задачу должен отвечать на вопрос задачи. Напомню вопрос.
"если полез иначально чёрное, существует ли общий алгоритм по которому можно всё поле инверсировать?
какие ограничения на M и N?"
Как твое решение отвечает на эти вопросы я ниасилил.
Да и все же я не понял, собственно ответ на задачу должен отвечать на вопрос задачи. Напомню вопрос.
"если полез иначально чёрное, существует ли общий алгоритм по которому можно всё поле инверсировать?
какие ограничения на M и N?"
Как твое решение отвечает на эти вопросы я ниасилил.
пишем простейшую программку на сях, вводим для данные m и n
получаем координаты кнопок которые надо нажать
если матрица не разрешима над полем z2 - значит данное поле инверсировать нельзя
temp3 пишет:srez пишет:Ну ты следовательно просто усложнил задачу на порядок... Я бы не назвал это решением.
я привёл её к более формальному виду, который допускает использование традиционных методов
усложнил или нет - это недоказуемов таком виде как задачка на олимпиаду по информатике вполне решаема
а по математике - не знаюНу че доказуемо или нет, в первом виде решение более менее понятно, остались мелочи, перебором решаемые несложно. А в этом виде я хз, что дальше делать... то есть глобальный затык. Ахрененная матрица с жуткими формулами.
Ну это как свести простенькую геометрическую задачу, расписать ее в координатах в формулы. Получить ахренненые нелинейные композиции синусов, тангесов корней бешенных. И сказать, что решение вона, получите. *)
ну программку-то ты сможешь написать?
srez пишет:temp3 пишет:я привёл её к более формальному виду, который допускает использование традиционных методов
усложнил или нет - это недоказуемов таком виде как задачка на олимпиаду по информатике вполне решаема
а по математике - не знаюНу че доказуемо или нет, в первом виде решение более менее понятно, остались мелочи, перебором решаемые несложно. А в этом виде я хз, что дальше делать... то есть глобальный затык. Ахрененная матрица с жуткими формулами.
Ну это как свести простенькую геометрическую задачу, расписать ее в координатах в формулы. Получить ахренненые нелинейные композиции синусов, тангесов корней бешенных. И сказать, что решение вона, получите. *)ну программку-то ты сможешь написать?
для инверсирования матрицы m*n, ой не факт. там не n^4 ли быстродействие если влоб?
temp3 пишет:srez пишет:Ну че доказуемо или нет, в первом виде решение более менее понятно, остались мелочи, перебором решаемые несложно. А в этом виде я хз, что дальше делать... то есть глобальный затык. Ахрененная матрица с жуткими формулами.
Ну это как свести простенькую геометрическую задачу, расписать ее в координатах в формулы. Получить ахренненые нелинейные композиции синусов, тангесов корней бешенных. И сказать, что решение вона, получите. *)ну программку-то ты сможешь написать?
для инверсирования матрицы m*n, ой не факт. там не n^4 ли быстродействие если влоб?
(m*n)^3
я уже сказал выше - никто не просит тебя решать методом гаусса, особенно когда матрица такая вот красивая
есть итерационные методы, которые с учётом известности и очень большой красивости поля решений будут сходиться вообще мгновенно
srez пишет:temp3 пишет:ну программку-то ты сможешь написать?
для инверсирования матрицы m*n, ой не факт. там не n^4 ли быстродействие если влоб?
(m*n)^3
я уже сказал выше - никто не просит тебя решать методом гаусса, особенно когда матрица такая вот красивая
есть итерационные методы, которые с учётом известности и очень большой красивости поля решений будут сходиться вообще мгновенно
о, ну значиццо n^6 решение предлагаешь фактически. а теперь давай своими итерационными методами реши задачку для m=n=1E20. *)
temp3 пишет:srez пишет:для инверсирования матрицы m*n, ой не факт. там не n^4 ли быстродействие если влоб?
(m*n)^3
я уже сказал выше - никто не просит тебя решать методом гаусса, особенно когда матрица такая вот красивая
есть итерационные методы, которые с учётом известности и очень большой красивости поля решений будут сходиться вообще мгновенноо, ну значиццо n^6 решение предлагаешь фактически. а теперь давай своими итерационными методами реши задачку для m=n=1E20. *)
для итерационных методов m=n=1E20 данная система уравнений будет решена за что-то типа O(1E80), а то и значительно быстрее, ведь поле решений очень и очень хорошее
думаю даже одного шага итерации будет достаточно в данном случае
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 система будет либо иметь либо не иметь решенияДо этого думаю тут много кто догадался, только вот очень уж робское решение получается, неконструктивное, трудоемкость факториальная, а хочется хотя бы полиномиальную.
Откуда факториальное решение, я не совсем понимаю? Решить систему уравнений - это факториальная трудоемкость? ))
Чтобы отправить ответ, вы должны войти или зарегистрироваться
СОЦИОН. » Юный техник » олимпиадная задачка
На основе PunBB, при поддержке Informer Technologies, Inc.
Currently used extensions: favorite_topic, pun_repository. Copyright © 2008 PunBB
Сгенерировано за 0.033 секунд(ы), выполнено 78 запросов