Magic: the Gathering - это игра с карточными играми, в которой, среди прочего, игроки играют в карты, представляющие существ, которые могут затем атаковать другого игрока или защищаться от атак другого игрока путем блокирования.
В этом соревновании по коду для игры в гольф ваша программа будет заменена игроком-волшебником, который решает, как блокировать в бою.
У каждого существа есть два соответствующих атрибута: сила и выносливость. Сила существа - это количество урона, которое оно может нанести в бою, а его прочность - количество урона, необходимого для его уничтожения. Сила всегда по крайней мере 0, а прочность всегда по крайней мере 1.
Во время боя в Магии игрок, ход которого объявил, что некоторые из его существ атакуют противника. Затем другой игрок, известный как защищающийся игрок, может назначить своих существ в качестве блокирующих. Существо может блокировать только одно существо в бою, но несколько существ могут блокировать одно и то же существо.
После объявления блокирующих атакующий игрок решает, для каждого атакующего существа, которое было заблокировано, как распределить урон (равный его силе), который это существо наносит существам, блокирующим его.
Затем наносится урон. Каждое существо наносит урон, равный его силе. Атакующие существа, которые были заблокированы, наносят урон, как описано выше. Разблокированные атакующие существа наносят урон обороняющемуся игроку. Блокирующие существа наносят урон существу, которое они заблокировали. Существа, принадлежащие защищающемуся игроку, которые не блокируют, не наносят никакого урона. (Существа не обязаны блокировать.)
Наконец, любое существо, нанесшее урон, равный или превышающий его выносливость, уничтожается и удаляется с поля битвы. Любое количество урона меньше силы существа не имеет никакого эффекта.
Вот пример этого процесса:
Существо с силой P и выносливостью T представляется как P/T
Attacking:
2/2, 3/3
Defending player's creatures:
1/4, 1/1, 0/1
Defending player declares blockers:
1/4 and 1/1 block 2/2, 0/1 does not block.
Attacking player distributes damage:
2/2 deals 1 damage to 1/4 and 1 damage to 1/1
Damage is dealt:
2/2 takes 2 damage, destroyed.
3/3 takes 0 damage.
1/1 takes 1 damage, destroyed.
1/4 takes 1 damage.
0/1 takes 0 damage.
Defending player is dealt 3 damage.
У защищающегося игрока есть 3 цели в бою: уничтожить существа противника, сохранить собственные и получить как можно меньше урона. Кроме того, существа с большей силой и выносливостью являются более ценными.
Чтобы объединить их в одну меру, мы скажем, что оценка защищающегося игрока в бою равна сумме сил и выносливости его выживших существ, минус сумма мощностей и выносливости выживающих существ его противника, минус один половина суммы урона, нанесенного защищающемуся игроку. Защищающийся игрок хочет максимизировать этот счет, в то время как атакующий игрок хочет минимизировать его.
В бою, показанном выше, счет был:
Defending player's surviving creatures:
1/4, 0/1
1 + 4 + 0 + 1 = 6
Attacking player's surviving creature:
3/3
3 + 3 = 6
Damage dealt to defending player:
3
6 - 6 - 3/2 = -1.5
Если бы защищающийся игрок вообще не блокировал бой, описанный выше, счет был бы
8 - 10 - (5/2) = -4.5
Оптимальным выбором для защищающегося игрока было бы заблокировать 2/2
с 1/1
и 1/4
и заблокировать 3/3
с 0/1
. Если бы они сделали это, только 1/4
и тот 3/3
выжил бы, и защищающемуся игроку не было бы нанесено никакого урона, делая счет
5 - 6 - (0/2) = -1
Ваша задача - написать программу, которая выдаст оптимальный вариант блокировки для защищающегося игрока. «Оптимальный» означает выбор, который максимизирует счет, учитывая, что противник распределяет урон таким образом, чтобы минимизировать счет, учитывая то, как вы заблокировали.
Это максимин: максимальный балл по распределению урона, который минимизирует балл для каждой комбинации блокировок.
Входные данные: входные данные будут состоять из двух списков из двух кортежей, где каждый из двух кортежей имеет форму (Сила, Прочность). Первый список будет содержать силы и выносливость каждого атакующего существа (существ противника). Второй список будет содержать силы и выносливость каждого из ваших существ.
Кортежи и списки могут быть представлены в любом удобном формате, например:
[[2, 2], [3, 3]]
[[1, 4], [1, 1], [0, 1]]
Вывод: вывод будет состоять из серии из двух кортежей в форме (блокирующее существо, заблокированное существо), то есть одно из ваших существ, за которым следует одно из их существ. Существа будут упоминаться по их индексу в списках ввода. Индексы могут быть 0 или 1 проиндексированы. Опять любой удобный формат. Любой заказ в порядке. Например, оптимальный сценарий блокировки сверху, с учетом вышеприведенного ввода, может быть представлен как:
[0, 0] # 1/4 blocks 2/2
[1, 0] # 1/1 blocks 2/2
[2, 1] # 0/1 blocks 3/3
Примеры:
Input:
[[2, 2], [3, 3]]
[[1, 4], [1, 1], [0, 1]]
Output:
[0, 0]
[1, 0]
[2, 1]
Input:
[[3, 3], [3, 3]]
[[2, 3], [2, 2], [2, 2]]
Output:
[1, 0]
[2, 0]
or
[1, 1]
[2, 1]
Input:
[[3, 1], [7, 2]]
[[0, 4], [1, 1]]
Output:
[1, 0]
or
[0, 0]
[1, 0]
Input:
[[2, 2]]
[[1, 1]]
Output:
(No output tuples).
Вход и выход могут быть через STDIN, STDOUT, CLA, функцию ввода / вывода и т. Д. Применяются стандартные лазейки . Это код-гольф: выигрывает самый короткий код в байтах.
Чтобы прояснить спецификацию и представить первоначальные идеи, этот pastebin предоставляет эталонное решение на Python. Эта best_block
функция является примером решения этой проблемы, и запуск программы обеспечит более подробный ввод и вывод.
источник
Ответы:
JavaScript (ES7),
354348 байтПринимает вход как
([attackers], [defenders])
.Попробуйте онлайн!
Менее гольф и отформатированы
Этот код идентичен версии для гольфа, только без
map
псевдонимов иeval()
переноса для удобства чтения.Как?
Инициализация и основной цикл
push
Мы собираемся заблокировать это фиктивное существо вместо того, чтобы вообще ничего не блокировать. Это позволяет некоторые упрощения в коде.
Строим нашу оборону
Оптимизация атаки
Решения злоумышленников не связаны между собой. Глобальный оптимум для атакующей стороны - это сумма локальных оптимумов для каждого атакующего.
Обновление счета защитника
После каждой итерации атакующего мы обновляем рейтинг защитника следующим образом:
Левая часть вычитает счет атакующего, если он выжил. Правая часть вычитает половину выносливости атакующего, если атака вообще не была заблокирована, или добавляет лучший результат атакующего в противном случае (который является худшим с точки зрения обороняющейся стороны).
источник