кто-нибудь сталкивался с такой вот игрой?

evor

есть связный граф, в каждой вершине - целое число, за ход разрешается:
1) увеличить число в вершине на степень вершины, при этом числа в смежных вершинах уменьшаются на 1;
2) уменьшить число в вершине на степень вершины, при этом числа в смежных вершинах увеличиваются на 1.
Требуется стратегия, при которой можно будет в конце-концов получить в каждой вершине неотрицательное число или сказать, что такого сделать невозможно.
Интересует, скорее даже вопрос, откуда возникла эта задача?

Forsit

есть связный граф, в каждой вершине - целое число, за ход разрешается:
1) увеличить число в вершине на степень вершины, при этом числа в смежных вершинах уменьшаются на 1;
2) уменьшить число в вершине на степень вершины, при этом числа в смежных вершинах увеличиваются на 1.
Интересует, скорее даже вопрос, откуда возникла эта задача?
Из пункта А в пункт В выехал велосипедист. Его скорость 10 км\ч но половину пути ему пришлось двигаться со скоростью 5 км\ч ибо велосипед сломался.
Требуется узнать, живет ли бабушка велосипедиста в пункте С?
Дополнительный вопрос на пятерку: какой дебил учил тебя формулировать задачи\условия игр?

narkom

а какова цель? или просто так бесконечно увеличивать, уменьшать? :)
Что мы минимизруем? Кто игроки, если они есть?

Lokomotiv59

Ключевая идея: коммутативность операций.
Для графа можно составить систему линейных неравенств с целыми переменными, где переменные — это количество применений операции к той или иной вершине (она может быть как положительной, так и отрицательной). Неравенства получаются из условия, что число в каждой вершине >= 0. Решаешь полученную систему любым способом, который гарантированно приводит к ответу за конечное число шагов, например, методом branch-and-cut. Решение — это и будет твоя стратегия.

evor

спасибо, конечно, но вопрос стоял в том, откуда произошла эта задача, так сказать, какова её хозяйственная составляющая?

Lokomotiv59

без понятия
Оставить комментарий
Имя или ник:
Комментарий: