#algorithm
#алгоритм
Вопрос:
Это вопрос, с которым я столкнулся в одном из онлайн-конкурсов по программированию:
Это игра для 2 игроков. Есть две породы воинов для начала «A» и «B«. Дано n городов, и в каждом городе i есть w [i] количество воинов (которые могут быть любой породы A или B). Каждый воин j в городе имеет силу S [j].
Первый игрок должен выбрать породу воина . Второй игрок получает другую породу .В свою очередь, игрок должен выбрать город и воина в этом городе выбранной им породы.
Один игрок выберет породу воинов и город, чтобы начать игру . Этот воин убьет любого другого воина города с меньшей силой, чем у него, независимо от породы. В конце он умрет. Затем второй игрок выберет другой город и породу и сделает то же самое. Это продолжается до тех пор, пока не останется ходов.
Первый игрок должен решить, какую породу воинов выбрать, чтобы он победил, или если у него нет возможности выиграть, если его противник играет оптимально.
Какова оптимальная стратегия алгоритма для первого игрока, который выиграет.
Пример —
пусть есть один город (C1) с 2 воинами — W1 силой 10 и породой A, W2 силой 15 и породой B.
Первый игрок выберет породу B, чей воин убьет другого воина, и, следовательно, у второго игрока не будет ни одного воина на выбор.
Комментарии:
1. Вы говорите, что игроки выбирают породу и город, но затем говорите об «этом воине», убивающем других воинов, как если бы игроки выбрали конкретных воинов. Не могли бы вы более точно указать проблему?
2. Извините, я виноват. Первый игрок должен выбрать породу воина . Второй игрок получает другую породу . В свою очередь, игрок должен выбрать город и воина в этом городе выбранной им породы..
3. Что произойдет, если игрок1 выберет более слабого воина в примере? Выбранный вами воин наверняка умрет в конце хода, а более сильные выживут? Есть ли несколько воинов одной породы и как они действуют (сражаются ли они со своей породой)? Если они делают, какова цель «размножения»?
4. Проблема не ясна. Необходимо уточнить дополнительные правила.
5. Был ли задан вопрос с ограничениями размера проблемы? Если это проблема программирования (а не математическая задача), то решение будет включать либо поиск, либо динамическое программирование.
Ответ №1:
Из вашего описания оптимальное решение простое. Для каждого воина в городе выберите воина с наивысшей силой. Посчитайте лучших воинов для каждого города, и победит та порода, в которой есть лучшие воины.