OberonCore

Можно решить эту задачу гораздо более быстрым способом. Модель такая. Есть замкнутая цепочка взаимодействующих частиц одинаковой массы. Взаимодействуют только соседние частицы цепочки (и первая с последней). Потенциал взаимодействия U-образный и имеет минимум на заданном расстоянии -- длине этого звена цепи. Ещё нужно добавить вязкость (чтобы всё в конце концов остановилось). Задаём случайное начальное условие и запускаем численную динамику. Когда частицы остановятся смотрим на длину звеньев. Если все частицы попали в минимумы потенциалов, значит решение найдено. Если не попали, то можно, на всякий случай, попробовать другие начальные данные, если не получится, то можно заявить, что решения не существует.

Можно? Гораздо? Вы точно пробовали?

Господа, подводных камней в задаче достаточно. Предлагаю подкрепить свои взгляды исходниками Задача творческая, как тут уже говорилось, и вполне может иметь нестандартное быстрое решение. Можно даже теорию вероятности применить Ж)
У меня тоже ощущение, что лошадка не панацея.
Будут работающие примеры, вот и сравним наглядно.
Там глядь и в задачник кто-нибудь включит
Вопрос к info21:
Как на ваш опытный взгляд по адекватности следующее?
Заполняем массив возможных приращений для обеих координат, для всех возможных длин на данном листе, как уже предлагал Владимир. Можно сразу сделать проверку всех входных данных по этому списку, можно и обойтись. Затем берем приращение (например по х) для первого звена, и сравниваем с суммой всех вариантов приращений оставшихся звеньев (исключение длина звена=5), ежели нуль то суммируем найденные приращения для второй координаты, ежели тоже нуль, то координаты найдены. Можно искать след вариант ломаной. Затем проверка входимости в лист (при длинах звеньев большей листа, можно заранее отсеить)

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

Попробовал для вещественной решётки. Для целочисленной надо думать.

Эффектно

>> Для целочисленной надо думать.

Чтобы отыскать целочисленный ответ, нужно добавить ещё притяжение частиц цепочки к целочисленным узлам "кристаллической решётки". Если само не "попадёт", то "потрясти".

Получается такая модель: замкнутая цепочка частиц летает в кристаллической решётке.

Ещё там в самом начале частицы находятся далеко от минимума потенциальной энергии поэтому прыгают как бешеные тарашки, а в конце, они уже находятся в окрестности минимумов и, наоборот, ползут как полудохлые улитки. Чтобы этого избежать, можно константу взаимодействия сначала сделать очень маленькой (звенья цепи -- хилые пружинки), а потом её плавно увеличивать (звенья цепи -- очень тугие прижинищи).

Блин!!! Едрена ВОШЬ! Думаю что-то не то в ходе рассуждений. Я задачу нечаянно усложнил. Звенья должны укладываться в ломаную только в том порядке в котором даны.
Ради бога простите склерозника
Хотя люди смотрю творчески не хило соображают. Может оно и к лучшему, что усложнил?!

>> Звенья должны укладываться в ломаную только в том порядке в котором даны.

Я так и понял.


Попробовал добавить "кристаллическую решётку". Как хочется -- не работает. Слишком много локальных минимумов. До глобального дотрясти никакого времени не хватит.

Мы сразу догадались.
Этот "людь" прочел очень много книжек, начиная с полноценного (т.е. физического, а не ИТ-шного) курса матанализа.

Просто замечание к дискуссии, убивает ли чтение книжек оригинальность мышления.

Согласен

Тогда простой перебор с возвратами. Ну, или распространение ограничений.
Без этого упрощения перебор гораздо серъезнее.

Ну с переборами все понятно. Я в начале говорил о том, что решили перебором. Сам уже предлагал версию. При переборе много поправок нарастает. Вопрос: имеет ли задача красивое решение? Сергей Губанов к этому очень близок imho. Тут уже речь идет о том, что ув. info21 называл "эффект магии". Возможно ли в этой задаче приодолеть комбинирование?

А вот это любопытно. Там ведь это не оговаривалось. Впрочем не оговаривалось и противоположное...

Наоборот, я убедился в том, что таким способом решение на решётке получить не реально.

Вы сдались окончательно?

Олимпиада ведь школьная. Поэтому есть подозрение, что задача была ещё проще.
Подразумевалось, что ломаная проведена по линиям листа.

Там была именно решетка, и входные данные были целочисленные с вещественными в перемешку. Хм... Ув. Сергей Губанов, а может вам делать то же самое в два этапа? Сначала для линий по горизонтали потом по вертикали...
Притяжение не к узлам а к линиям...

Без перебора не обойтись. Надо ведь выести все решения.
Но перебор не страшный: для небольшого квадрата - примерно 4^n.

А это как?

Ну к примеру "заноза" - длина звена равная 5 в моем примере. Можно конечно и без поправок.