0xDEADBEEF

Этож точ в точ Записки невесты программиста. Только слова поменяли. Экслер негодует.

Ой, я только сейчас об этом прочел... Теперь чувствую, что совершил что-то плохое...

И конечно-же POHMELFS *05

X-tender Спасибо. Предложение такое - устраивать раз в 2-3 дня контест часа на 3 по вечеру с небольшим числом задач. Использовать ACM Server, обсуждать можно здесь хотя бы http://ulanovka.ru/forum/viewtopic.php?t=73948 Рейтинг свой завести, пока на бумажке) Добавлено спустя 8 минут 29 секунд: X-tender Хорошо, только ирку освою)

X-tender Можно ссылочку на профиль? Про конкурс и обсуждения - можно устраивать хоть каждый день небольшие локальные контесты, были бы желающие.

X-tender А чем codeforces.ru не устраивает? В плане судей можем посодействовать.

ToNY667 Ошибаешься *05 Сидел на Дебиане 4м около 1.5 года. Ставил изначально по минимуму - одну консоль, предварительно снеся полностью винду и любые пути отступления. За пару недель влился Хотя мой способ изучения мало еще кому подойдет. По поводу игр - играл в WoW под Wine. Игралось вполне сносно. Это было 3 года назад, сейчас думается играется все.

Про печеньки не забываем

А вы разводить их собираетесь? Вообще то на их искусственное разведение мораторий. У хорошего программиста скил маскировки вкачан на 100500, так что встретить его можно его где угодно, но распознать - сложно весьма.

Всегда на Эрдеме собирались. А сидели на танке) Давайте всеже на Эрдем

Админ этих камер тоже будет

Клуб любителей ноликов и единичек приглашает на чай с печеньками

Простите великодушно, может я не в теме... Но при чем тут программирование?

Напиши в ЛС. А то телефон убежал(

Собственно тут http://www.verbatim.jp/senshuken/ Надеюсь создатели выдадут флэшек победителю, равную силе монстра.

Как вариант - Code::Blocks. Если решить писать гуй на wxWidgest, то он очень поможет.

В нашем городе можно знать ворд с экселем и считаться хорошим программистом)

Eclipse однозначно. Для Qt лучше QtCreator.

Данное число - количество П (В) вершин. Очевидно всетаки 3 массива). Множетсво смежных вершин с данно разбивается на 2 (V и P), поэтому V+P = D; Отметку можно ставить, когда она точно изветна. Т.е. для вершины кота, если есть путь в хоть в одну П, то для нее ставим П и считаем рассмотренной. Вот правила для расстановки меток, из них все следует. Если расставить все метки в примере - то получается что для кота выйгрышные 1,3,4. Которые образуют цикл. Значит чтобы выйграть он должен ходить по этому циклу. Бесконечно.

Постараюсь ответить на все. 1. Ход делает владелец позиции: Нулевая сумма проще говоря, это если 1 выигрывает, то другой обязательно проигрывает. Если за выигрыш дают 1 (балл) за проигрыш -1, а за ничью 0. Если у нас 2 игрока и один из них выиграл (получил 1), то другой обязательно получит -1 (проиграет) чтобы в сумме получилось 0. Тестовый пример имелся ввиду тот, который дан в задаче. Контрпример - это то что я нарисовал, пояснения тоже к нему относятся, а не к примеру из задачи. Процедура можно сказать рекурсивная, стартует от заранее известных позиций (в нашем случае Z). Как узнать? - здесь ничего сложного: стартуя из Z и идя по инвертированным ребрам для каждой вершины считаем количество П (В) вершин, в которые мы можем из нее попасть. После этого сравниваем степень вершины с данным числом - это даст ответ на вопрос все ли пути ведут в П (В) вершины, и далее в зависимости от владельца выдаем ответ. То что вы здесь процитировали и есть алгоритм расстановки. если вспомнить, что пометки расставляются относительно лисы - то ясно что лиса всегда хочет выиграть, а значит идет по своим выигрышам. Кот наоборот идет по ее проигрышам, те.е своим выигрышам. ДФС = Depth First Search - поиск в глубину. БФС = Breadth First Serch - поиск в ширину. Давайте попробуем расставить метки для примера из задачи. Делать это будем поиском в ширину. У нас 2 массива D - степени вершин по исходу, P - количество П вершин, в которые мы можем попасть, V - количество V вершин. Нужно отметить важный факт D = V+P. Вершину можно считать рассмотренной, когда для нее можно поставить пометку. Z - заранее известная В позиция. 1. В нее можем прийти из 2х вершин 3 и 6. Значит V[3] = 1, V[6] = 1; вершина 6 полностью рассмотрена: имеем D[6] = 1, V[6] = 1. Т.к. она принадлежит лисе и есть ход в В, то она В. 2. В 6 попадаем из 5, 4, 3 значит V[5] = 1, V[4] = 1, V[3] = 2; Для 3х V[1] = 1, V[4] = 2. вершина 5 полностью рассмотрена: имеем D[5] = 1, V[5] = 1, Т.к. она принадлежит коту и из нее нет хода в П, значит она В. 3 не является рассмотренной, т.к. не все исходы из нее известны. 3. Далее в 5 попадаем из 2 V[2] = 1 может считаться рассмотренной и получает метку В (принадлежит лисе, имеет ход в В). В 4 из 2 и 1, но для них ничего не происходить, т.к. 2 уже рассмотрена, а 1 еще нет. У нас остались 3 не рассмотренные вершины - для них мы можем однозначно поставить метку П. К стати этот пример дает ответ на вопрос о результате игры, когда коту выгодно бесконечно ходить по кругу.

Фишка одна, двигать ее может только владелец позиции. Позиция не может быть выигрышной для обоих сторон. Наша игра - с нулевой суммой, т.е. если кто-то выигрывает, то другой обязательно проиграет. Так получилось, что для вашего решения тестовый пример сработал). А вот на таком графе, который иллюстрирует почти все противоречия, нет: Лиса-->Лиса-->Кот --> Кот --> Кот --> Z 1 2 3 4 5 1. От позиции 3 лисья позиция ни разу не встретилась, однако выигрывает однозначно лиса. 2. От позиции 1 длины путей длина пути для кота меньше, чем для лисы. однако однозначно выигрывает она. Итак. Будем каждой вершине проставлять метки П и В (проигрышная и выигрышная), для игры с поочередным ходом: 1. Если из вершины с мы можем попасть только в в вершины с меткой В, то эта вершина П. 2. В другом случае она В. Оптимальная стратегия предельно проста - мы должны перевести следующего игрока в П вершину, т.е. ту из которой он не сможет сделать выигрышный ход. Теперь принимая во внимания условия задачи, модифицируем. Для определенности П,В метки расставляются относительно лисы: Стратегия кота - ходить только в П вершины. Для лисы наоборот. Для вершины кота: 1. Если из вершины мы можем попасть только в В вершины (неважно чьи), то эта позиция В (относительно лисы) 2. Иначе это П. Для вершины лисы: 1. Если из вершины мы можем попасть только в П вершины (неважно чьи), то эта позиция П. 2. Иначе это В. Помечать можно дфсом или бфсм (на свой вкус) из вершины Z. Не пройденные (не помеченные) вершины являются П.

1. Потомучто на каждую выкладку можно придумать нехитрый контр пример. 2. Ничейных позиций быть не может. При равенстве вы неявно вводите возможность существования ничейной позиции, а точнее говоря при равенстве двух путей выходит, что позиция выйгрышна для обох игроков (ведь матрицы равноценны?) 3. Выйгрышный путь может состоять только из вершин кота, может заходить на вершины кота, может делать, вообще говоря, любые ходы. Заранее сказать нельзя.

Ваши рассуждения в корне не верны.

R@UBTIER Тема - игры на графах. Нужны самые начала - N-P позиции (т.е. выигрышные/проигрышные). http://e-maxx.ru/algo/games_on_graphs Тут небольшое описание и пример. В ваше задаче разница в том, что ходят не по очереди, а по принадлежности.

R@UBTIER В той постановке, в которой вы хотите ее решать сложность будет порядка N^(N-2), где N - количество вершин. Оценка вытекает из алгоритма поиска всех путей - а именно простой dfs, проходящий все эти пути. Решить ее можно одним bfs'ом, используя базовые понятия игр на графах.