Bubble Cup 8 - Finals [Online Mirror] |
---|
Закончено |
Саша и Ира — лучшие друзья. Они не просто друзья — они разработчики ПО и эксперты по искусственному интеллекту. Они разрабатывают алгоритм для двух ботов, играющих в игру для двух игроков. За каждый ход, один из игроков совершает ход (неважно, какой игрок, возможно, игроки делают ходы не по очереди).
Алгоритм для ботов, разработанный Сашей и Ирой, работает за счет отслеживания состояния, в котором находится игра. Каждый раз, когда любой бот делает ход, состояние меняется. А так как игра очень динамичная, она никогда не вернется в то состояние, в котором она была на каком-либо этапе в прошлом.
Саша и Ира — перфекционисты и они хотят, чтобы у их алгоритма была оптимальная выигрышная стратегия. Они заметили, что в оптимальной выигрышной стратегии оба бота делают ровно по N ходов каждый. Но для того, чтобы найти оптимальную стратегию, их алгоритму надо проанализировать все возможные состояния этой игры (они ещё не изучили альфа-бета отсечение) и выбрать лучшую последовательность ходов.
Они беспокоятся насчет эффективности их алгоритма и им интересно, какое общее количество состояний в игре, которое необходимо проанализировать?
В первой и единственной строке записано целое число N.
Вывод должен содержать единственное целое число – количество возможных состояний по модулю 109 + 7.
2
19
Начало: Игра в состоянии A.
Всего образуется 19 различных состояний игры, необходимых в анализе алгоритма.
Название |
---|